1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
|
using namespace std; #define forl(i, l, r) for (int i = l; i <= r; i++) #define forr(i, r, l) for (int i = r; i >= l; i--) #define for1(i, n) for (int i = 1; i <= n; i++) #define fro1(i, n) for (int i = 1; i <= n; i++) #define for0(i, n) for (int i = 0; i < n; i++) #define fro0(i, n) for (int i = 0; i < n; i++) #define meminf(a) memset(a, inf, sizeof(a)) #define mem_1(a) memset(a, -1, sizeof(a)) #define mem0(a) memset(a, 0, sizeof(a)) #define memcp(a,b) memcpy(a,b,sizeof(b)) #define oper(type) bool operator <(const type y)const #define mp make_pair #define pu_b push_back #define pu_f push_front #define po_b pop_back #define po_f pop_front #define fi first #define se second #define whiel while #define retrun return typedef pair<long long, long long> pll; typedef vector<long long> vll; typedef pair<int, int> pii; typedef unsigned long long ull; typedef vector<int> vii; typedef double db; typedef long double ldb; typedef long long ll; typedef int itn; void (initializer_list<int*> li){for(auto ptr=li.begin();ptr!=li.end();ptr++)scanf("%d",*ptr);} void (initializer_list<ll*> li){for(auto ptr=li.begin();ptr!=li.end();ptr++)scanf("%lld",*ptr);} void (initializer_list<db*> li){for(auto ptr=li.begin();ptr!=li.end();ptr++)scanf("%lf",*ptr);} void out(initializer_list<int> li){auto ti=li.end();ti--;for(auto ptr=li.begin();ptr!=li.end();ptr++)printf("%d%c",*ptr,ptr==ti?'n':' ');} void out(initializer_list<ll> li){auto ti=li.end();ti--;for(auto ptr=li.begin();ptr!=li.end();ptr++)printf("%lld%c",*ptr,ptr==ti?'n':' ');} void out(initializer_list<db> li){auto ti=li.end();ti--;for(auto ptr=li.begin();ptr!=li.end();ptr++)printf("%f%c",*ptr,ptr==ti?'n':' ');} void out(int a,bool ln){printf("%d%c",a,ln?'n':' ');} void out(ll a,bool ln){printf("%lld%c",a,ln?'n':' ');} void out(db a,int digit,bool ln){printf("%.*f%c",digit,a,ln?'n':' ');} void out(ldb a,int digit,bool ln){printf("%.*Lf%c",digit,a,ln?'n':' ');} void out0(int a[],int n){for0(i,n)out(a[i],i==n-1);} void out1(int a[],int n){for1(i,n)out(a[i],i==n);} void out0(ll a[],int n){for0(i,n)out(a[i],i==n-1);} void out1(ll a[],int n){for1(i,n)out(a[i],i==n);} int (int &a,int &b,int &c,int &d){return scanf("%d%d%d%d",&a,&b,&c,&d);} int (int &a,int &b,int &c){return scanf("%d%d%d",&a,&b,&c);} int in(int &a,int &b){return scanf("%d%d",&a,&b);} int in(ll &a,ll &b,ll &c,ll &d){return scanf("%lld%lld%lld%lld",&a,&b,&c,&d);} int in(ll &a,ll &b,ll &c){return scanf("%lld%lld%lld",&a,&b,&c);} int in(ll &a,ll &b){return scanf("%lld%lld",&a,&b);} int in(ll &a){return scanf("%lld",&a);} int in(int &a){return scanf("%d",&a);} int in(char *s){return scanf("%s",s);} int in(char &c){return scanf("%c",&c);} int in(db &a){return scanf("%lf",&a);} int in(ldb &a){return scanf("%Lf",&a);} void in0(int a[],int n){for0(i,n)in(a[i]);} void in1(int a[],int n){for1(i,n)in(a[i]);} void in0(ll a[],int n){for0(i,n)in(a[i]);} void in1(ll a[],int n){for1(i,n)in(a[i]);} const db pi = acos(-1); const db eps = 1e-8; int sign(db a) {return a < -eps ? -1 : a > eps;} int db_cmp(db a, db b){ return sign(a-b);} const ll inf =0x3f3f3f3f; const ll mod = 1e9+7; const int M = 2.1e5; const int N = 2.1e3;
int dp[N][N],n; bool vis[N][N]; bool check(int i,int j){ if(j>=0&&j<=n&&(i-j)%2==0&&i+j<=2*n)retrun 1; else retrun 0; } int main() { in(n); for(int i=2*n-1;i>=0;i--){ for(int j=0;j<=min(n,i);j++){ bool flag=0; if(check(i+1,j-1)){ if(vis[i+1][j-1]==0)vis[i+1][j-1]=1,flag=1; dp[i][j]=(dp[i][j]+dp[i+1][j-1])%mod; } if(check(i+1,j+1)){ if(vis[i+1][j+1]==0&&flag==0)flag=1,vis[i+1][j+1]=1; dp[i][j]=(dp[i][j]+dp[i+1][j+1])%mod; } if(flag){ vis[i][j]=1,dp[i][j]=(dp[i][j]+1)%mod; } } } out(dp[0][0],1); return 0; }
|
近期评论