제출 #985550

#제출 시각아이디문제언어결과실행 시간메모리
985550Blistering_Barnacles캥거루 (CEOI16_kangaroo)C++17
0 / 100
1 ms460 KiB
//Billions of bilious blue blistering barnacles in a thundering typhoon! //Yesterday is history, tomorrow is a mystery, today is a gift of God, which is why we call it the present. #include<bits/stdc++.h> using namespace std; void solve(){ const int mod = (int)1e9 + 7; auto add = [&](int x, int y) -> int{ return x + y - (x + y >= mod) * mod; }; auto mul = [&](int x, int y) -> int{ return (int64_t)x * y % mod; }; int n, s, e; cin >> n >> s >> e; vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0)); dp[1][1] = 1; for(int i = 2; i <= n; i++){ for(int j = 1; j <= i; j++){ if(i == s){ //either make a new component on the left or stick it to the leftmost component dp[i][j] = add(dp[i - 1][j - 1], dp[i - 1][j]); } else if(i == e){ //either make a new component on the right or stick it to the rightmost component dp[i][j] = add(dp[i - 1][j - 1], dp[i - 1][j]); } else{ //either make a new component or merge to components //num is the number of places to make a new component int num = j + 1 - (i > s) - (i > e); dp[i][j] = add(mul(num, dp[i - 1][j - 1]), mul(j, dp[i - 1][j + 1])); } } } cout << dp[n][1] << "\n"; } int main(){ ios::sync_with_stdio(0), cin.tie(0); int tt = 1; //cin >> tt; while(tt--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...