四校联考：乐队

四校联考：乐队

tony102

2020 年 10 月 27 日

1308 次浏览

暂无评论

1486字数

总结

四校联考第一场的坑现在来补

这个题的母题就是联合省选A卷那一道组合数问题，可以先做那一道题再来做这一道

## Sol

首先来看我们要处理的式子

$$
\sum_{i=1}^{n} \binom{n}{i}*2^{n-i}*f(i)
$$

把多项式$f(i)$拆成求和的形式

$$
\sum_{i=1}^{n}\sum_{j=0}^{k}a_j i^j*2^{n-i}*\binom{n}{i}
$$

把$a_j$的计算提前，并且我们对$i^j$用第二类斯特林数进行转换

$$
\sum_{i=1}^{n} a_j\sum_{j=0}^{k}\sum_{p=0}^{j} \binom{i}{p}*p!*\begin{Bmatrix} j\\p\end{Bmatrix}*2^{n-i}*\binom{n}{i}
$$

观察$\binom{i}{p}$和$\binom{n}{i}$两项，按照套路这两项可以换成:

$$
\sum_{i=1}^{n} a_j\sum_{j=0}^{k}\sum_{p=0}^{j}p!*\begin{Bmatrix} j\\p\end{Bmatrix}*2^{n-i} * \binom{n}{p}*\binom{n-p}{i-p}
$$

利用$\binom{n}{m}=\binom{n}{n-m}$对$\binom{n-p}{i-p}$进行处理

$$
\sum_{i=1}^{n} a_j\sum_{j=0}^{k}\sum_{p=0}^{j}p!*\begin{Bmatrix} j\\p\end{Bmatrix}*2^{n-i} * \binom{n-p}{n-i}* \binom{n}{p}
$$

如果你熟悉二项式定理推论的话：$(x+1)^n = \sum_{i=1}^{n} \binom{n}{i} * x^i$

$$
\sum_{i=1}^{n} a_j\sum_{j=0}^{k}\sum_{p=0}^{j}p!*\begin{Bmatrix} j\\p\end{Bmatrix}*3^{n-p} * \binom{n}{p}
$$

好了，现在你只要$O(k^2)$地预处理斯特林数和下降幂了

最后再讲一下下降幂的计算方法

$$
n^{\underline{i}} = i!*\binom{n}{p} = \frac{n!}{i!(n-i)!} * i! = \frac{n!}{(n-i)!} = \prod_{i=n-p+1}^{n} i
$$

## Code

代码还是我最喜欢的环节

```CPP
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 5e3 + 5;
const int mod = 998244853;

int n, k;
int S[SIZE][SIZE], pw[SIZE], a[SIZE];

inline int read()
{
	char ch = getchar();
	int f = 1, x = 0;
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
	return x * f;
}

inline int qPow(int a, int b)
{
	int ans = 1;
	for ( ; b; b >>= 1, a = a * a % mod) {
		if (b & 1) ans = ans * a % mod;
	}
	return ans;
}

inline void init()
{
	S[0][0] = 1;
	for (register int i = 1; i <= k; ++ i) {
		for (register int j = 1; j <= i; ++ j) 
			S[i][j] = (S[i - 1][j] * j % mod + S[i - 1][j - 1]) % mod;
	}
	pw[1] = qPow(3, n - k);
	for (register int i = 2; i <= k + 1; ++ i) pw[i] = pw[i - 1] * 3 % mod;
}

signed main()
{
	n = read(), k = read();
	for (register int i = 0; i <= k; ++ i) a[i] = read();
	init();
	int ans = 0;
	for (register int i = 0; i <= k; ++ i) {
		int sum = 0, cnt = 1;
		for (register int j = 0; j <= i; ++ j) {
			sum = (sum + S[i][j] * pw[k - j + 1] % mod * cnt % mod) % mod;
			cnt = cnt * (n - j) % mod;
		}
		ans = (ans + sum * a[i] % mod) % mod;
	}
	printf("%lld\n", ans);
	return 0;
}
```

最后修改：2021 年 09 月 04 日