Perm 排列计数

分手后的思念是犯贱 2021-11-11 01:38 199阅读 0赞

排列组合这部分确实很水，但关键是想到树，堆。

i与2×i，2×i+1有关，符合树上节点编号的特点，加上大小限制就是堆的性质了。

这个堆中存的是节点编号所以大小固定，每个节点的size\[i\]固定往里边填数（排列组合部分）;

设f\[i\]是以i为根的组合方案数,

f\[i\]=f\[i\*2\]\*f\[i\*2+1\]\*C(size\[i\]-1,size\[2\*i\]),在符合比i大的数里随机选size\[2\*i\]个分给左树，剩下的是右数。

n,m很大用lucas定理。

C（n,m）%p=C(n%p,m%p)\*C(n/p,m/p);

递归：lucas(n,m)( =C(n,m)%p )=C(n%p,m%p)\*lucas(n/p,m/p)%p;

阶乘可以打表。虽然P可能到1e9,但n%p,一定小于n，所以打到n就完事了。

逆元部分可打表也可快速幂：

根据费马小定理。

p为质，x^p-1同余1（mod p）;所以x\*x^p-2同余1;x的逆元就是x^p-2;

ll C(int n,int m)  
\{   
    if(m>n) return 0;  
    return fac\[n\]\*qpow(fac\[m\]\*fac\[n-m\]%p,p-2)%p;  
\}

%p也可以在快速幂里写但不能忽略，因为a\*a%p这可能会炸...WA36原因。

1不是质数不考虑。

总结：树编号的特点灵活用，知识间的结合，观察数列，数，编号的特点疯狂联想。

lucas定理。

mod p要考虑清楚是否需要是否可能炸。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<iostream>
    using namespace std;
    #define ll long long
    const int maxn=2e6+5;
    int n,p,size[maxn];
    ll f[maxn],fac[maxn];
    void init()
    {
        fac[0]=1;
        int turn=min(n,p);
        for(int i=1;i<=turn;i++)
            fac[i]=fac[i-1]*i%p;
    }
    ll qpow(ll a,int b)
    {
        ll ans=1;
        while(b)
        {
            if(b&1) ans=ans*a%p;
            b>>=1;
            a=a*a%p;
        }
        return ans;
    }
    ll C(int n,int m)
    {
        if(m>n) return 0;
        return fac[n]*qpow(fac[m]*fac[n-m]%p,p-2)%p;
    }
    ll lucas(int n,int m)
    {
       if(!m) return 1;
       return C(n%p,m%p)*lucas(n/p,m/p)%p;
    }
    ll F(int x)
    {
        if(x>n) return 1;
        f[x]=( F(2*x)*F(2*x+1) )%p *lucas(size[x]-1,size[2*x]) %p;
        return f[x];
    }
    int Size(int x)
    {
        if(x>n) return 0;
        size[x]=Size(2*x)+Size(2*x+1)+1;
        return size[x];
    }
    int main()
    {
        scanf("%d%d",&n,&p);
        if(p==1)
        {
            printf("0");
            return 0;
        }
        init();
        size[1]=Size(1);
        f[1]=F(1);
        printf("%lld",f[1]);
    }

转载于:https://www.cnblogs.com/three-D/p/11126738.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/d63f961151df415cb5a15b388eb3a0fe.png