题目链接：
题目大意：$n$个位置染$m$种颜色，如果出现次数恰为$S$次的颜色有$k$种，则对答案有$W_k$的贡献，求所有染色方案的答案之和$\bmod 1004535809$。
数据范围：$n\leq 10^7,m\leq 10^5,S\leq 150,0\leq W_i\leq 1004535808$
首先是要推式子的。
首先我们知道，出现次数恰为$S$次的至多$up=\min(m,\frac{n}{S})$种。
设恰好出现$S$次的颜色至少$i$种，则
$$f_i=C_m^i*\frac{n!}{(S!)^i(n-iS)!}*(m-i)^{n-iS}$$
这三项分别是选$i$种颜色，对现在这$i+1$种颜色（选定的$i$种和未染色的）做可重集排列，对剩下的$n-iS$个位置任意染色。
然后用容斥原理就可以得出，恰好出现$S$次的颜色正好$i$种的方案数
$$ans_i=\sum_{j=i}^{up}(-1)^{j-i}C_j^if_j$$
所以
$$\frac{ans_i}{i!}=\sum_{j=i}^{up}\frac{(-1)^{j-i}}{(j-i)!}*\frac{f_j}{j!}$$
如果你不知道如何做，把第一个数组先反转再向右平移$up$位，再把计算后的$ans_i$左移$up$位就可以了。
1 #include2 #include 3 #define Rint register int 4 using namespace std; 5 typedef long long LL; 6 const int N = 400003, G = 3, Gi = 334845270, mod = 1004535809; 7 int n, m, s, up, W[N], fac[10000003], inv[10000003], f[N], g[N], ans; 8 inline int kasumi(int a, int b){ 9 int res = 1;10 while(b){11 if(b & 1) res = (LL) res * a % mod;12 a = (LL) a * a % mod;13 b >>= 1;14 }15 return res;16 }17 inline void init(){18 fac[0] = 1;19 for(Rint i = 1;i <= 10000000;i ++) fac[i] = (LL) i * fac[i - 1] % mod;20 inv[0] = inv[1] = 1;21 for(Rint i = 2;i <= 10000000;i ++) inv[i] = (LL) inv[mod % i] * (mod - mod / i) % mod;22 for(Rint i = 1;i <= 10000000;i ++) inv[i] = (LL) inv[i] * inv[i - 1] % mod;23 }24 inline int C(int n, int m){25 if(n < m) return 0;26 return (LL) fac[n] * inv[m] % mod * inv[n - m] % mod;27 }28 int rev[N];29 inline void NTT(int *A, int limit, int type){30 for(Rint i = 0;i < limit;i ++)31 if(i < rev[i]) swap(A[i], A[rev[i]]);32 for(Rint mid = 1;mid < limit;mid <<= 1){33 int Wn = kasumi(type == 1 ? G : Gi, (mod - 1) / (mid << 1));34 for(Rint j = 0;j < limit;j += mid << 1){35 int w = 1;36 for(Rint k = 0;k < mid;k ++, w = (LL) w * Wn % mod){37 int x = A[j + k], y = (LL) w * A[j + k + mid] % mod;38 A[j + k] = (x + y) % mod;39 A[j + k + mid] = (x - y + mod) % mod;40 }41 }42 }43 if(type == -1){44 int inv = kasumi(limit, mod - 2);45 for(Rint i = 0;i < limit;i ++) A[i] = (LL) A[i] * inv % mod;46 }47 }48 int main(){49 scanf("%d%d%d", &n, &m, &s);50 for(Rint i = 0;i <= m;i ++) scanf("%d", W + i);51 init(); up = min(m, n / s);52 for(Rint i = 0;i <= up;i ++)53 f[i] = (LL) C(m, i) * fac[i] % mod * fac[n] % mod * kasumi(inv[s], i) % mod * inv[n - i * s] % mod * kasumi(m - i, n - i * s) % mod;54 for(Rint i = 0;i <= up;i ++)55 g[i] = ((up - i) & 1) ? (mod - inv[up - i]) : inv[up - i];56 int limit = 1, L = -1;57 while(limit <= (up << 1)){limit <<= 1; ++ L;}58 for(Rint i = 0;i < limit;i ++)59 rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << L);60 NTT(f, limit, 1); NTT(g, limit, 1);61 for(Rint i = 0;i < limit;i ++) f[i] = (LL) f[i] * g[i] % mod;62 NTT(f, limit, -1);63 for(Rint i = 0;i <= up;i ++)64 ans = (ans + (LL) W[i] * f[up + i] % mod * inv[i] % mod) % mod;65 printf("%d\n", ans);66 }
