Submission #81741

#TimeUsernameProblemLanguageResultExecution timeMemory
81741SaboonKangaroo (CEOI16_kangaroo)C++14
6 / 100
11 ms4700 KiB
#include <iostream>
#include <sstream>
#include <queue>
#include <stack>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <iomanip>
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 200 + 37;
const int mod = 1e9 + 7;

int dp[maxn][maxn][maxn][3];

ll fen[maxn + 100][maxn][3];

ll get (int idx, int w, int d) {
    if (idx < 0)
        return 0;
    ll ret = 0;
    for (; idx; idx -= idx & -idx)
        ret = (ret + fen[idx][w][d]) % mod;
    return ret;
}

ll sum (int l, int r, int w, int d) {
    return get (r - 1, w, d) - get (l - 1, w, d);
}

void change (int idx, ll val, int w, bool d) {
    for (; idx < maxn; idx += idx & -idx)
        fen[idx][w][d] = (fen[idx][w][d] + val) % mod;
}

int main() {
    ios_base::sync_with_stdio(false);
    int n, s, t;
    cin >> n >> s >> t;
    dp[2][1][2][1] = 1;
    dp[2][2][1][0] = 1;
    change (1, 1, 2, 1);
    change (2, 1, 1, 0);
    for (int i = 3; i <= n; i++) {
        for (int st = 1; st <= i; st ++) {
            for (int en = 1; en <= i; en ++) {
                if (st != en) {
                    if (en > st) {
                        dp[i][st][en][1] = sum (st, i, en - 1, 0);
//                      dp[i][st][en][1] = (dp[i][st][en][1] + par[i - 1][i - 1][en - 1][0] - par[i - 1][st - 1][en - 1][0] + mod + mod) % mod;
                        dp[i][st][en][0] = sum (0, st, en - 1, 1);
//                      dp[i][st][en][0] = (dp[i][st][en][0] + par[i - 1][st - 1][en - 1][1]) % mod;
                    }
                    else {
                        dp[i][st][en][1] = sum (st, i, en, 0);
//                      dp[i][st][en][1] = (dp[i][st][en][1] + par[i - 1][i - 1][en][0] - par[i - 1][st - 1][en][0] + mod + mod) % mod;
                        dp[i][st][en][0] = sum (0, st, en, 1);
//                      dp[i][st][en][0] = (dp[i][st][en][0] + par[i - 1][st - 1][en][1] + mod) % mod;
                    }
//                  cout << i << " " << st << " " << en << " right " << dp[i][st][en][1] << endl;
//                  cout << i << " " << st << " " << en << " left " << dp[i][st][en][0] << endl;
                }
            }
        }
        memset (fen, 0, sizeof fen);
        for (int st = 1; st <= i; st ++) {
            for (int en = 1; en <= i; en ++) {
                change (st, dp[i][st][en][1], en, 1);
                change (st, dp[i][st][en][0], en, 0);
            }
        }
    }
    cout << (dp[n][s][t][1] + dp[n][s][t][0]) % mod << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...