[SDOI2010]地精部落

Linker

做法：DP+组合数

首先我们定义(dp[i])为长度为i时的方案数。

不难想到，如果要满足每一个点都满足为山峰或者山谷的话，肯定是曲折的。（及若山谷为0，山峰为1，肯定是(010101010101cdots) 或者 (101010101010cdots)）

我们把这一个长度为n分成两个部分，设左边的长度为j，则右边的长度为i-j

发现这样不太好转移，于是我们把dp的状态再定义严格一点。

我们定义(dp[i])表示长度为i，且第一个严格为山峰的方案数。

那么我们此时此刻，左边的开头与右边的开头就都是山峰了。

由上面的(01)串可得，我们的左边最后一个也得是山峰，也就是说，我们左边的长度得是奇数

最后一个问题：如何保证左边最后一个与右边第一个一定为山峰？

我们把中间放上了一个最小值不就好了吗？

因此我们得到dp转移方程

(dp[i] = sum_{j=1}^{i-1} dp[j] * dp[i-1-j]*C_{i-1}^{j}(j\%2==1))

然后进行dp就好了。

对于山谷，与山峰的情况是完全一样的，因此我们直接*2即可

Code:

#include<bits/stdc++.h>
#define re register
#define rep(i,a,b) for(re int i=a,i##end=b; i<=i##end; i++)
#define drep(i,a,b) for(re int i=a,i##end=b; i>=i##end; i--)
#define repp(i,a,b) for(re int i=a,i##end=b; i<i##end; i++)
#define drepp(i,a,b) for(re int i=a,i##end=b; i>i##end; i--)
#define Erep(i,x) for(re int i=head[x]; i; i=Edge[i].nxt)
#define lowbit(x) ((x)&-(x))
#define ms(x,a) memset(x,a,sizeof x)
#define debug(x) cerr<<#x<<" = "<<x<<endl
#define CM cerr<<(&S2-&S1)/1024./1024.<<"MB"<<endl
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define coint const int
#define coll const ll
typedef long long ll;
using namespace std;
template<class T>inline T rd(){
	static char ch;static bool neg;static T x;
	for(neg=0, ch=0; ch>'9'||ch<'0'; neg|=(ch=='-'),ch=getchar());
	for(x=0; ch<='9'&&ch>='0'; x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar());
	return neg?-x:x;
}
template<class T>inline T Max(const T &x, const T &y) { return x>y?x:y; }
template<class T>inline T Min(const T &x, const T &y) { return x<y?x:y; }

bool S1;

int n,p;

struct P100{
	static coint N=4200+5;
	int dp[N]; // dp[i] -> 长度为i,符合条件 且 严格定义第一个为山峰(山谷同理)的方案数
	int C[N][N];
	inline void Upd(int &x, coint y){
		x+=y; x-=(x>=p?p:0); return;
	}
	inline void solve(){
		rep(i,0,N-5){
			C[i][i]=C[i][0]=1;
			repp(j,1,i) Upd(C[i][j],C[i-1][j]+C[i-1][j-1]);
		}
		dp[0]=dp[1]=1;
		rep(i,2,n){
			repp(j,1,i) if(j&1){ // 保证中间'1'的两边都是山峰
				dp[i]=(dp[i]+1ll*dp[j]*dp[i-1-j]%p*C[i-1][j]%p)%p;
			}
		}
		Upd(dp[n],dp[n]);
		printf("%d
",dp[n]);
		return;
	}
}p100;

bool S2;

int main(){
//	CM;
//	freopen("goblin.in","r",stdin);
//	freopen("goblin.out","w",stdout);
	n=rd<int>(),p=rd<int>();
	if(n<=10) return p20.solve(),0;
	if(n<=18) return p40.solve(),0;
	p100.solve();
//	fclose(stdin); fclose(stdout);
	return 0;
}