Submission #1695136

---

Source Code Expand

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
const int maxn=3000+10;
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c<'0' || c>'9'));
	if(c=='-') c=getchar(),f=-1;
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	ll f=1;
	while((c=getchar())!='-' && (c<'0' || c>'9'));
	if(c=='-') c=getchar(),f=-1;
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int mod=1e9+7;
int dp[maxn][maxn][2];
int main(){
	int n=read(),m=read();
	dp[0][0][1]=1;
	REP(i,1,n) dp[0][i][0]=1;
	REP(i,1,m)
		REP(j,0,n)
			REP(k,0,1){
				if(j){
					dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-1][k])%mod;
					dp[i][j][k|(j==1)]=(dp[i][j][k|(j==1)]+dp[i-1][j][k])%mod;
				}
				if(j<n){
					dp[i][j][k|(j==0)]=(dp[i][j][k|(j==0)]+dp[i-1][j+1][k])%mod;
					dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k])%mod;
				}
			}
	int ans=0;
	REP(i,0,n) ans=(ans+dp[m][i][1])%mod;
	printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result