結果

問題 No.3349 AtCoder Janken Train
コンテスト
ユーザー りすりす/TwoSquirrels
提出日時 2025-11-19 15:24:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 68 ms / 2,000 ms
コード長 5,623 bytes
コンパイル時間 6,239 ms
コンパイル使用メモリ 141,132 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-11-19 17:11:05
合計ジャッジ時間 8,232 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Gemini 3 Thinking

/**
 * Problem Analysis:
 * We are merging columns in a binary tree structure.
 * Let's classify the "state" of a column by the color of its head person.
 * - If a column headed by Warm (W) meets a column headed by Cold (C), W wins the head position.
 * - If W meets W, winner is W.
 * - If C meets C, winner is C.
 * * Effectively, W is dominant. A column has a Cold head if and only if ALL head-to-head comparisons 
 * leading to this state were won by Cold. Given the rules, this implies that for a specific binary 
 * tree structure, the head is Cold iff all people in the specific positions that "compete" for the 
 * head are Cold.
 * * Actually, simpler logic:
 * For the final permutation to be valid, for every canonical split into Left (L) and Right (R) halves:
 * It is FORBIDDEN to have Head(L) == Cold and Head(R) == Warm.
 * Because if Head(L) was Cold and Head(R) was Warm, they would merge as (R, L), not (L, R).
 * * Let W_t(x) be the generating function for the number of valid color patterns of length 2^t 
 * where the head is Warm, indexed by the number of Cold people.
 * Let C_t(x) be the same for Head == Cold.
 * * Base case t=0:
 * W_0(x) = 1 (1 pattern "W", 0 Cold people)
 * C_0(x) = x (1 pattern "C", 1 Cold person)
 * * Transitions t -> t+1:
 * Merge L and R.
 * Valid merges for New Head Warm:
 * 1. Head(L)=W, Head(R)=W. (Valid, New Head W). Count: W_t * W_t
 * 2. Head(L)=W, Head(R)=C. (Valid, New Head W). Count: W_t * C_t
 * Total W_{t+1} = W_t * (W_t + C_t).
 * * Valid merges for New Head Cold:
 * 1. Head(L)=C, Head(R)=C. (Valid, New Head C). Count: C_t * C_t
 * (Note: Head(L)=C, Head(R)=W is invalid).
 * * Observation:
 * C_t(x) will always be x^{2^t}. Because if there is even one Warm person, 
 * they will eventually bubble up to the head if they meet a Cold person. 
 * Wait, "all people are Cold" is the only case for Cold Head?
 * Yes. If there is a Warm person, consider the "highest" node in the tournament tree 
 * where a Warm-headed list meets a Cold-headed list. The Warm head wins. 
 * Thus the root will be Warm-headed unless no such meeting occurs (all Cold).
 * * So C_t(x) = x^{2^t}.
 * Algorithm:
 * P = {1}
 * For t = 0 to N-1:
 * Sz = 2^t
 * P_next = P * (P + x^Sz)
 * P = P_next
 * Trim P to size M+1 if necessary.
 * * Final Answer: P[M] * M! * (2^N - M)!
 * Exception: If M = 2^N, P[M] is 0 (since P counts Warm heads), but valid config exists (All Cold).
 * However, if M = 2^N, the answer is simply (2^N)! since all are Cold.
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/convolution>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using mint = modint998244353;

// Factorial calculation helper
mint factorial(int n) {
    mint res = 1;
    for (int i = 1; i <= n; ++i) res *= i;
    return res;
}

int main() {
    // Optimize I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    int M;
    if (!(cin >> N >> M)) return 0;

    int num_people = 1 << N;

    // Edge Case: If everyone is Cold, the head is always Cold.
    // The standard DP tracks Warm-headed configurations.
    // Since everyone is the same color (Cold), any permutation is valid
    // because all merges are (Cold, Cold) -> Arbitrary order.
    if (M == num_people) {
        cout << factorial(num_people).val() << endl;
        return 0;
    }

    // P stores the coefficients for Warm-headed configurations.
    // P[k] = number of valid color patterns of current size with exactly k Cold people.
    // Initially size 1 (2^0), 0 Cold people.
    vector<mint> P = {1};

    for (int t = 0; t < N; ++t) {
        int S = 1 << t; // Current size of blocks being merged (2^t)
        
        // We want to compute P_{next} = P * (P + x^S).
        // x^S represents the single valid pattern of size S where head is Cold (all Cold).
        // P covers cases where head is Warm (implies not all Cold, so max Cold is S-1? 
        // Actually P can have terms up to x^S if we just talk about polynomials, 
        // but structurally Warm head means at least one Warm, so Cold count < S is correct).
        
        // Construct Q = P + x^S
        vector<mint> Q = P;
        
        // We only need coefficients up to M.
        // The term x^S contributes to the result only if we are looking for indices >= S.
        // If M < S, then x^S * P will result in terms with x^{S + ...} which are > x^M.
        // So we only add x^S to Q if S <= M.
        if (S <= M) {
            // Ensure Q has enough space to hold the term x^S
            if ((int)Q.size() <= S) {
                Q.resize(S + 1, 0);
            }
            Q[S] += 1;
        }

        // Convolve P and Q
        P = convolution(P, Q);

        // Optimization: We only care about the coefficient for x^M.
        // Terms with power > M are irrelevant.
        if ((int)P.size() > M + 1) {
            P.resize(M + 1);
        }
    }

    // P[M] is the number of valid color patterns of length 2^N with M Cold people (Head Warm).
    // Since M != 2^N (handled above), the head MUST be Warm for any valid configuration with M Cold people.
    // (If head were Cold, everyone would have to be Cold).
    mint ans = 0;
    if (M < (int)P.size()) {
        ans = P[M];
    }

    // Multiply by permutations of the specific people
    // M! ways to assign specific Cold people to the Cold positions
    // (2^N - M)! ways to assign specific Warm people to the Warm positions
    ans *= factorial(M);
    ans *= factorial(num_people - M);

    cout << ans.val() << endl;

    return 0;
}
0