Submission #443562

#	Time	Username	Problem	Language	Result	Execution time	Memory
443562		nafis_shifat	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	32 ms	31692 KiB

kangaroo

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=2e3+5;
const int inf=1e9;
const ll mod = 1e9 + 7;
int main() {

    int n,cf,cs;

    cin >> n >> cf >> cs;


    ll dp[n + 1][n + 1] = {};


    dp[1][1] = 1;
    int k = (1 == cs || 1 == cf);

    for(ll i = 2; i <= n; i++) {
        if(i == cf || i == cs) k++;
        for(ll j = 1; j <= i; j++) {
            if(i == cf || i == cs) {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
                continue;
            }
            dp[i][j] = (j - k) * dp[i - 1][j - 1]  % mod;
            dp[i][j] += j * dp[i - 1][j + 1] % mod;
            dp[i][j] %= mod;
        }
    }

    cout<<dp[n][1]<<endl;

}

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49