BZOJ 5306 [HAOI2018] 染色

首先，求出$N$个位置，出现次数恰好为$S$的颜色至少有$K$种。

方案数显然为$a_i=\frac{n!\times (m-i)^{m-i\times s}}{(m-K)!\times (s!)^K}\times C(m,K)$

然后二项式反演一下，得到恰好的数量：$ans_i=\sum\limits_{j=i}^n (-1)^{j-i}\times a_i\times C(j,i)$

然后展开一下就可以得到两个多项式：$A_i=\frac{m!\times n!\times (m-i)^{m-i\times s}}{(m-i)!\times (n-s\times i)!\times (s!)^i},b_i=\frac{(-1)^{m-i}}{(m-i)!}$

然后显然答案方案数就是：$C=A\times B ,ans_i=\frac{C[m+i]}{i!}$

最后加一下权即可！

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 262205#define ll long long#define mod 1004535809int a[N],b[N],w[N],n,m,s,lim,fac[10000005],inv[10000005],ans;int q_pow(int x,int n){int ret=1;for(;n;n>>=1,x=(ll)x*x%mod)if(n&1)ret=(ll)ret*x%mod;return ret;}#define inv(x) q_pow(x,mod-2)void NTT(int *a,int len,int flag){ int i,j,k,t,w,x,tmp; for(i=k=0;i
            
             k)swap(a[i],a[k]); for(j=len>>1;(k^=j)
             
              >=1); } for(k=2;k<=len;k<<=1) { t=k>>1;x=q_pow(3,(mod-1)/k);if(flag==-1)x=inv(x); for(i=0;i