結果

問題 No.1771 A DELETEQ
ユーザー 👑 Nachia
提出日時 2021-12-05 16:16:33
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 12 ms / 3,500 ms
コード長 3,501 bytes
コンパイル時間 9,084 ms
コンパイル使用メモリ 159,596 KB
最終ジャッジ日時 2025-01-26 04:34:40
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(n); i++)


#include <atcoder/modint>
#include <atcoder/convolution>
const unsigned int MOD = 998244353;
using m32 = atcoder::static_modint<MOD>;



 
vector<m32> vectorm32_slice(const vector<m32>& src, int l, int r){
    vector<m32> res(r-l);
    for(int i=l; i<r; i++) res[i-l] = src[i];
    return res;
}
void vectorm32_concat(vector<m32>& dst, const vector<m32>& src){
    for(auto a : src) dst.push_back(a);
}


vector<m32> powsumFPS(const vector<m32>& A, int n){
    if(n == 0){ return {}; }
    if(n == 1){ return { 1 }; }
    vector<m32> hInv = {1};
    while(hInv.size() < n){
        int nn = hInv.size();
        vector<m32> tmp(nn*2);
        for(int i=0; i<A.size() && i<nn*2; i++) tmp[i] = A[i];
        tmp = vectorm32_slice(atcoder::convolution(hInv, tmp), nn, nn*2);
        tmp = vectorm32_slice(atcoder::convolution(tmp, hInv), 0, min(n-nn, nn));
        vectorm32_concat(hInv, tmp);
    }
    return hInv;
}
 
 
vector<m32> invFPS(const vector<m32>& A, int n){
    m32 iA0 = A[0].inv();
    vector<m32> xA(min(n,(int)A.size()));
    for(int i=0; i<xA.size(); i++) xA[i] = -A[i] * iA0;
    xA[0] = 0;
    xA = powsumFPS(xA,n);
    for(int i=0; i<xA.size(); i++) xA[i] *= iA0;
    return xA;
}
 
 
static vector<m32> InvMOD = {1,1};
 
vector<m32> logFPS(const vector<m32>& A, int n){
    int z = A.size();
    for(int i=InvMOD.size(); i<=n; i++){
        InvMOD.push_back(-InvMOD[MOD % i] * (MOD / i));
    }
    auto res = invFPS(A, n);
    vector<m32> Abuf(z);
    rep(i,z-1) Abuf[i] = A[i+1] * (i+1);
    res = atcoder::convolution(res, Abuf);
    res.resize(n);
    for(int i=n-2; i>=0; i--) res[i+1] = res[i] * InvMOD[i+1];
    res[0] = 0;
    return res;
}
 
 
vector<m32> expFPS(const vector<m32>& A, int n){
    vector<m32> res = {1};
    while(res.size() < n){
        int z = res.size();
        auto tmp = logFPS(res,z*2);
        tmp[0] = m32(0) - 1;
        rep(i,min<int>(z*2,A.size())) tmp[i] = A[i] - tmp[i];
        res = atcoder::convolution(res, tmp);
        res.resize(min(n,2*z));
    }
    return res;
}


vector<m32> powFPS(const vector<m32>& A, u64 k){
    int n = A.size();
    int zerocnt = 0;
    rep(i,n) if(A[i] == 0) zerocnt = i+1; else break;
    if(zerocnt >= (n-1)/k+1) return vector<m32>(n,0);
    auto res = A;
    rep(i,n-zerocnt) res[i] = res[i+zerocnt];
    m32 A0 = res[0];
    m32 iA0 = A0.inv();
    m32 pA0 = A0.pow(k);
    rep(i,n) res[i] *= iA0;
    res = logFPS(res,n);
    rep(i,n) res[i] *= k;
    res = expFPS(res,n);
    rep(i,n) res[i] *= pA0;
    zerocnt *= k;
    res.resize(n);
    for(int i=n-1; i>=zerocnt; i--) res[i] = res[i-zerocnt];
    rep(i, zerocnt) res[i] = 0;
    return res;
}


int main(){
    u64 x,y; cin >> x >> y;
    if(x > y) swap(x,y);
    auto G3 = invFPS({1,MOD-1}, x+1);
    vector<m32> G = convolution({1,2}, invFPS({1,MOD-1}, x+1));
    G.resize(x+1, 0);
    
    auto B = powFPS(G, y);
    rep(i,x) B[i+1] += B[i];
    
    auto G2 = invFPS(G, x+1);
    reverse(G2.begin(), G2.end());
    G2.push_back(0);
    reverse(G2.begin(), G2.end());

    B = convolution(B, powsumFPS(G2, x+1));
    m32 ans = B[x];
    cout << ans.val() << endl;
    return 0;
}




struct ios_do_not_sync {
    ios_do_not_sync() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0