@liu_runda
【题目描述】
出个题就好了.这就是出题人没有写题目背景的原因.
你在平面直角坐标系上.
你一开始位于(0,0).
每次可以在上/下/左/右四个方向中选一个走一步.
即:从(x,y)走到(x,y+1),(x,y-1),(x-1,y),(x+1,y)四个位置中的其中一个.
允许你走的步数已经确定为n.现在你想走n步之后回到(0,0).但这太简单了.你希望知道有多少种不同的方案能够使你在n步之后回到(0,0).当且仅当两种方案至少有一步走的方向不同,这两种方案被认为是不同的.
答案可能很大所以只需要输出答案对10^9+7取模后的结果.(10^9+7=1000000007,1和7之间有8个0)
这还是太简单了,所以你给能够到达的格点加上了一些限制.一共有三种限制,加上没有限制的情况,一共有四种情况,用0,1,2,3标号:
- 0.没有任何限制,可以到达坐标系上所有的点,即能到达的点集为{(x,y)|x,y为整数}
- 只允许到达x轴非负半轴上的点.即能到达的点集为{(x,y)|x为非负数,y=0}
- 只允许到达坐标轴上的点.即能到达的点集为{(x,y)|x=0或y=0}
- 只允许到达x轴非负半轴上的点,y轴非负半轴上的点以及第1象限的点.即能到达的点集为{(x,y)|x>=0,y>=0}
【输入格式】
一行两个整数(空格隔开)n和typ,分别表示你必须恰好走的步数和限制的种类.typ的含义见【题目描述】.
【输出格式】
一行一个整数ans,表示不同的方案数对10^9+7取模后的结果.
【样例输入0】
100 0
【样例输出0】
383726909
【样例输入1】
100 1
【样例输出1】
265470434
【样例输入2】
100 2
【样例输出2】
376611634
【样例输入3】
100 3
【样例输出3】
627595255
【数据范围】
10%的数据,typ=0,n<=100
10%的数据,typ=0,n<=1000
5%的数据, typ=0,n<=100000
10%的数据,typ=1,n<=100
10%的数据,typ=1,n<=1000
5%的数据, typ=1,n<=100000
10%的数据,typ=2,n<=100
15%的数据,typ=2,n<=1000
10%的数据,typ=3,n<=100
10%的数据,typ=3,n<=1000
5%的数据, typ=3,n<=100000
以上11部分数据没有交集.
100%的数据,保证n为偶数,2<=n<=100000,0<=typ<=3.
分析：
考场上的dp做法详见hu测10.5
正解：
四合一Catalan应用
first.typ=1
裸的Catalan
模拟出入栈
second.typ=0
对于typ=0的数据
枚举横向移动了多少步
横向移动i步时(为了存在合法解,i必须是偶数)
方案数为C(n,i)*C(i,i/2)*C((n-i),(n-i)/2)
横向选择i步移动，i步中有一半正向移动，剩下纵向的n-i步中，一半正向移动
third.typ=2
f[i]表示走了i步回到原点的方案数
（中途可能回到过原点多次）
枚举第一次回到原点时走过的步数j(为了存在合法解,j为偶数)
则此时方案数为f[i-j]*catalan(j/2-1)
解释：
第j步第一次回到远点，之后可能有多次再次回原点（f[i-j]），
在计算这j步时，我们必须保证j步中不回原点，所以catalan(j/2-1)
这个-1就是保证栈不为空
（在我们眼里，移动就像出入栈）
最后答案需要*4
复杂度为O(n^2)所以最大范围只出到1000
fourth.typ=3
枚举横向移动了多少步
横向移动i步时(为了存在合法解,i必须是偶数)
方案数为C(n,i)*catalan(i/2)*catalan((n-i)/2)
选择n步中的i步横向移动，其中一半的步数正向移动，
剩下纵向移动的步数中，也有一半的步数正向移动
Catalan保证是在第一象限内移动（任意前缀入栈不少于出栈）
//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
const ll mod=1000000007;
const int N=200010;
int n,typ;
ll inv[N],jc[N],f[1010];
ll KSM(ll a,int b)
{
a%=mod;
ll t=1;
while (b)
{
if (b&1)
t=(t%mod*a%mod)%mod;
b>>=1;
a=(a%mod*a%mod)%mod;
}
return t%mod;
}
void cl()
{
jc[0]=1; jc[1]=1;
for (int i=2;i<N;i++) jc[i]=(jc[i-1]%mod*(ll)i%mod)%mod;
inv[0]=1; inv[1]=1;
for (int i=2;i<N;i++) inv[i]=((mod-mod/i)%mod*inv[mod%i]%mod)%mod;
for (int i=1;i<N;i++) inv[i]=(inv[i]*(ll)inv[i-1])%mod; //阶乘的逆元
}
ll C(int n,int m)
{
if (n<m) return 0;
if (m==0) return 1;
return (jc[n]%mod*inv[m]%mod*inv[n-m]%mod)%mod;
}
ll Catalan(int x) //公式求法
{
return C(2*x,x)%mod*KSM((ll)(x+1),mod-2)%mod; //费马小定理求逆元
}
int main()
{
freopen("problem.in","r",stdin);
freopen("problem.out","w",stdout);
scanf("%d%d",&n,&typ);
cl();
if (typ==1)
{
printf("%lld",Catalan(n/2));
}
else if (typ==0)
{
ll ans=0;
for (int i=0;i<=n;i+=2) //为了能回到原点，枚举的横向步数一定是偶数
ans=(ans+C(n,i)%mod*C(i,i/2)%mod*C(n-i,(n-i)/2)%mod)%mod;
printf("%lld",ans%mod);
}
else if (typ==2)
{
n/=2; //方便dp
f[0]=1;
f[1]=4;
for (int i=2;i<=n;i++) //枚举总步数
for (int j=1;j<=i;j++) //枚举第一次到达原点的步数
f[i]=(f[i]%mod+f[i-j]%mod*4*Catalan(j-1)%mod)%mod;
printf("%lld",f[n]%mod);
}
else
{
ll ans=0;
for (int i=0;i<=n;i+=2)
ans=(ans+C(n,i)%mod*Catalan(i/2)%mod*Catalan((n-i)/2)%mod)%mod;
printf("%lld",ans);
}
return 0;
}