首页 > 代码库 > BZOJ 1925 地精部落（DP）
BZOJ 1925 地精部落（DP）
题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1925
题意：求1到n个所有排列中有多少种满足高低交错。
思路：f[n][k]表示n个数，最后一个为k且最后两个递增，g[n][k]表示n个数最后一个数为k且最后两个递减。对于f[n][k]，若我们将每个数x换为n+1-x，则就成了g[n][n+1-k]，因此有：f[n][k]=g[n][n+1-k]。那么可得：
由于对称性，我们计算出：
那么最后的答案就是2ans。
i64 f[2][N];int n,p;i64 cal(){ if(n==1) return 1%p; if(n==2) return 2%p; f[0][1]=0; f[0][2]=1; int pre=0,cur=1,i,j; for(i=3;i<=n;i++) { for(j=1;j<=i;j++) { f[cur][j]=f[pre][i-j+1]+f[cur][j-1]; f[cur][j]%=p; } swap(cur,pre); } i64 ans=0; FOR1(i,n) ans=(ans+f[pre][i])%p; return ans*2%p;}int main(){ RD(n,p); PR(cal());}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。