题解 LOJ #2527. 「HAOI2018」染色

题目链接

感觉网上的题解好像都是二项式反演，这里给出一种新的做法。

我们先考虑按照 (W(i)=w_i) 做牛顿级数：

[W(x)=sum_{t=0}^mc_tinom{x}{t} ]

现在考虑这东西的组合意义：每个大小恰好为 (i) 的集合的贡献相当于是枚举它每个大小为 (t) 的子集，然后乘上一个贡献的系数。这样一来就可以直接枚举 (t)，然后考虑有多少种情况可以找出一个大小为 (t) 的子集，这就是：

[inom mtinom{n}{St}frac{(St)!}{(S!)^t}(n-St)^{m-t} ]

总的答案就是：

[sum_t c_tinom mtinom{n}{St}frac{(St)!}{(S!)^t}(n-St)^{m-t} ]

直接做就没了。

#include<poly.h>

const int maxm = 1E+7 + 5;

ll n = getll(), m = getll(), s = getll();
ll Fac[maxm], Inv[maxm]; poly w, C;

inline ll sgn(int x) { return x & 1 ? mod - 1 : 1; }
inline ll binom(int n, int m) { return Fac[n] * Inv[m] % mod * Inv[n - m] % mod; }

int main() {
	Fac[0] = 1; int T = std::max(n, m);
	for(int i = 1; i <= T; ++i)
		Fac[i] = Fac[i - 1] * i % mod;
	Inv[T] = fsp(Fac[T], mod - 2);
	for(int i = T; i >= 1; --i)
		Inv[i - 1] = Inv[i] * i % mod;
	
	for(int i = 0; i <= m; ++i) w[i] = getll() * Inv[i] % mod;
	for(int i = 0; i <= m; ++i) C[i] = sgn(i) * Inv[i] % mod;
	
	C = C * w;
	for(int i = 0; i <= m; ++i)
		C[i] = C[i] * Fac[i] % mod;
	
	ll ans = 0;
	for(int t = 0; t <= m && t * s <= n; ++t) {
		(ans += C[t] * binom(n, t * s) % mod * binom(m, t) % mod *
			fsp(m - t, n - s * t) % mod * Fac[t * s] % mod * fsp(Inv[s], t)) %= mod;
	} putll(ans), IObuf::flush();
}