题解 P2467 【[SDOI2010]地精部落】

~~可以算是优质题解？虽然我也是看了题解才完成的本题~~ 只用一维DP，没有那么复杂 - 首先发现一个性质：/\/\\....和\/\/的数量一样多 - 设f[i]表示1到i的排列中，首个下降的波动序列个数 - 转移：加入i，一定是放在山峰的位置，枚举在第j个位置，则$f[i]+=f[j-1]*f[i-j]*C[i-1][j-1]$ - 意思是在剩余的i-1个数中选j-1个放在左边，然后左右的数字分别离散话之后的方案就是f[j-1]、f[i-j] 代码很简单 ```cpp #include<iostream> using namespace std; const int N=4210; int C[2][N],f[N],P,n; int main() { cin>>n>>P;C[0][0]=C[1][0]=f[0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) { if(j&1) (f[i]+=1ll*f[j-1]*f[i-j]%P*C[(i-1)&1][j-1]%P)%=P; C[i&1][j]=(C[(i-1)&1][j]+C[(i-1)&1][j-1])%P; } cout<<2ll*f[n]%P<<endl; } Blog:https://www.cnblogs.com/xzyxzy ``` C要滚动因为要卡空间（BZOJ）