제출 #783092

#제출 시각아이디문제언어결과실행 시간메모리
783092minhcool캥거루 (CEOI16_kangaroo)C++17
6 / 100
1 ms852 KiB
#define local #ifndef local #include "" #endif #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; #define int long long #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 2e3 + 5; const int oo = 1e18 + 7, mod = 1e9 + 7; mt19937 rng(1); int rnd(int l, int r){ int temp = rng() % (r - l + 1); return abs(temp) + l; } int n, st, en; int f[N][N][2], g[N][N][2], pref[N][N][2]; //dp[N][N][N][2]; void add(int &a, int b){ a = (a + b) % mod; } #ifdef local void process(){ cin >> n >> st >> en; if(n <= 10){ g[1][2][0] = g[2][1][1] = 1; for(int num = 3; num <= n; num++){ for(int st_ind = 1; st_ind <= num; st_ind++){ for(int en_ind = 1; en_ind <= num; en_ind++){ f[st_ind][en_ind][0] = g[st_ind][en_ind][0]; f[st_ind][en_ind][1] = g[st_ind][en_ind][1]; g[st_ind][en_ind][0] = g[st_ind][en_ind][1] = 0; } } for(int st_ind = 1; st_ind <= n; st_ind++){ for(int en_ind = 1; en_ind <= n; en_ind++){ pref[st_ind][en_ind][0] = pref[st_ind][en_ind - 1][0]; add(pref[st_ind][en_ind][0], f[st_ind][en_ind][0]); pref[st_ind][en_ind][1] = pref[st_ind][en_ind - 1][1]; add(pref[st_ind][en_ind][1], f[st_ind][en_ind][1]); } } for(int st_ind = 1; st_ind <= num; st_ind++){ for(int en_ind = 1; en_ind <= num; en_ind++){ if(st_ind == en_ind) continue; int temp = st_ind - (st_ind > en_ind); g[st_ind][en_ind][0] = pref[temp][en_ind - 1][1]; g[st_ind][en_ind][1] = (pref[temp][num - 1][0] - pref[temp][en_ind - 1][0] + mod) % mod; /* for(int lst = 1; lst < en_ind; lst++){ if(lst == st_ind) continue; // we are deleting en_ind add(dp[num][st_ind][en_ind][0], dp[num - 1][st_ind - (st_ind > en_ind)][lst][1]); }*/ /* for(int lst = en_ind + 1; lst <= num; lst++){ if(lst == st_ind) continue; // we are deleting en_ind add(dp[num][st_ind][en_ind][1], dp[num - 1][st_ind - (st_ind > en_ind)][lst - 1][0]); }*/ } } } cout << (g[st][en][0] + g[st][en][1]) % mod << "\n"; return; } g[1][2][0] = g[2][1][1] = 1; for(int num = 3; num <= n; num++){ for(int st_ind = 1; st_ind <= num; st_ind++){ if(st_ind != 1 && st_ind != (num - 1)) continue; for(int en_ind = 1; en_ind <= num; en_ind++){ f[st_ind][en_ind][0] = g[st_ind][en_ind][0]; f[st_ind][en_ind][1] = g[st_ind][en_ind][1]; g[st_ind][en_ind][0] = g[st_ind][en_ind][1] = 0; } } for(int st_ind = 1; st_ind <= num; st_ind++){ if(st_ind != 1 && st_ind != (num - 1)) continue; for(int en_ind = 1; en_ind <= num; en_ind++){ pref[st_ind][en_ind][0] = pref[st_ind][en_ind - 1][0]; add(pref[st_ind][en_ind][0], f[st_ind][en_ind][0]); pref[st_ind][en_ind][1] = pref[st_ind][en_ind - 1][1]; add(pref[st_ind][en_ind][1], f[st_ind][en_ind][1]); } } for(int st_ind = 1; st_ind <= num; st_ind++){ if(st_ind >= 2 && st_ind < num) continue; for(int en_ind = 1; en_ind <= num; en_ind++){ if(st_ind == en_ind) continue; int temp = st_ind - (st_ind > en_ind); g[st_ind][en_ind][0] = pref[temp][en_ind - 1][1]; g[st_ind][en_ind][1] = (pref[temp][num - 1][0] - pref[temp][en_ind - 1][0] + mod) % mod; /* for(int lst = 1; lst < en_ind; lst++){ if(lst == st_ind) continue; // we are deleting en_ind add(dp[num][st_ind][en_ind][0], dp[num - 1][st_ind - (st_ind > en_ind)][lst][1]); }*/ /* for(int lst = en_ind + 1; lst <= num; lst++){ if(lst == st_ind) continue; // we are deleting en_ind add(dp[num][st_ind][en_ind][1], dp[num - 1][st_ind - (st_ind > en_ind)][lst - 1][0]); }*/ //cout << num << " " << st_ind << " " << en_ind << " " << (g[st_ind][en_ind][0] + g[st_ind][en_ind][1]) % mod << "\n"; } } } if(st < en) cout << (g[1][en - st + 1][0] + g[1][en - st + 1][1]) % mod << "\n"; else cout << (g[n][n - (st - en)][0] + g[n][n - (st - en)][1]) % mod << "\n"; //cout << (double)clock() / (double)CLOCKS_PER_SEC << "\n"; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen("abc.inp", "r", stdin); //freopen("abc.out", "w", stdout); process(); } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...