[HAOI2018]染色

标签：frac ifac int 染色 LL rev text HAOI2018

\(\text{Solution}\)

第二道二项式反演题
挺套路的
设 \(g(i)\) 为恰好出现 \(S\) 次的颜色至少有 \(i\) 种
那么

\[g(i)=\binom{m}{i}\binom{n}{is}\frac{(is)!}{(s!)^i}(m-i)^{n-is} \]

然后二项式反演

\[f(i)=\sum_{j=i}^m (-1)^{j-i} \binom{j}{i} g(j) \]

这是 \(m^2\) 的
考虑把组合数拆开整理下看能否卷积

\[\begin{aligned} f(i) &=\sum_{j=i}^m (-1)^{j-i} \frac{j!}{i!(j-i)!} g(j) \\ &=\frac{1}{i!}\sum_{j=i}^m \frac{(-1)^{j-i}}{(j-i)!} j!g(j) \\ \end{aligned} \]

显然翻转系数就可以 \(\text{NTT}\) 了

\(\text{Code}\)

#include <bits/stdc++.h>
#define IN inline
using namespace std;

typedef long long LL;
const int N = 262155, P = 1004535809;
int n, m, s, w[N], fac[10000005], ifac[10000005], rev[N], g[N], f[N], h[N];

IN int fpow(int x, int y){int s = 1; for(; y; y >>= 1, x = (LL)x * x % P) if (y & 1) s = (LL)s * x % P; return s;}
IN int C(int n, int m){return (LL)fac[n] * ifac[m] % P * ifac[n - m] % P;}
IN void Add(int &x, int y){if ((x += y) >= P) x -= P;}

IN void NTT(int *a, int len, int inv) {
	for(int i = 0; i < len; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for(int mid = 1; mid < len; mid <<= 1) {
		int I = fpow(3, (P - 1) / (mid << 1));
		if (inv == -1) I = fpow(I, P - 2);
		for(int i = 0; i < len; i += (mid << 1)) {
			for(int j = 0, W = 1; j < mid; j++, W = (LL)W * I % P) {
				int x = a[i + j], y = (LL)W * a[i + j + mid] % P;
				a[i + j] = (x + y) % P, a[i + j + mid] = (x - y + P) % P;
			}
		}
	}
	if (inv == 1) return;
	inv = fpow(len, P - 2); for(int i = 0; i < len; i++) a[i] = (LL)a[i] * inv % P;
}

int main() {
	scanf("%d%d%d", &n, &m, &s); int mm = min(m, n / s);
	for(int i = 0; i <= m; i++) scanf("%d", &w[i]);
	fac[0] = ifac[0] = ifac[1] = 1;
	for(int i = 1; i <= max(n, m); i++) fac[i] = (LL)fac[i - 1] * i % P;
	for(int i = 2; i <= max(n, m); i++) ifac[i] = (LL)ifac[P % i] * (P - P / i) % P;
	for(int i = 2; i <= max(n, m); i++) ifac[i] = (LL)ifac[i] * ifac[i - 1] % P;
	int ipws = 1;
	for(int i = 0; i <= mm; i++, ipws = (LL)ipws * ifac[s] % P)
		g[i] = (LL)C(m, i) * C(n, i * s) % P * fac[s * i] % P * ipws % P * fpow(m - i, n - i * s) % P;
	for(int i = 0; i <= mm; i++) g[i] = (LL)g[i] * fac[i] % P, h[i] = (LL)((i & 1) ? P - ifac[i] : ifac[i]);
	reverse(g, g + mm + 1);
	int len = 1, bit = 0;
	while (len <= 2 * mm) len <<= 1, bit++;
	for(int i = 1; i < len; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bit - 1);
	NTT(g, len, 1), NTT(h, len, 1);
	for(int i = 0; i < len; i++) g[i] = (LL)g[i] * h[i] % P;
	NTT(g, len, -1);
	for(int i = 0; i <= mm; i++) f[mm - i] = (LL)g[i] * ifac[mm - i] % P;
	int ans = 0;
	for(int i = 0; i <= mm; i++) Add(ans, (LL)f[i] * w[i] % P);
	printf("%d\n", ans);
}

标签：frac,ifac,int,染色,LL,rev,text,HAOI2018
From： https://www.cnblogs.com/leiyuanze/p/17112715.html