Submission #2543657

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long LL;
#define sqr(x) ((x)*(x))
#define mp make_pair
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
	int x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(int a){
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
	write(a); puts("");
}
const int N=3005,mod=1000000007;
int n,m,dp[N][N][2],ans;
inline void add(int &a,int b){
	a=a+b>=mod?a+b-mod:a+b;
}
int main(){
	n=read(); m=read();
	dp[0][0][0]=1;
	for(int i=1;i<=n;i++)dp[0][i][1]=1;
	for(int i=0;i<m;i++){	
		for(int j=0;j<=n;j++){
			for(int k=0;k<2;k++){
				if(j<n){add(dp[i+1][j+1][k],dp[i][j][k]); add(dp[i+1][j][k],dp[i][j][k]);}
				if(j){add(j==1?dp[i+1][j-1][0]:dp[i+1][j-1][k],dp[i][j][k]); add(j==1?dp[i+1][j][0]:dp[i+1][j][k],dp[i][j][k]);}
			}
			//cout<<i<<" "<<j<<" "<<dp[i][j][0]<<" "<<dp[i][j][1]<<endl;
		}
	}
	ans=dp[m][0][1];
	for(int i=0;i<=n;i++)add(ans,dp[m][i][0]);
	cout<<ans<<endl;
}

Submission Info

Judge Result