题目链接：洛谷
题目大意：$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$位就可以了。
#include<cstdio>
#include<algorithm>
#define Rint register int
using namespace std;
typedef long long LL;
const int N = , G = , Gi = , mod = ;
int n, m, s, up, W[N], fac[], inv[], f[N], g[N], ans;
inline int kasumi(int a, int b){
int res = ;
while(b){
if(b & ) res = (LL) res * a % mod;
a = (LL) a * a % mod;
b >>= ;
}
return res;
}
inline void init(){
fac[] = ;
for(Rint i = ;i <= ;i ++) fac[i] = (LL) i * fac[i - ] % mod;
inv[] = inv[] = ;
for(Rint i = ;i <= ;i ++) inv[i] = (LL) inv[mod % i] * (mod - mod / i) % mod;
for(Rint i = ;i <= ;i ++) inv[i] = (LL) inv[i] * inv[i - ] % mod;
}
inline int C(int n, int m){
if(n < m) return ;
return (LL) fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int rev[N];
inline void NTT(int *A, int limit, int type){
for(Rint i = ;i < limit;i ++)
if(i < rev[i]) swap(A[i], A[rev[i]]);
for(Rint mid = ;mid < limit;mid <<= ){
int Wn = kasumi(type == ? G : Gi, (mod - ) / (mid << ));
for(Rint j = ;j < limit;j += mid << ){
int w = ;
for(Rint k = ;k < mid;k ++, w = (LL) w * Wn % mod){
int x = A[j + k], y = (LL) w * A[j + k + mid] % mod;
A[j + k] = (x + y) % mod;
A[j + k + mid] = (x - y + mod) % mod;
}
}
}
if(type == -){
int inv = kasumi(limit, mod - );
for(Rint i = ;i < limit;i ++) A[i] = (LL) A[i] * inv % mod;
}
}
int main(){
scanf("%d%d%d", &n, &m, &s);
for(Rint i = ;i <= m;i ++) scanf("%d", W + i);
init(); up = min(m, n / s);
for(Rint i = ;i <= up;i ++)
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;
for(Rint i = ;i <= up;i ++)
g[i] = ((up - i) & ) ? (mod - inv[up - i]) : inv[up - i];
int limit = , L = -;
while(limit <= (up << )){limit <<= ; ++ L;}
for(Rint i = ;i < limit;i ++)
rev[i] = (rev[i >> ] >> ) | ((i & ) << L);
NTT(f, limit, ); NTT(g, limit, );
for(Rint i = ;i < limit;i ++) f[i] = (LL) f[i] * g[i] % mod;
NTT(f, limit, -);
for(Rint i = ;i <= up;i ++)
ans = (ans + (LL) W[i] * f[up + i] % mod * inv[i] % mod) % mod;
printf("%d\n", ans);
}
luogu4491