留个位置
本题...一言难尽啊...
首先可以发现，恰好为$S$个的颜色数量为$M=min(frac{n}{S},m)$
首先我们设$g(i)$表示至少选了$i$种颜色达到恰好$S$个的方案数，那么$g(i)=C_{m}^{i}(m-i)^{n-iS}frac{n!}{(S!)^{i}(n-iS)!}$（这个叫方案数其实并不准确，因为事实上并不能保证中间没有重复，但是这样设计状态对下面的操作有帮助）
这个公式的来历是首先人为选出$i$种颜色，然后剩下的格子随意摆放，再乘一个有重复的排列公式
但是为什么说他并不是准确的至少选$i$种颜色达到恰好$S$个的方案数呢？
因为会有大量的重复！
比如我们有颜色$a,b,c$，$S=2,n=6$，那么按照我们的计算方法，至少有两种颜色达标的就会把$2a,2b,2c$这种组合统计$3$次！
因此叫做方案数并不准确！
但是，如果我们设$f(i)$表示恰好选了$i$种颜色达到恰好$S$个的方案数（这是真正的方案数，也就是答案）
那么显然有递推：$g(k)=sum_{i=k}^{M} C_{i}^{k}f(i)$
这就一目了然了，这个递推的原理是我们枚举实际上有$i$种颜色达标，然后我们只需要其中$k$种，因此一个$f(i)$在计算$g(i)$时贡献应当被统计$C_{i}^{k}$次！
二项式反演，直接得到：$f(k)=sum_{i=k}^{M}(-1)^{i-k}C_{i}^{k}g(i)$
展开组合数，得到：
$f(k)=sum_{i=k}^{M}(-1)^{i-k}frac{i!}{k!(i-k)!}g(i)$
移项整理，有：$f(k)k!=sum_{i=k}^{M}frac{(-1)^{i-k}}{(i-k)!}g(i)i!$
这个就是一个卷积的形式了，$NTT$优化即可
（具体地，将$frac{(-1)^{i-k}}{(i-k)!}$看做一部分，$g(i)i!$看做另一部分，然后将后半部分翻转就是一个卷积了）
贴代码：
#include <cstdio> #include <algorithm> #define ll long long using namespace std; const ll mode=1004535809; ll mul[10000005]; ll minv[10000005]; ll inv[10000005]; int to[(1<<20)+5]; int n,m,s,M; ll v[10000005]; ll F[(1<<20)+5],G[(1<<20)+5],H[(1<<20)+5]; void init() { mul[0]=mul[1]=inv[0]=inv[1]=minv[0]=minv[1]=1; for(int i=2;i<=max(n,m);++i) { mul[i]=mul[i-1]*i%mode; inv[i]=(mode-mode/i)*inv[mode%i]%mode; minv[i]=minv[i-1]*inv[i]%mode; } } ll pow_mul(ll x,ll y) { ll ret=1; while(y) { if(y&1)ret=ret*x%mode; x=x*x%mode,y>>=1; } return ret; } void NTT(ll *a,int len,int k) { for(int i=0;i<len;i++)if(i<to[i])swap(a[i],a[to[i]]); for(int i=1;i<len;i<<=1) { ll w0=pow_mul(3,(mode-1)/(i<<1)); for(int j=0;j<len;j+=(i<<1)) { ll w=1; for(int o=0;o<i;o++,w=w*w0%mode) { ll w1=a[j+o],w2=a[j+o+i]*w%mode; a[j+o]=(w1+w2)%mode,a[j+o+i]=(w1-w2+mode)%mode; } } } if(k==-1) { ll inv=pow_mul(len,mode-2); for(int i=1;i<(len>>1);i++)swap(a[i],a[len-i]); for(int i=0;i<len;i++)a[i]=a[i]*inv%mode; } } ll C(ll x,ll y) { if(x<y)return 0; return mul[x]*minv[y]%mode*minv[x-y]%mode; } ll get_F(ll x) { return C(m,x)*pow_mul(m-x,n-x*s)%mode*mul[n]%mode*pow_mul(minv[s],x)%mode*minv[n-x*s]%mode; } template <typename T>inline void read(T &x) { int f=1; x=0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x*=f; } int main() { read(n),read(m),read(s); init(); M=min(n/s,m); for(int i=0;i<=m;i++)read(v[i]); int lim=1,l=0; while(lim<=2*M)lim<<=1,l++; for(int i=0;i<lim;i++)to[i]=((to[i>>1]>>1)|((i&1)<<(l-1))); ll x0=1; for(int i=0;i<=M;i++)F[i]=x0*minv[i]%mode,G[i]=get_F(M-i)*mul[M-i]%mode,x0=mode-x0; NTT(F,lim,1),NTT(G,lim,1); for(int i=0;i<lim;i++)H[i]=F[i]*G[i]%mode; NTT(H,lim,-1); ll ans=0; for(int i=0;i<=M;i++)ans=(ans+H[M-i]*v[i]%mode*minv[i]%mode)%mode; printf("%lld ",ans); return 0; }