Submission #1117735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117735		vjudge1	Kangaroo (CEOI16_kangaroo)	C++17	0 / 100	1 ms	336 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;
    function<void(long long, int, int )> func = [&](long long tmp, int ind, int dir) -> void {
        if (ind == V) {
            memo[tmp] = (tmp == 0);
            return;
        }
        bool ch = (memo.find(tmp) == memo.end());
        if (dir != 0) {
            bool as = false;
            for (int i = ind + 1;i < N;i ++) if ((tmp & (1LL << i)) > 0) {
                as = true;
                break;
            }
            if (!as) {
                if (memo.find(tmp) == memo.end()) memo[tmp] = 0;
            } else if (ch == true) {
                for (int i = ind + 1;i < N;i ++) if ((tmp & (1LL << i)) > 0) {
                    func ((tmp ^ (1LL << i)), i, 0);
                    memo[tmp] = (memo[(tmp ^ (1LL << i))] + memo[tmp]) % mod;
                }
            }
        }
        if (dir != 1) {
            bool as = false;
            for (int i = ind - 1;i >= 0;i --) if ((tmp & (1LL << i)) > 0) {
                as = true;
                break;
            }
            if (!as) {
                if (memo.find(tmp) == memo.end()) memo[tmp] = 0;
            } else if (ch == true) {
                for (int i = ind - 1;i >= 0;i --) if ((tmp & (1LL << i)) > 0) {
                    func ((tmp ^ (1LL << i)), i, 1);
                    memo[tmp] = (memo[(tmp ^ (1LL << i))] + memo[tmp]) % mod;
                }
            }
        }
    };
    func (((1LL << N) - 1) ^ (1LL<< U), U, -1);

    // cout << (((1 << N) - 1) ^ (1 << U)) << "\n";
    cout << memo[((1LL << N) - 1) ^ (1LL << U)] << "\n";
    // for (auto v : memo) {
    //     cout << v.first << " " << v.second << "\n";
    // }
}

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