题目描述
称一个 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: 复制
16
说明
100% 的数据中, 1 N 10^6, P 10^9,p 是一个质数.
题解
数位 dp? 这怕不是个树位 dp......
我们把原序列看成一棵二叉树
那么就是要我们求大小为 $n$ 的小根堆有多少个 (就是父节点比左右儿子都小)
那么考虑 dp, 设 $dp[i]$ 表示有多少个大小为 $i$ 的小根堆,$val[i]$ 表示 $i$ 的子树的大小
因为父亲必须小于儿子, 所以根节点只能是最小的点, 那么剩下的 $i-1$ 个点里有 $val[l]$ 个可以放在左子树, 剩下的都可以放在右子树, 方案数为 $C_{i-1}^{val[l]}$
然后因为选不同的点之后还能有不同的方案, 所以还要乘上方案数
所以最后的状态转移方程是这样的 $dp[i]=C_{i-1}^{val[l]}*dp[val[l]]*dp[val[r]]$
然后因为要组合数取模, 得用上 Lucas 定理
- //minamoto
- #include<cstdio>
- #define ll long long
- const int N=1e6+5;
- ll inv[N],fac[N],val[N],dp[N],n,mod;
- #define min(a,b) ((a)<(b)?(a):(b))
- ll qpow(ll x,ll y){
- ll res=1;
- while(y){
- if(y&1) res=res*x%mod;
- y>>=1,x=x*x%mod;
- }
- return res;
- }
- void init(){
- int k=min(n,mod-1);
- fac[0]=fac[1]=1;
- for(int i=2;i<=k;++i) fac[i]=fac[i-1]*i%mod;
- inv[k]=qpow(fac[k],mod-2);
- for(int i=k-1;i;--i) inv[i]=(i+1)*inv[i+1]%mod;
- }
- ll C(ll n,ll m){
- if(m>n) return 0;
- return fac[n]*inv[m]%mod*inv[n-m]%mod;
- }
- ll Lucas(ll n,ll m){
- if(m==0||m==n) return 1;
- return Lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod;
- }
- int main(){
- //freopen("testdata.in","r",stdin);
- scanf("%lld%lld",&n,&mod);init();
- for(int i=n;i;--i){
- val[i]=1;if((i<<1)<=n) val[i]+=val[i<<1];if((i<<1|1)<=n) val[i]+=val[i<<1|1];
- if((i<<1|1)<=n) dp[i]=Lucas(val[i]-1,val[i<<1])*dp[i<<1]%mod*dp[i<<1|1]%mod;
- else if((i<<1)<=n) dp[i]=dp[i<<1];
- else dp[i]=1;
- }
- printf("%lld\n",dp[1]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2743952.html