bzoj 2111: [ZJOI2010]Perm 排列计数

神题。。。

扒自某神犇题解：

http://blog.****.net/aarongzk/article/details/50655471

 #include<bits/stdc++.h>
 #define LL long long
 using namespace std;
 inline LL ra()
 {
     LL x=; char ch=getchar();
     while (ch<'' || ch>'') ch=getchar();
     while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
     return x;
 }

 const int maxn=;

 LL n,mod,f[maxn],size[maxn];
 LL fac[maxn],inv[maxn];

 LL C(int n, int m)
 {
     if (n<m) return ;
     if (n<mod && m<mod) return fac[n]*inv[m]%mod*inv[n-m]%mod;
     return C(n/mod,m/mod)*C(n%mod,m%mod);
 }

 int main()
 {
     n=ra(); mod=ra(); fac[]=;
     for (int i=; i<=n; i++) fac[i]=fac[i-]*i%mod;
     inv[]=inv[]=;
     for (int i=; i<=n; i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
     for (int i=; i<=n; i++) inv[i]=inv[i]*inv[i-]%mod;
     for (int i=n; i>=; i--)
     {
         size[i]=size[i<<]+size[i<<|]+;
         f[i]=((i<<)>n?:f[i<<])*((i<<|)>n?:f[i<<|])%mod*C(size[i]-,size[i<<])%mod;
     }
     cout<<f[]<<endl;
     return ;
 }