bzoj2111 Perm 排列计数-程序员宅基地

称一个1,2,...,N的排列P1,P2...,Pn是Magic的，当且仅当2<=i<=N时，Pi>Pi/2. 计算1，2，...N的排列中有多少是Magic的，答案可能很大，只能输出模P以后的值

Input

输入文件的第一行包含两个整数 n和p，含义如上所述。

Output

输出文件中仅包含一个整数，表示计算1,2,⋯, �的排列中， Magic排列的个数模 p的值。

Sample Input

20 23

Sample Output

16

Hint

 

100%的数据中，1 ≤ � N ≤ 106, P� ≤ 10^9，p是一个质数。 数据有所加强

 

题解：题目意思比较好理解，就是问你有多少种小根堆，那么根可以确定，然后左边右边就是

组合一下，确定，如果只有一个点，那么方案数就为1，size为1，不然就是左右子树合并。

这样瞎搞。。。(⊙o⊙)…，就好了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 1000007
#define M 1007
#define ll long long
using namespace std;

int n,p;
ll fac[N],ni[N],f[N];
int siz[N];

ll C(int n,int m)
{
    if(m>n) return 0;
    if(n<p) return fac[n]*ni[m]%p*ni[n-m]%p;
    return C(n/p,m/p)*C(n%p,m%p)%p;
}
int main()
{
    int i;
    scanf("%d%d",&n,&p);
    fac[0]=ni[0]=ni[1]=1;
    
    for(i=1;i<=n&&i<p;i++)
        fac[i]=fac[i-1]*i%p;
    for(i=2;i<=n&&i<p;i++)
        ni[i]=(p-p/i)*ni[p%i]%p;
        
    for(i=2;i<=n&&i<p;i++)
        (ni[i]*=ni[i-1])%=p;
    for(i=n;i>=1;i--)
    {
        if(i*2+1<=n)
        {
            siz[i]=1+siz[i*2]+siz[i*2+1];
            f[i]=f[i*2]*f[i*2+1]%p*C(siz[i]-1,siz[i*2])%p;
        }
        else if(i*2<=n)
        {
            f[i]=f[i*2];
            siz[i]=1+siz[i*2];
        }
        else
        {
            f[i]=1;
            siz[i]=1;
        }
    }
    printf("%lld\n",f[1]);
}