Submission #2532202

---

Source Code Expand

#include<bits/stdc++.h>
#define MD 1000000007
#define MAXN 4005
using namespace std;
int read(){
	char c;int x;while(c=getchar(),c<'0'||c>'9');x=c-'0';
	while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
}
int n,m,f[MAXN][MAXN][2],ans;
int main()
{
	n=read();m=read();
	f[0][0][1]=1;
	for(int i=1;i<=n;i++) f[0][i][0]=1;
	for(int i=0;i<=m-1;i++)
	 for(int j=0;j<=n;j++)
	  for(int k=0;k<=1;k++){
	  	if(j) f[i+1][j][k|(j==1)]=(f[i+1][j][k|(j==1)]+f[i][j][k])%MD;
		if(j) f[i+1][j-1][k|(j==1)]=(f[i+1][j-1][k|(j==1)]+f[i][j][k])%MD;
		if(n-j) f[i+1][j][k]=(f[i+1][j][k]+f[i][j][k])%MD;
		if(n-j) f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k])%MD;
	  }
	for(int i=0;i<=n;i++) ans=(ans+f[m][i][1])%MD;
	printf("%d",ans);
	return 0;
}

Submission Info

Judge Result