結果

問題 No.2839 AND Constraint
コンテスト
ユーザー 👑 potato167
提出日時 2024-08-09 22:56:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 3,718 bytes
コンパイル時間 3,715 ms
コンパイル使用メモリ 239,736 KB
最終ジャッジ日時 2025-02-23 22:00:33
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

// https://yukicoder.me/problems/no/2801

#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;
    swap(N, M);
    cout << solve(N + 1, M).back().val() << "\n";
}
0