CF961G Partitions

题意

link
求将 n 个物品划分成 k 个集合的所有方案的权值和，权值和为每个集合的大小乘集合元素的和的和。

推式子就完了

一眼得:

\[\sum_{x = 1}^nw_x \sum_{i = 1}^{n}i\binom{n - 1}{i - 1} \begin{Bmatrix} n - i\\ k - 1\end{Bmatrix} \]

和是线性的，直接拆开算每个元素贡献，枚举它所在集合的大小 \(i\)，给它选 \(i - 1\) 个数，剩下 \(n - i\) 个数自己分成 \(k - 1\) 个非空集合。

考虑拆开第二类斯特林数，有个容斥的式子：

\[\begin{Bmatrix} n\\ m \end{Bmatrix} = \frac{1}{m!} \sum_{i = 0}^{m} (-1)^i(m - i)^n\binom{m}{i} \]

\[= \sum_{i = 0}^{m} \frac{(-1)^i(m - i)^n}{i!(m - i)!} \]

实际上只要计算出后面的式子:

\[\sum_{i = 1}^{n}i\binom{n - 1}{i - 1} \sum_{j = 0}^{k - 1} \frac{(-1)^j(k - 1 - j)^{n - i}}{j!(k - 1 - j)!} \]

后面的拆开的式子又不能合回去，那就把它移到前面：

\[\sum_{j = 0}^{k - 1} \frac{(-1)^j}{j!(k - 1 - j)!}\sum_{i = 1}^{n}i\binom{n - 1}{i - 1}(k - 1 - j)^{n - i} \]

发现 \(n - i\) 和 \(i - 1\) 等于 \(n - 1\), 但是多了 \(i\)，要不然就能用二项式定理了，那就拆开，令 \(i = 1 + (i - 1)\)

\[\sum_{j = 0}^{k - 1} \frac{(-1)^j}{j!(k - 1 - j)!}(\sum_{i = 1}^{n}\binom{n - 1}{i - 1}(k - 1 - j)^{n - i} + \sum_{i = 1}^{n}(i - 1)\binom{n - 1}{i - 1}(k - 1 - j)^{n - i}) \]

那么:

\[\sum_{i = 1}^{n}\binom{n - 1}{i - 1}(k - 1 - j)^{n - i} = (k - 1 - j + 1) ^ {n - 1} \]

注意到 \((i - 1)\) 和 \(\binom{n - 1}{i - 1}\), 有这样一个组合恒等式：

\[m \binom{n}{m} = \frac{(n - 1)! n}{(m - 1)! (n - m)!} = n \binom{n - 1}{m - 1} \]

利用这个式子，可以把一个变量替换成不变量，是推组合式子的常用操作。

就有:

\[\sum_{i = 1}^{n}(i - 1)\binom{n - 1}{i - 1}(k - 1 - j)^{n - i}) = \sum_{i = 1}^{n}(n - 1)\binom{n - 2}{i - 2}(k - 1 - j)^{n - i} \]

再提出 \(n - 1\):

\[(n - 1)\sum_{i = 1}^{n - 2}\binom{n - 2}{i - 2}(k - 1 - j)^{n - i} \]

利用二项式定理，就有：

\[(n - 1)(k - 1 - j + 1)^{n - 2} \]

因此，上面的式子为：

\[\sum_{j = 0}^{k - 1} \frac{(-1)^j}{j!(k - 1 - j)!}[(k - j) ^ {n - 1} + (n - 1)(k - j)^{n - 2}] \]

在时间复杂度 \(O(n \log n)\) 就能算出。

不然就得用 MTT 计算第二类斯特林数的生成函数，时间复杂度是大常数 \(O(n \log^2 n)\)， 码量爆炸。

代码

#include
using namespace std;

using ll = long long;
const int MAXN = 200010;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double eps = 1e-9; 

template 
void Read(T &x) {
	x = 0; T f = 1; char a = getchar();
	for(; a < '0' || '9' < a; a = getchar()) if (a == '-') f = -f;
	for(; '0' <= a && a <= '9'; a = getchar()) x = (x * 10) + (a ^ 48);
	x *= f;
}

inline int add(const int &a, const int &b, const int p = mod) {
	static int c;
	c = a + b;
	if (c >= p) c -= p;
	return c; 
} 
inline int dec(const int &a, const int &b, const int p = mod) {
	static int c;
	c = a - b;
	if (c < 0) c += p;
	return c; 
} 
inline int mul(const int &a, const int &b, const int p = mod) {
	return 1ll * a * b % p; 
}
inline int qpow(int a, int b, const int p = mod) {
	int sum(1);
	while(b) {
		if (b & 1) sum = mul(sum, a, p);
		a = mul(a, a, p);
		b >>= 1; 
	}
	return sum; 
}

int n, k; 
 
int f[MAXN], ifa[MAXN]; 
int main() {
	Read(n); Read(k);
	if (n == 1) {
		int w;
		Read(w);
		return cout << w, 0 ; 
	}
	f[0] = 1; 
	for (int i = 1; i <= k - 1; i ++)	
		f[i] = mul(f[i - 1], i);
	ifa[k - 1] = qpow(f[k - 1], mod - 2);
	for (int i = k - 2; i >= 0; i --)
		ifa[i] = mul(ifa[i + 1], i + 1);
	int sum = 0;
	for (int i = 0, p = 1; i <= k - 1; i ++, p = mod - p) 
		sum = add(sum, mul(mul(mul(p, ifa[i]), ifa[k - 1 - i]), add(qpow(k - i, n - 1), mul(n - 1, qpow(k - i, n - 2))))); 
	int ans = 0; 
	for (int i = 1; i <= n; i ++) {
		int w; 
		Read(w);
		ans = add(ans, mul(w, sum));  
	}
	cout << ans; 
	
	return 0;	
}