注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2111][ZJOI2010]Perm 排列计数  

2014-12-01 20:18:41|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2111: [ZJOI2010]Perm 排列计数

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 1109  Solved: 175
[Submit][Status]

Description

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

Input

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

Output

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

Sample Input

20 23

Sample Output

16

HINT

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

Solution

F[n]表示答案。

题意可转换为:由1~n构成的小根堆有多少种?

假设n>3,并且第二号节点左子树大小为d1,右子树大小为d2,三号节点为d3,d4,显然最小编号只能放1号节点,次小编号只能是1号的儿子。有F[n]=

F[d1]*C(d1+d2+d3+d4+1,d1)*F[d2]*C(d2+d3+d4+1,d2)*F[d3+d4+1] //次小编号为左儿子

+F[d1+d2+1]*C(d1+d2+d3+d4+1,d1+d2+1)*F[d3]*C(d3+d4,d3)*F[d4] //次小编号为右儿子

记忆化搜索就行了没必要一个个算,有些F值(快一半)是用不到的。

化简得:

F[x]=F[d]*F[x-1-d]*fac[x-1]/fac[d]/fac[x-1-d]

d为除去根节点外任意一个子树的大小。

但是怎么也过不了。。。

Code

AC

/**************************************************************
    Problem: 2111
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:124 ms
    Memory:16436 kb
****************************************************************/
 
#include<cstdio>
typedef long long ll;
int n,i;ll p,fac[1000010],F[1000010];
ll power(ll t,ll k){
    ll f=1;
    for(;k;k>>=1,t=(t*t)%p)k&1?f=(f*t)%p:1;
    return f;
}
ll solve(int x){
    if(F[x]!=-1)return F[x]%=p;
    int ret=x-2,d=1,d1,d2,d3,d4;
    for(;d<<1<x+1;d<<=1);d--;
    if(x-d>(d+1>>1)+(d+1>>2))d1=d2=d3=d>>1,d4=ret-1-d1-d2-d3;
    else if(x-d>(d+1>>1))d1=d2=d>>1,d4=d1>>1,d3=ret-1-d1-d2-d4;
    else if(x-d>(d+1>>2))d1=d>>1,d3=d4=d1>>1,d2=ret-1-d1-d3-d4;
    else d2=d3=d4=d>>2,d1=ret-1-d2-d3-d4;
    F[x]=solve(d1)*solve(d2)%p*solve(d3+d4+1)%p*fac[ret]%p*power(fac[d1],p-2)%p*power(fac[d2],p-2)%p*power(fac[d3+d4+1],p-2)%p+solve(d1+d2+1)*solve(d3)%p*solve(d4)%p*fac[ret]%p*power(fac[d1+d2+1],p-2)%p*power(fac[d3],p-2)%p*power(fac[d4],p-2)%p;
    return F[x]%=p;
}
int main(){
    scanf("%d%lld",&n,&p);
    for(fac[0]=1,i=1;i<=n;i++)fac[i]=fac[i-1]*i%p,F[i]=-1;
    F[1]=1,F[2]=1,F[3]=2,F[4]=3,F[5]=8,F[6]=20,F[7]=80;
    printf("%lld",solve(n)%p);
}

Wa
/**************************************************************
    Problem: 2111
    User: wjy1998
    Language: C++
    Result: Wrong_Answer
****************************************************************/
 
#include<cstdio>
#include<cstring>
typedef long long ll;
const int N=1000010;
int n,i;ll p,fac[N],F[N];
ll power(ll t,ll k){ll f=1;for(;k;k>>=1,t=(t*t)%p)k&1?f=(f*t)%p:1;return f;}
ll solve(int x){
    if(F[x]!=-1)return F[x];int d=1;for(;d<<1<x+1;d<<=1);d--,x-d>d+1>>1?1:d>>=1;
    return F[x]=solve(d)*solve(x-1-d)%p*fac[x-1]%p*power(fac[d],p-2)%p*power(fac[x-1-d],p-2)%p;
}int main(){memset(F,-1,sizeof(F));
    for(scanf("%d%lld",&n,&p),fac[1]=1,i=2;i<=n;i++)fac[i]=fac[i-1]*i%p;
    F[1]=1,F[2]=1,F[3]=2,F[4]=3,F[5]=8,F[6]=20,F[7]=80;printf("%lld",solve(n));
}
谁能帮我找出哪里错了...
  评论这张
 
阅读(49)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018