洛谷P2606 [ZJOI2010]排列计数

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

20 23

输出样例#1：

说明

100%的数据中，1 ≤N ≤ 10^6, P≤ 10^9，p是一个质数。

题目大意：求1--n能构成小根堆的排列

题解：

暴力30...

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int n,p,ans,a[];

int main(){

    scanf("%d%d",&n,&p);

    for(int i=;i<=n;i++)a[i]=i;

    do{

        bool flag=false;

        for(register int i=;i<=n;i++){

            if(a[i]<a[i/]){

                flag=true;break;

            }

        }

        if(!flag)ans=(ans%p+%p)%p;

    }while(next_permutation(a+,a+n+));

    printf("%d\n",ans);

    return ;

}

正解：Lucas定理+树形dp

没看出来是小根堆...我这个沙茶...

然后根一定是最小的，然后f[i]=c(s[i]-1,s[i<<1])*f[l]*f[r]

f[i]表示以i为根的小根堆的数量....然后左子树的大小就是从s[i]-1（减去根

中选出s[i<<1]，用Lucas定理求就行啦...

因为有子问题的....

ps：不知道为什么一直WA，抱着试试看的心态，我多加了一个取模。

你猜怎么着？就A了....

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 1000009

#define LL long long

using namespace std;

LL n,p;

LL f[maxn],inv[maxn],s[*maxn],dp[maxn];

LL ksm(LL x,LL y){

    LL ret=%y;

    while(y){

        if(y&)ret=(1LL*ret*x)%p;

        x=1LL*x*x%p;

        y>>=;

    }

    return ret;

}

void pre(){

    f[]=inv[]=;

    for(int i=;i<=n;i++)f[i]=(1LL*f[i-]*i)%p;

    for(int i=;i<=n;i++)inv[i]=ksm(f[i],p-)%p;

}

LL C(LL n,LL m){

    return 1LL*f[n]*inv[m]%p*inv[n-m]%p;

}

LL Lucas(LL n,LL m){

    if(!m)return ;

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

}

int main(){

    scanf("%lld%lld",&n,&p);

    pre();

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

        s[i]=s[i<<]+s[i<<|]+;

        dp[i]=Lucas(s[i]-,s[i<<])%p;

        if((i<<)<=n)dp[i]=dp[i]*dp[i<<]%p;

        if((i<<|)<=n)dp[i]=dp[i]*dp[i<<|]%p;

        dp[i]=dp[i]%p;

    }

    printf("%lld\n",dp[]%p);

    return ;

}

巴特西

洛谷P2606 [ZJOI2010]排列计数

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章