这一类题都要考虑推式子

首先推出题目要求的式子,枚举正好有\(s\)个颜色的种类(范围\([0,p=min(\lfloor\frac{n}{s}\rfloor,m)]\)),然后对于后面的颜色可能也有数量为\(s\)的,容斥一下即可,即\[ans=\sum_{k=0}^{p}w_k*\binom{m}{k}*\binom{n}{ks}*\frac{(ks)!}{(s!)^k}\sum_{i=0}^{p-k}(-1)^i*\binom{m-k}{i}*\binom{n-ks}{is}*\frac{(is)!}{(s!)^i}*(m-k-i)^{n-ks-is}\]

\[ans=\sum_{k=0}^{p}w_k*\frac{m!}{k!(m-k)!}*\frac{n!}{(ks)!(n-ks)!}*\frac{(ks)!}{(s!)^k}\sum_{i=k}^{p}(-1)^{i-k}*\frac{(m-k)!}{(i-k)!(m-i)!}*\frac{(n-ks)!}{(is-ks)!(n-is)!}*\frac{(is-ks)!}{(s!)^{i-k}}*(m-i)^{n-is}\]

\[ans=n!m!\sum_{k=0}^{p}w_k*\frac{1}{k!(m-k)!}*\frac{1}{(n-ks)!}*\frac{1}{(s!)^k}\sum_{i=k}^{p}(-1)^{i-k}*\frac{(m-k)!}{(i-k)!(m-i)!}*\frac{(n-ks)!}{(n-is)!}*\frac{1}{(s!)^{i-k}}*(m-i)^{n-is}\]

\[ans=n!m!\sum_{k=0}^{p}\frac{w_k}{k!(s!)^k}\sum_{i=k}^{p}\frac{(-1)^{i-k}}{(i-k)!(s!)^{i-k}}*\frac{(m-i)^{n-is}}{(m-i)!(n-is)!}\]

\[ans=n!m!\sum_{i=0}^{p}\frac{(m-i)^{n-is}}{(m-i)!(n-is)!}\sum_{k=0}^{i}\frac{w_k}{k!(s!)^k}*\frac{(-1)^{i-k}}{(i-k)!(s!)^{i-k}}\]

前面可以枚举,后面直接\(NTT\)

#include
    
     #define LL long long#define db double#define il inline#define re register  using namespace std;const int N=100000+10,M=270000+10,O=10000000+10,mod=1004535809,g=3;il int rd(){  int x=0,w=1;char ch=0;  while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}  while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}  return x*w;}int mm,nn,l,a[M],b[M],rdr[M];il int fpow(int a,int b){  int an=1;  while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;}\  return an;}il void ntt(int *a,int op){  int W,w,x,y;  for(int i=0;i
     
      =1;--i) iac[i-1]=1ll*iac[i]*i%mod;  for(int i=0;i<=p;++i) a[i]=1ll*w[i]*iac[i]%mod*fpow(iac[s],i)%mod;  for(int i=0;i<=p;++i) b[i]=(i&1)?mod-1ll*iac[i]*fpow(iac[s],i)%mod:1ll*iac[i]*fpow(iac[s],i)%mod;  mm=p+p;  for(nn=1;nn<=mm;nn<<=1) ++l;  for(int i=0;i
      
       >1]>>1)|((i&1)<<(l-1));  ntt(a,1),ntt(b,1);  for(int i=0;i