Submission #875369

#	Time	Username	Problem	Language	Result	Execution time	Memory
875369		matu	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	14 ms	16216 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7, N = 2e3 + 1;
// ifstream fin("1.in");
// ofstream fout("1.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;
    }
    void operator += (Mint oth){
        val = (1LL * val + oth.val) % mod;
        
    }
};
Mint dp[N][N];
int n, x ,y;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> x >> y;
    
    dp[1][1] = 1;
    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= i; j++){
            
            if(i == x){
                dp[i][j + 1] += dp[i - 1][j];
                dp[i][j] += dp[i - 1][j];
            }
            else if(i == y){
                dp[i][j + 1] += dp[i - 1][j];
                dp[i][j] += dp[i - 1][j];
            }else{

                dp[i][j + 1] += dp[i - 1][j] * (j + 1 - (i > x) - (i > y));
                dp[i][j - 1] += dp[i - 1][j] * (j - 1);
            }
        }
    }

    cout << dp[n][1];

   
}

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