제출 #1183713

#제출 시각아이디문제언어결과실행 시간메모리
1183713meicris캥거루 (CEOI16_kangaroo)C++17
6 / 100
1 ms324 KiB
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int N, cs, cf;
vector<vector<vector<int>>> dp;
int solve(int current, int prev, int mask) {
    if (mask == (1 << N) - 1) {
        return current == cf ? 1 : 0;
    }
    int &res = dp[current][prev][mask];
    if (res != -1) return res;
    res = 0;
    for (int next = 0; next < N; ++next) {
        if (mask & (1 << next)) continue;
        if ((prev < current && next < current) || (prev > current && next > current)) {
            res = (res + solve(next, current, mask | (1 << next))) % MOD;
        }
    }
    return res;
}
int main() {
    cin >> N >> cs >> cf;
    cs--; cf--;
    if (N > 20) {
        return 0;
    }
    dp.assign(N, vector<vector<int>>(N, vector<int>(1 << N, -1)));
    int ans = 0;
    for (int next = 0; next < N; ++next) {
        if (next == cs) continue;
        ans = (ans + solve(next, cs, (1 << cs) | (1 << next))) % MOD;
    }
    cout << ans << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...