제출 #351089

#제출 시각아이디문제언어결과실행 시간메모리
351089doowey캥거루 (CEOI16_kangaroo)C++14
51 / 100
1790 ms67680 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 202;
const int MOD = (int)1e9 + 7;
int dp[N][N][N][2];

void add(int &a, int b){
    a += b;
    if(a >= MOD) a -= MOD;
}

int main(){
    fastIO;
    int n, a, b;
    cin >> n >> a >> b;
    a -- ;
    b -- ;
    dp[2][0][1][1]=1;
    dp[2][1][0][0]=1;
    for(int len = 3; len <= n; len ++ ){
        for(int x = 0; x < len; x ++ ){
            for(int y = 0; y < len; y ++ ){
                if(x == y) continue;
                // compute q = 1
                for(int nx = 0; nx < x; nx ++ ){
                    add(dp[len][x][y][0],dp[len-1][nx][y-(y>x)][1]);
                }
                for(int nx = x + 1; nx < len; nx ++ ){
                    add(dp[len][x][y][1],dp[len-1][nx-1][y-(y>x)][0]);
                }
            }
        }
    }
    cout << (dp[n][a][b][0] + dp[n][a][b][1]) % MOD;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...