結果

問題 No.2801 Unique Maximum
ユーザー noya2noya2
提出日時 2024-06-28 21:05:48
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,638 ms / 4,000 ms
コード長 3,647 bytes
コンパイル時間 4,456 ms
コンパイル使用メモリ 294,476 KB
実行使用メモリ 27,108 KB
最終ジャッジ日時 2024-06-28 21:06:14
合計ジャッジ時間 23,039 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 4 ms
6,940 KB
testcase_02 AC 408 ms
9,416 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 4 ms
6,944 KB
testcase_05 AC 6 ms
6,940 KB
testcase_06 AC 6 ms
6,940 KB
testcase_07 AC 1,638 ms
27,108 KB
testcase_08 AC 1,575 ms
27,104 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 1,576 ms
25,428 KB
testcase_11 AC 1,567 ms
24,612 KB
testcase_12 AC 1,551 ms
23,744 KB
testcase_13 AC 1,579 ms
24,608 KB
testcase_14 AC 1,588 ms
25,428 KB
testcase_15 AC 4 ms
6,940 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 5 ms
6,944 KB
testcase_18 AC 615 ms
13,476 KB
testcase_19 AC 629 ms
14,400 KB
testcase_20 AC 694 ms
14,992 KB
testcase_21 AC 1,512 ms
24,444 KB
testcase_22 AC 1,337 ms
25,648 KB
testcase_23 AC 1,525 ms
24,528 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using ll = long long;
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#include <atcoder/convolution>
using mint = atcoder::modint998244353;
using namespace std;

vector<mint> solve(ll N, ll M){
    // f += g;
    auto add = [&](vector<mint> &f, vector<mint> g, mint v = 1) -> void {
        rep(i, 0, g.size()){
            if (i == (int)f.size()){
                f.push_back(0);
            }
            f[i] += g[i] * v;
        }
    };
    // Binomial
    vector<mint> fact(N + 1, 1), fact_inv(N + 1, 1);
    rep(i, 1, N + 1) fact[i] = fact[i - 1] * i;
    fact_inv[N] = fact[N].inv();
    for (int i = N; i > 0; i--){
        fact_inv[i - 1] = fact_inv[i] * i;
    }
    auto C = [&](int a, int b) -> mint {
        if (a < b || b < 0) return 0;
        return fact[a] * fact_inv[a - b] * fact_inv[b];
    };

    // init
    vector<mint> f(N + 2);
    vector<mint> A(N + 2); // f + f ^ 2
    vector<mint> B(N + 2); // f(x + x ^ 2)
    // g(x) = x + x ^ 2
    vector<mint> g = {0, 1, 1};
    // return (g(x) ^ (r - l - 1), sum_{i = l , l + 1, ... r - "2"}(g(x) ^ {i - l} f_{i})) 
    auto calc = [&](auto self, int l, int r) -> pair<vector<mint>, vector<mint>> {
        if (l + 1 == r) return {{1}, {0}};
        int m = (l + r) / 2;
        pair<vector<mint>, vector<mint>> tmp1 = self(self, l, m);
        // add A[m : r] from f[l : m - 1]
        vector<mint> p(m - l);
        vector<mint> q(min(l, r - l));
        rep(i, 0, min(l, r - l)) q[i] = f[i];
        rep(i, l, m - 1) p[i - l] = f[i];
        auto v = atcoder::convolution(p, q);
        rep(i, m, r){
            int j = i - l;
            if (0 <= j && j < (int)v.size()) A[i] += v[j] * 2;
        }
        v = atcoder::convolution(p, p);
        rep(i, m, r){
            int j = i - l * 2;
            if (0 <= j && j < (int)v.size()) A[i] += v[j];
        }
        // add B[m : r] from f[l : m - 1] = sum * (x + x ^ 2) ^ l
        // h(x) = g ^ l
        // h'(x) = h[m - (|sum| - 1): r]
        int a = max(0, m - (int)(tmp1.second.size()) + 1);
        int b = r;
        int len = b - a;
        vector<mint> h(len);
        rep(i, a, b) h[i - a] = C(l, i - l);
        p = atcoder::convolution(h, tmp1.second);
        rep(i, m, r){
            int j = i - a;
            if (0 <= j && j < (int)p.size()){
                B[i] += p[j];
            }
        }
        // calc f[m - 1]
        if (m <= 3){
            if (m == 1){
                f[m - 1] = 0;
            }
            if (m == 2){
                f[m - 1] = 1;
            }
            if (m == 3){
                f[m - 1] = M;
            }
        }
        else{
            f[m - 1] = (A[m] - B[m]) / (m - 3);
        }
        // add A[m : r] from f[m - 1]
        A[m - 1] += f[m - 1];
        rep(i, m, r){
            if (i < 2 * (m - 1)) A[i] += f[m - 1] * f[i - m + 1] * 2ll;
            if (i == 2 * (m - 1)) A[i] += f[m - 1] * f[m - 1];
        }
        // add B[m : r] from f[m - 1]
        rep(i, m - 1, r){
            B[i] += f[m - 1] * C(m - 1, i - m + 1);
        }
        // add sum from f[m - 1]
        add(tmp1.second, tmp1.first, f[m - 1]);
        pair<vector<mint>, vector<mint>> tmp2 = self(self, m, r);
        // merge
        tmp1.first = atcoder::convolution(tmp1.first, g);
        add(tmp1.second, atcoder::convolution(tmp2.second, tmp1.first));
        tmp1.first = atcoder::convolution(tmp1.first, tmp2.first);
        return tmp1;
    };
    calc(calc, 0, N + 2);
    f.erase(f.begin());
    f.pop_back();
    return f;
}

int main(){
    ll N, M;
    cin >> N >> M;
    cout << solve(N + 1, M).back().val() << "\n";
}
0