結果

問題 No.3055 Simple Chicken Game
ユーザー suisen
提出日時 2025-01-18 16:10:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,046 bytes
コンパイル時間 2,804 ms
コンパイル使用メモリ 112,548 KB
実行使用メモリ 20,864 KB
最終ジャッジ日時 2025-02-05 00:27:45
合計ジャッジ時間 11,289 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 RE * 12 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

// naive

#include <array>
#include <cassert>
#include <iostream>
#include <vector>
#include <atcoder/modint>

using mint = atcoder::modint;


#include <map>
#include <tuple>

struct S {
    double p;
    mint mp;
    S() : S(0) {}
    template <typename T>
    S(const T& x) : S(x, x) {}
    S(double p, mint mp) : p(p), mp(mp) {}
    friend S operator+(const S& a, const S& b) { return { a.p + b.p, a.mp + b.mp }; }
    friend S operator-(const S& a, const S& b) { return { a.p - b.p, a.mp - b.mp }; }
    friend S operator*(const S& a, const S& b) { return { a.p * b.p, a.mp * b.mp }; }
    friend S operator/(const S& a, const S& b) { return { a.p / b.p, a.mp / b.mp }; }
};

int main() {
    int n, mod;
    std::cin >> n >> mod;
    mint::set_mod(mod);
    assert(n <= 20);
    std::map<std::tuple<int, int, int, int>, int> ops;
    std::vector<std::map<std::tuple<int, int, int, int, int, int, int, int>, S>> memo(n);
    for (int i = n - 1; i >= 0; --i) {
        for (int a = 0; a <= i; ++a) for (int b = 0; a + b <= i; ++b) {
            int c = i - a - b;
            auto dfs = [&](auto dfs, int j, int x, int y, int z, int v) -> S {
                std::tuple key{ j, a, b, c, x, y, z, v };
                if (memo[i].count(key)) {
                    return memo[i][key];
                }
                if (j == n) {
                    if (v == 0) {
                        return memo[i][key] = y + z + a;
                    } else if (v == 1) {
                        return memo[i][key] = b;
                    } else {
                        return memo[i][key] = y + c;
                    }
                } else {
                    std::tuple op_key{ j, x + (v == 0), y + (v == 1), z + (v == 2) };
                    assert(ops.count(op_key));
                    int op = ops[op_key];
                    if (op == 0) {
                        return memo[i][key] = dfs(dfs, j + 1, x, y, z + 1, v);
                    } else if (op == 1) {
                        return memo[i][key] = (dfs(dfs, j + 1, x + 1, y, z, v) + dfs(dfs, j + 1, x, y + 1, z, v)) / 2;
                    } else {
                        return memo[i][key] = (dfs(dfs, j + 1, x, y, z + 1, v) + (dfs(dfs, j + 1, x + 1, y, z, v) + dfs(dfs, j + 1, x, y + 1, z, v)) / 2) / 2;
                    }
                }
                };
            S v0 = dfs(dfs, i + 1, a, b, c, 2);
            S v1 = (dfs(dfs, i + 1, a, b, c, 0) + dfs(dfs, i + 1, a, b, c, 1)) / 2;
            if (std::abs(v0.p - v1.p) < 1e-6 and v0.mp == v1.mp) {
                assert(a == c); // !
                ops[{i, a, b, c}] = 2;
            } else if (v0.p > v1.p) {
                assert(a < c); // !
                ops[{i, a, b, c}] = 1;
            } else {
                assert(a > c); // !
                ops[{i, a, b, c}] = 0;
            }
        }
    }
    std::vector<mint> R(n, 1);
    auto dfs = [&](auto dfs, int i, int x, int y, int z, mint p) -> void {
        if (i == n) return;
        std::tuple key{ i, x, y, z };
        int op = ops[{i, x, y, z}];
        if (op == 0) {
            R[i] += p * memo[i][{i + 1, x, y, z, x, y, z, 2}].mp;
            dfs(dfs, i + 1, x, y, z + 1, p);
        } else if (op == 1) {
            p /= 2;
            R[i] += p * memo[i][{i + 1, x, y, z, x, y, z, 0}].mp;
            R[i] += p * memo[i][{i + 1, x, y, z, x, y, z, 1}].mp;
            dfs(dfs, i + 1, x + 1, y, z, p);
            dfs(dfs, i + 1, x, y + 1, z, p);
        } else {
            p /= 2;
            R[i] += p * memo[i][{i + 1, x, y, z, x, y, z, 2}].mp;
            dfs(dfs, i + 1, x, y, z + 1, p);
            p /= 2;
            R[i] += p * memo[i][{i + 1, x, y, z, x, y, z, 0}].mp;
            R[i] += p * memo[i][{i + 1, x, y, z, x, y, z, 1}].mp;
            dfs(dfs, i + 1, x + 1, y, z, p);
            dfs(dfs, i + 1, x, y + 1, z, p);
        }
        };
    dfs(dfs, 0, 0, 0, 0, 1);
    for (int i = 0; i < n; ++i) {
        if (i) std::cout << ' ';
        std::cout << R[i].val();
    }
    std::cout << std::endl;
}
0