제출 #875356

#제출 시각아이디문제언어결과실행 시간메모리
875356matu캥거루 (CEOI16_kangaroo)C++14
0 / 100
1 ms604 KiB
#include <bits/stdc++.h> using namespace std; const int N = 201, mod = 1e9 + 7; ifstream fin("kangaroo.in"); ofstream fout("kangaroo.out"); #define cin fin #define cout fout struct Mint { int val; Mint(int x = 0) { val = x % mod; } Mint(long long x) { val = x % mod; } Mint operator+(Mint oth) { return val + oth.val; } Mint operator*(Mint oth) { return 1LL * val * oth.val; } Mint operator-(Mint oth) { return val - oth.val + mod; } Mint fp(Mint a, long long n){ Mint p = 1; while(n){ if(n & 1){ p = p * a; } a = a * a; n /= 2; } return p; } Mint operator/(Mint oth){ Mint invers = fp(oth, mod - 2); return 1LL * val * invers.val; } friend ostream& operator << (ostream& os, const Mint& lol){ os << lol.val; return os; } }; Mint dp[N][N][2]; int n, x, y; int main(){ cin.tie(0)->sync_with_stdio(0); cin >> n >> x >> y; dp[1][x][0] = dp[1][x][1] = 1; for(int i = 2; i < n; i++){ for(int j = 1; j <= n; j++){ if(j == x || j == y) continue; for(int k = 1; k <= n; k++){ if(k == j || k == y) continue; if(j < k){ dp[i][j][0] = dp[i][j][0] + dp[i - 1][k][1]; }else{ dp[i][j][1] = dp[i][j][1] + dp[i - 1][k][0]; } } } } for(int i = 1; i <= n; i++){ if(i == y) continue; if(i < y){ dp[n][y][1] = dp[n][y][1] + dp[n - 1][i][0]; }else{ dp[n][y][0] = dp[n][y][0] + dp[n - 1][i][1]; } } cout << dp[n][y][0] + dp[n][y][1]; } // dp[i][j] = in cate moduri pot sa pun eu astea astfel incat sa se termine cu cu al k lea element lol // 2 .. 3 // n - 2 // dp[i][j componente][A primu element][B, ultimul] // dp[i][j] = pui o singura componenta // lipesti pe i la o componenta // unesti 2 compnonente, cu i la mijloc // dp[i][j][nr] = // dp[i][x] = in cate moduri poti sa pui numerele astfel incat // dp[i][x][1/0] = daca eu iau // dp[1][2][0][1] = 1; // dp[2][1][0] = dp[i - 1][]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...