Submission #1117841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117841		vjudge1	Kangaroo (CEOI16_kangaroo)	C++17	6 / 100	2054 ms	72592 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    int N, U, V;
    cin >> N >> U >> V;
    -- U;
    -- V;
    map<long long, int> memo[N][3];
    function<int(long long, int, int )> func = [&](long long tmp, int ind, int dir) -> int {
        if (ind == V) {
            memo[ind][dir][tmp] = (tmp == 0);
            return (tmp == 0);
        }
        if (memo[ind][dir].find(tmp) != memo[ind][dir].end()) return memo[ind][dir][tmp];
        if (dir != 1) {
            bool as = false;
            for (int i = ind + 1;i < N;i ++) if ((tmp & (1LL << i)) > 0) {
                as = true;
                break;
            }
            if (!as) {
                if (memo[ind][dir].find(tmp) != memo[ind][dir].end()) memo[ind][dir][tmp] = 0;
            } else {
                for (int i = ind + 1;i < N;i ++) if ((tmp & (1LL << i)) > 0) {
                    if (memo[i][1].find((tmp ^ (1LL << i))) == memo[i][1].end()) {
                        memo[ind][dir][tmp] = (func ((tmp ^ (1LL << i)), i, 1) + memo[ind][dir][tmp]) % mod;
                    } else {
                        memo[ind][dir][tmp] = (memo[i][1][(tmp ^ (1LL << i))] + memo[ind][dir][tmp]) % mod;
                    }
                }
                // ans += memo[ind][dir][tmp];
            }
        }
        if (dir != 2) {
            bool as = false;
            for (int i = ind - 1;i >= 0;i --) if ((tmp & (1LL << i)) > 0) {
                as = true;
                break;
            }
            if (!as) {
                if (memo[ind][dir].find(tmp) != memo[ind][dir].end()) memo[ind][dir][tmp] = 0;
            } else {
                for (int i = ind - 1;i >= 0;i --) if ((tmp & (1LL << i)) > 0) {
                    if (memo[i][2].find((tmp ^ (1LL << i))) == memo[i][2].end()) {
                        memo[ind][dir][tmp] = (func ((tmp ^ (1LL << i)), i, 2) + memo[ind][dir][tmp]) % mod;
                    } else {
                        memo[ind][dir][tmp] = (memo[i][2][(tmp ^ (1LL << i))] + memo[ind][dir][tmp]) % mod;
                    }
                }
                // ans += memo[ind][dir][tmp];
            }
        }
        // memo[tmp] = (memo[tmp] + ans) % mod;
        return memo[ind][dir][tmp];
    };
    int answer = func (((1LL << N) - 1) ^ (1LL << U), U, 0);

    // cout << (((1 << N) - 1) ^ (1 << U)) << "\n";
    cout << answer << "\n";
}

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