| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1289445 | namious | Kangaroo (CEOI16_kangaroo) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0) ,cin.tie(0),cout.tie(0);
const int maxn = 2e3+3 , mod = 1e9+7 , inf = 1e9+9;
int n,s,e;
int dp[maxn][2][maxn];
int pd[maxn][2][maxn];
int cnt[maxn][2];
int main(){
fast_io
dp[1][0][1] = 1 , dp[1][1][1];
for (int i = 2 ; i < maxn ; i++){
int sm = 0; for (int j = i-1; j > 0; j--) sm = (sm + dp[i-1][1][j]) % mod , dp[i][0][j] = sm;
sm = 0; for (int j = 2 ; j <= i ; j++) sm = (sm + dp[i-1][0][j-1]) % mod , dp[i][1][j] = sm;
}
cin >> n >> s >> e;
if (e < s) swap(s,e);
for (int ne = n; ne >= e; ne--){
for (int c = 0 ; c <= ne-e ; c++){
bool bt = (n-c-1)&1;
if (bt){
int a0 = cnt[c+1][1], a1 = (dp[n-c-1][0][s] + dp[n-c-1][1][s] - cnt[c+1][0] + mod) % mod;
cnt[c][0] = (cnt[c][0] + a0) % mod , cnt[c][1] = (cnt[c][1] + a1) % mod;
pd[ne][0][c] = a0 , pd[ne][1][c] = a1;
} else {
int a0 = cnt[c+1][1], a1 = (dp[n-c-1][0][s] + dp[n-c-1][1][s] - cnt[c+1][0] + mod) % mod;
cnt[c][0] = (cnt[c][0] + a0) % mod , cnt[c][1] = (cnt[c][1] + a1) % mod;
pd[ne][0][c] = a0 , pd[ne][1][c] = a1;
}
}
}
cout << (pd[e][0][0] + pd[e][1][0]) % mod << endl;
}