Perm 排列计数

内存限制：512 MiB 时间限制：1000 ms 标准输入输出

题目描述

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

输入格式

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

输出格式

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

样例

样例输入

20 23

样例输出

数据范围与提示

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

事实上题目少说一句i为奇数/2就向下取整（虽然说不说都可以推断，说了比较严谨）

既然这样我们可以把它想象成一个二叉堆（小根堆）满足magic 就是满足二叉堆那么magic的方案数就是满足二叉堆的方案数。

但如果暴力计算方式会TLE，我们需要用一种别的方式计算

于是就有了树形dp 设f[i]为以i为根的方案数显然可以由两个儿子贡献过来

当前点因为根是最小的所以size[i]-1表示剩余的节点数然后是在size[i]-1的范围内选size[left]数量的数分配给左儿子

于是

**$f[i]=f[(i <<1)]f[(i<<1|1)]{C_{size[i]-1}^{size[i<<1]}}$**

由于n比较大然后要用lucas定理

然后注意当前点不能大于n转移就完了

下面依然是本人丑陋的代码

#include<bits/stdc++.h>
#define ll long long
#define A 1100000
#define maxn 1000010
#define p 1000000007
using namespace std;
ll m,n,k,f[A],jie[A],ermi[A],ans,ni[A];
inline ll read()
{
    ll f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return f*x;
}
ll meng(ll x,ll k)
{
    ll ans=1;
    for(;k;k>>=1,x=x*x%p)
        if(k&1)
            ans=x%p*ans%p;
    return ans;
}
ll C(ll n,ll m)
{
    if(m==0) return 1;
    if(m>n) return 0;
    else return (jie[n]*ni[m]%p*ni[n-m])%p;
}
void init()
{
    n=read(),k=read();
    m=n-k;
    jie[0]=1;ni[0]=1;ermi[0]=1;
    for(ll i=1;i<=maxn;i++)    ermi[i]=2*ermi[i-1]%(p-1);//2^ermi[i]%p!=2^ermi[i]%p
    for(ll i=1;i<=n;i++)    jie[i]=jie[i-1]*i%p;
    ni[n]=meng(jie[n],p-2);
    for(ll i=n-1;i>=1;i--)ni[i]=ni[i+1]*(i+1)%p;
    for(ll i=0;i<=n;i++)    f[i]=C(n,i)%p*(meng(2,ermi[n-i])%p-1)%p;
}
int main()
{
//    freopen("test.in","r",stdin);freopen("vio.out","w",stdout);
    ans=0;
    init();
    for(ll i=k;i<=n;i++)
    ans=(C(i,k)*f[i]%p*((i-k)&1?-1:1)+ans)%p;
    cout<<(ans%p+p)%p<<endl;
}

View Code

当然也可以线性转移

    for(int i=n;i;--i)
    {
        if(sz[i]<3) dp[i]=1;
        else dp[i]=1ll*dp[lch]*dp[rch]%mod*lucas(sz[i]-1,sz[lch])%mod;
        //不能给右儿子算组合数，可能越界
    }

会快很多