結果

問題 No.3349 AtCoder Janken Train
コンテスト
ユーザー りすりす/TwoSquirrels
提出日時 2026-01-25 13:28:49
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 36 ms / 2,000 ms
コード長 1,376 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,919 ms
コンパイル使用メモリ 215,096 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-25 13:28:55
合計ジャッジ時間 5,335 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// Gemini 3 Thinking

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

using namespace std;
using namespace atcoder;

using mint = modint998244353;

int main() {
    int N, M;
    cin >> N >> M;

    if (N == 0) {
        cout << 1 << endl;
        return 0;
    }

    // 指数型生成関数の係数を管理するベクトル
    // f_n は暖色を先頭とする有効な並び方の数 / (m! * (2^n-m)!) を保持します
    vector<mint> f = {1};

    for (int t = 0; t < N; ++t) {
        // g_{t} は x^(2^t) なので、f_{t} * (f_{t} + x^(2^t)) を計算します
        vector<mint> f_plus_g = f;
        f_plus_g.push_back(1); // x^(2^t) の項を加算

        f = convolution(f, f_plus_g);
        
        // f の次数は常に 2^(t+1) - 1 になります
    }

    // 最終的な答えを抽出
    // [x^M] (f_N + g_N) * M! * (2^N - M)! を計算します
    mint ans_coeff;
    int total_people = 1 << N;
    if (M < total_people) {
        ans_coeff = f[M];
    } else {
        ans_coeff = 1; // g_N = x^(2^N) の係数
    }

    // 階乗の計算
    vector<mint> fact(total_people + 1, 1);
    for (int i = 2; i <= total_people; ++i) {
        fact[i] = fact[i - 1] * i;
    }

    mint result = ans_coeff * fact[M] * fact[total_people - M];

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

    return 0;
}
0