T1.
T2.
T3.
本来人家是简、单、题，硬生生被改成随单题。
T1、T2太难了，不在考虑范畴，直接看T3。
T3.
找规律、推式子、敲代码、得到部分分。
typ=1的时候，明显想到Catlan数，EZ。
typ=0的时候，是前几天的考题的简化版。
经WD大佬的指点，式子也可写为（C（2n,n））^2; 如下图，
每走一步由原来的（1,0）、（-1,0）、（0,1）、（0，-1）变为（1，-1）、（-1,1）、（1,1），（-1，-1） 这样就可以分别组合数并乘起来。
typ=2的时候，递推（想不到啊）
f[i]表示走了i步回到原点的方案数 中途可能回到过原点多次） ， 枚举第一次回到原点时走过的步数j(为了存在合法解,j为偶数) 则此时方案数为f[i-j]*catalan(j/2-1) 累加答案时要乘4（四个方向）。（看不懂看代码，就懂了）
typ=3的时候，枚举横向移动了多少步 ，各个方向步数就定了。
方案数为C(n,i)*catalan(i/2)*catalan((n-i)/2) （i为横向步数）
推荐一篇博客：
1 #include2 #define ll long long 3 #define RE register 4 using namespace std; 5 const int mod=1e9+7; 6 const int maxn=2000010; 7 ll n,typ; 8 ll inv[maxn],fac[maxn]; 9 ll fast_pow(ll x,ll b,ll p){10 ll s=1;11 while(b){12 if(b&1) s=s*x%p;13 x=x*x%p;14 b>>=1;15 }16 return s%p;17 }18 void init(){19 fac[0]=fac[1]=inv[0]=1;20 for(int i=2;i<=n;i++) fac[i]=fac[i-1]%mod*i%mod;21 inv[n]=fast_pow(fac[n],mod-2,mod);22 for(int i=n-1;i>=0;i--) 23 inv[i]=inv[i+1]*(i+1)%mod;24 }25 ll C(ll mm,ll nn){26 if(mm==0) return 1;27 if(mm>nn) return 0;28 return fac[nn]%mod*inv[mm]%mod*inv[nn-mm]%mod;29 }30 ll Cat(ll x){31 return (C(x,x*2)*(fac[x]*inv[x+1]%mod)%mod)%mod;32 }33 ll anss=0;34 ll f[1010];//f[i]表示走i*2步回到原点 ，也就是，最远距离 35 int main(){36 // freopen("in.txt","r",stdin);37 scanf("%lld%lld",&n,&typ);38 init();39 if(typ==0){40 ll a,b,c,d;//上，下，右，左41 for(a=0;a<=n/2;a++){42 b=a,c=(n-a*2)/2,d=c;43 ll ans=C(a,n)%mod*C(b,n-a)%mod*C(c,n-a-b)%mod;44 anss=(anss+ans)%mod;45 } 46 printf("%lld\n",(anss%mod+mod)%mod);47 return 0;48 }49 if(typ==1){50 ll ans=Cat(n/2);51 printf("%lld\n",(ans%mod+mod)%mod);52 return 0;53 }54 if(typ==2){55 ll m=n/2;56 f[0]=1;57 for(int i=1;i<=m;i++){58 for(int j=1;j<=i;j++)59 f[i]=(4*f[i-j]%mod*Cat(j-1)%mod+f[i]%mod)%mod;//为什么要j-1，是因为不计算原点，从1开始到的最远距离 60 }61 printf("%lld",f[m]%mod);62 return 0;63 }64 if(typ==3){65 ll ans=0;66 for(int i=0;i<=n;i+=2)67 ans=(ans+C(i,n)%mod*Cat(i/2)%mod*Cat((n-i)/2)%mod)%mod;68 printf("%lld",(ans%mod+mod)%mod);69 return 0;70 }71 }