Submission #875356

#	Time	Username	Problem	Language	Result	Execution time	Memory
875356		matu	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	1 ms	604 KiB

kangaroo

#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][]

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