제출 #1187652

#제출 시각아이디문제언어결과실행 시간메모리
1187652peteza캥거루 (CEOI16_kangaroo)C++20
100 / 100
24 ms15944 KiB
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;

int n, sf, st, psd;
int dp[2005][2005]; //filled 1-i with j components

int main() {
    psd = 0;
    cin >> n >> sf >> st;
    dp[0][0] = 1;
    for(int i=1;i<=n;i++) {
        if(i == sf || i == st) {
            for(int k=1;k<=n;k++) dp[i][k] = dp[i-1][k];
            for(int k=0;k<=n;k++) {
                dp[i][k+1] += dp[i-1][k];
                if(dp[i][k+1] >= mod) dp[i][k+1] -= mod;
            }
            psd++;
        } else {
            for(int k=0;k<=n;k++) { //make new compo
                dp[i][k+1] += 1ll * dp[i-1][k] * max(0, k+1 - psd) % mod;
                if(dp[i][k+1] >= mod) dp[i][k+1] -= mod;
            }
            for(int k=2;k<=n;k++) { //merge existing compo
                dp[i][k-1] += 1ll * dp[i-1][k] * (k-1) % mod;
                if(dp[i][k-1] >= mod) dp[i][k-1] -= mod;
            }
        }
    }
    cout << dp[n][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...