bzoj 2111: [ZJOI2010]Perm 排列计数
1 ≤ N ≤ 10^6, P≤ 10^9
题意：求1~N的排列有多少种小根堆
1: #include<cstdio>
2: using namespace std;
3: const int N = 1e6+5;
4: typedef long 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) {
9: return t == 1 ? 1 : (p - p / t) * inv(p % t, p) % p;
10: }
11: LL C(LL n, LL m){
12: if(n < m) return 0;
13: if(n < p && m < p)
14: return F[n] * 1ll * inv(F[n-m]%p, p) % p * inv(F[m]%p, p) % p;
15: return C(n/p, m/p) * C(n%p, m%p) %p;
16: }
17: int main(){
18: int i;
19: scanf("%d%lld", &n, &p);
20: F[0] = 1;
21: for(i = 1; i <= n&&i < p; i++) F[i] = F[i-1] * i %p;//阶乘预处理
22: 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: }
26: printf("%lld\n", f[1]);
27: }