[HAOI2018]染色-白红宇

[HAOI2018]染色

阅读量：5021 次

发布时间：2019-06-12

本文共 1489 字，大约阅读时间需要 4 分钟。

神仙题。

令\(lim=min\{[n/s,m]\}\),容斥之后暴力推式子，有

\[ans=m!n!\sum_{i=0}^{lim}\frac{(m-i)^{n-is}}{(s!)^i(m-i)!(n-is)!}\sum_{i=0}^{j}\frac{w_i}{i!}\frac{(-1)^{j-i}}{(j-i)!}\]

\(NTT\)即可。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   #include
                    
                     #define FILE "a"#define mp make_pair#define pb push_back#define RG register#define il inlineusing namespace std;typedef unsigned long long ull;typedef vector
                     
                      VI;typedef long long ll;typedef double dd;const dd eps=1e-10;const int mod=1004535809;const int N=10000010;const dd pi=acos(-1);const int inf=2147483647;const ll INF=1e18+1;il ll read(){ RG ll data=0,w=1;RG char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')w=-1,ch=getchar(); while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar(); return data*w;}il void file(){ srand(time(NULL)+rand()); freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout);}il int poww(int a,int b){ RG int ret=1; for(;b;b>>=1,a=1ll*a*a%mod) if(b&1)ret=1ll*ret*a%mod; return ret;}int invf[N],fac[N];il void init(){ invf[0]=fac[0]=1; for(RG int i=1;i
                      
                       >1]>>1)|((i&1)<<(l-1)); for(RG int i=0;i
                       
                        
                         >1);k++,w=1ll*w*wn%mod){ RG int x=1ll*a[k+(i>>1)]*w%mod; a[k+(i>>1)]=(a[k]-x+mod)%mod; a[k]=(a[k]+x)%mod; } } } if(opt==-1) for(RG int i=0,rv=poww(n,mod-2);i