這東西還是挺有思想的，道聽途說一些東西，問問DuanYue同志，然后自己打表畫樹推了推，就搞出來了。

首先根據(jù)p i>p i/2（向下取整）這種形式，如果線段樹學(xué)的好的人，一定能看出來，這是在唯一標號法標號后的形式，即父親的權(quán)值大于兩個兒子的權(quán)值，這是一個小根堆的樣子。

那問題就是求給定數(shù)目的數(shù)字，求其能構(gòu)成小根堆的個數(shù)。

這是一個類似樹形dp的問題，我們設(shè)f[i]表示以當前節(jié)點為根所能構(gòu)成小根堆的個數(shù)，那么有狀態(tài)轉(zhuǎn)移方程:

就是說當前節(jié)點及其子樹一共分配了size[i]個數(shù)字，然后分給了左右子樹，有上式Combine種可能，然后把左右兒子的貢獻轉(zhuǎn)移上來。

組合數(shù)還是老規(guī)矩打階乘及其逆元的表，用lucas定理求一下，因為不用的話模數(shù)小的時候會崩，模數(shù)大了lucas也可以自動求組合取模。

實現(xiàn)過程中沒有定義dp數(shù)組（其實size數(shù)組也沒必要），直接帶返回值的dfs搞一下。

代碼略丑，勿看（主要是懶，直接define int long long 了）。

#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<cstdio> #include<vector> #include<queue> #define int long long using namespace std; int n,p; int size[2000000]; int fac[2000000],inv[2000000]; int qpow(int x,int k){int ans=1;for(;k;k>>=1,x=1ll*x*x%p)if(k&1) ans=1ll*ans*x%p;return ans; } void pre(){fac[0]=1;for(int i=1;i<min(n,p);i++)fac[i]=1ll*fac[i-1]*i%p;inv[min(n,p)-1]=qpow(fac[min(n,p)-1],p-2);for(int i=min(n,p)-1;i>=1;i--)inv[i-1]=1ll*inv[i]*i%p; } int com(int x,int y){if(y>x) return 0;return ((1ll*fac[x]*inv[y])%p*inv[x-y]%p)%p; } int lucas(int x,int y){if(!y) return 1;return com(x%p,y%p)*lucas(x/p,y/p)%p; } int dfs(int x){if(x>n) return 1;size[x]++;int a=dfs(x<<1)%p;int b=dfs(x<<1|1)%p;size[x]+=size[x<<1]+size[x<<1|1];return 1ll*((a*b)%p*(lucas(size[x]-1,size[x<<1])%p))%p; } signed main(){scanf("%lld%lld",&n,&p);pre();/*for(int i=1;i<=p;i++)cout<<fac[i]<<" ";cout<<endl;for(int i=1;i<=p;i++)cout<<inv[i]<<" ";cout<<endl;*/printf("%lld",dfs(1)%p);return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/Yu-shi/p/11121778.html

總結(jié)

以上是生活随笔為你收集整理的Zjoi2010排列计数Perm的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。