[SDOI2010] 地精部落

题意

问 1-n 的排列中,峰谷交替的排列有多少个,答案对 P 取模。

峰谷交替:即对于一个排列中的任意一个数 ,满足以下条件之一:

.

分析

首先有一个简单 DP,定义 表示 个数,其中第一个数是从小到达中排第 的数,且比第二个数(小 0/ 大 1)时的方案数。

初始化 ,目标 .

观察方程,然后前缀和优化即可

定义 .

然后你的 就不需要了……

初始化 ,目标 .

复杂度 .

代码

#include<cstdio>
using namespace std;
const int N=4205;
int n,P,ans,p[N][N][2];
int main(){scanf("%d%d",&n,&P);
    p[1][1][0]=p[1][1][1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            p[i][j][1]=((long long)p[i][j-1][1]+p[i-1][j-1][0])%P;
            p[i][j][0]=((long long)p[i][j-1][0]+p[i-1][i-1][1]-p[i-1][j-1][1])%P;
        }
    }
    ans=(((long long)p[n][n][0]+p[n][n][1])%P+P)%P;
    printf("%d",ans);
    return 0;
}

  转载请注明: Sshwy's Blog [SDOI2010] 地精部落

 上一篇
[LuoguP1357] 花园 [LuoguP1357] 花园
暴力 DP首先有一个暴力状压 DP, 表示以第 个花盆结尾,后 个花盆的二进制状态为 (1 为 C,0 为 P)时的方案数 对于环形的处理,我们让两个相同状态作为 DP 的初始和结尾即可.具体的说,初始
2018.12.17
下一篇 
博弈论 博弈论
摘要 博奕论,一门高深的学问。 2019.6.15 编入精选文章。 dls 讲博弈论:“你掉线,我随意” 博弈的分类博弈大体分为平等博弈和不平等博弈。平等博弈指双方的决策集等价,不平等博弈则指双方决策集不等价。 常见的平等博弈则则是 I
2018.12.13
  目录