Submission #1319188

---

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
using namespace std;
typedef long long LL;
const int N=3010;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
int f[N][2],g[N][2];
const int mod=1e9+7;
inline void inc(int &x,int y) { (x+=y)<mod?0:x-=mod; }
int main()
{
	int n=gi(),m=gi(),i,j,ans=0;
	for (i=0;i<=n;i++) f[i][!i]=1;
	while (m--) {
		for (i=0;i<=n;i++)
			for (j=0;j<2;j++) if (f[i][j]) {
					if (i) {
						inc(g[i-1][ j | !(i-1) ],f[i][j]);
						inc(g[i][ j | !(i-1) ],f[i][j]);
					}
					if (i<n) {
						inc(g[i+1][j],f[i][j]);
						inc(g[i][j],f[i][j]);
					}
				}
		for (i=0;i<=n;i++) f[i][0]=g[i][0],f[i][1]=g[i][1],g[i][0]=g[i][1]=0;
	}
	for (i=0;i<=n;i++) inc(ans,f[i][1]);
	printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result