bzoj 2111: [ZJOI2010]Perm 排列计数 （dp+卢卡斯定理）

   1: #include<cstdio>

namespace std;

int N = 1e6+5;

long LL;

   5: LL m, p, T, x, y, F[N];

   6: LL n, size[N<<1];

   7: LL f[N];

   8: LL inv(LL t, LL p) {

return t == 1 ? 1 : (p - p / t) * inv(p % t, p) % p;

  10: }

  11: LL C(LL n, LL m){

return 0;

if(n < p && m < p)

return F[n] * 1ll * inv(F[n-m]%p, p) % p * inv(F[m]%p, p) % p;

return C(n/p, m/p) * C(n%p, m%p) %p;

  16: }

int main(){

int i;

, &n, &p);

  20:     F[0] = 1;

//阶乘预处理

for(i = n; i; i--) {

  23:         size[i] = size[i<<1] + size[i<<1|1] + 1;

  24:         f[i] = C(size[i]-1, size[i<<1])*((i<<1)>n?1:f[i<<1])%p*((i<<1|1)>n?1:f[i<<1|1])%p;

  25:     }

, f[1]);

  27: }