P2467
Aryper
·
·
个人记录
[SDOI2010]地精部落
感觉并不是很好做的计数 DP，想了很长时间没有什么很简单的方法。。。
法一：定义 f(i,j) 表示序列中有 i 个数，第一个数为 j，且第一个数为山峰的方案数。
那么我们知道，对于 f(i,j)，它其实还表示以 i-j+1 为高度的山谷作为开头，序列中同样有 i 个数，此时的序列方案数。原因就是我们可以将整个序列翻转（盗图）：
那么我们可以得知最后的答案就是 \sum_{i=1}^n 2f(n,i)。
那么转移怎么办：
f(i,j)=f(i-1,i-j+1)+f(i,j-1)
这里的 f(i-1,i-j+1) 就表示以 j-1 为开头的山谷，然后再开头拼上 j。这里的 f(i,j-1) 就表示我们不以 j-1 为开头谷底时的情况（原理是交换 f(i,j-1) 中的 j-1 与 j 的位置，序列仍然合法，但是 j 处在开头且为山峰，并且紧接着它后面的山谷不会是 j-1）。
于是这样就可以不重不漏的统计了。不过并没有那么的直觉。
时间复杂度 O(n^2)。
法二：一维的想法。稍微直觉一些。
那么 $f(i)=\sum_{j\in[1,i],j=2k+1}f(j-1)f(i-j)C_{i-1}^{j-1}$。
这里的意思就是说，枚举 $i-1$ 个数中的 $i$ 个位置，考虑把 $i$ 插入其中。那么显然我们的 $i$ 必须是山峰。那么 $f(j-1)$ 就是左边的这一段，需要接上 $i$，也就是说，$f(j-1)$ 的序列中最后一个数必须是山谷，所以说 $j$ 必须为偶数。同样，我们还要乘上右边这一段 $f(i-j)$，上文已经说了，这个方案数完全可以转化为开头是山谷的方案数，所以可以接上 $i$。最后，我们左右两边的数会有交叉组合，所以从 $i-1$ 个数中挑出 $j-1$ 个数放入左边，所以最后要再乘上 $C_{i-1}^{j-1}$。
时间复杂度 $O(n^2)$。
代码（法一）：
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const ll N=4.2e3;
ll n,p,ans;
ll f[2][N+5];
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
return ret*f;
}
void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {
do{buf[++len]=x%10+48;x/=10;}while(x);
}
else {
putchar('-');
do{buf[++len]=-(x%10)+48;x/=10;}while(x);
}
while(len>=0) putchar(buf[len--]);
}
int main() {
n=read();p=read();
f[0][1]=0;f[0][2]=1;
for(ll i=3;i<=n;i++) {
for(ll j=1;j<=i;j++) {
f[i&1][j]=(f[(i-1)&1][i-j+1]+f[i&1][j-1])%p;
}
}
for(ll i=1;i<=n;i++) {
ans=(ans+f[n&1][i]+f[n&1][i])%p;
}
write(ans);
return 0;
}
```
代码（法二）：
```cpp
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=4.2e3;
ll n,p;
ll f[N+5],c[2][N+5];
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
return ret*f;
}
void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {
do{buf[++len]=x%10+48;x/=10;}while(x);
}
else {
putchar('-');
do{buf[++len]=-(x%10)+48;x/=10;}while(x);
}
while(len>=0) putchar(buf[len--]);
}
int main() {
n=read();p=read();
f[0]=1;c[0][0]=1;
for(ll i=1;i<=n;i++) {
for(ll j=1;j<=i;j++) {
if(j&1) f[i]=(f[i]+(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;
}
c[i&1][0]=c[(i-1)&1][0];
}
write(2ll*f[n]%p);
return 0;
}
```