結果

問題 No.2801 Unique Maximum
ユーザー 👑 potato167potato167
提出日時 2024-06-28 21:21:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,294 ms / 4,000 ms
コード長 3,660 bytes
コンパイル時間 3,475 ms
コンパイル使用メモリ 249,044 KB
実行使用メモリ 23,136 KB
最終ジャッジ日時 2024-06-28 21:21:55
合計ジャッジ時間 18,284 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 3 ms
6,820 KB
testcase_02 AC 328 ms
8,480 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 3 ms
6,944 KB
testcase_05 AC 4 ms
6,940 KB
testcase_06 AC 4 ms
6,940 KB
testcase_07 AC 1,240 ms
21,672 KB
testcase_08 AC 1,226 ms
21,672 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 1,233 ms
21,664 KB
testcase_11 AC 1,247 ms
23,136 KB
testcase_12 AC 1,275 ms
22,760 KB
testcase_13 AC 1,294 ms
23,012 KB
testcase_14 AC 1,288 ms
21,660 KB
testcase_15 AC 3 ms
6,944 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 4 ms
6,940 KB
testcase_18 AC 482 ms
11,216 KB
testcase_19 AC 472 ms
13,292 KB
testcase_20 AC 569 ms
12,656 KB
testcase_21 AC 1,222 ms
19,996 KB
testcase_22 AC 979 ms
20,604 KB
testcase_23 AC 1,215 ms
22,108 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];
    };
    // return c * (1 + x) ^ a * x ^ b
    auto make_bin = [&](int a, int b) -> vector<mint> {
        vector<mint> res(a + b + 1, 0);
        rep(i, 0, a + 1) res[i + b] = C(a, i);
        return res;
    };
    // 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) -> vector<mint> {
        if (l + 1 == r) return {0};
        int m = (l + r) / 2;
        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.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);
        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, make_bin(m - 1 - l, m - 1 - l), f[m - 1]);
        vector<mint> tmp2 = self(self, m, r);
        // merge
        add(tmp1, atcoder::convolution(tmp2, make_bin(m - l, m - l)));
        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