結果

問題 No.1771 A DELETEQ
ユーザー 👑 NachiaNachia
提出日時 2021-12-05 16:16:33
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 13 ms / 3,500 ms
コード長 3,501 bytes
コンパイル時間 2,641 ms
コンパイル使用メモリ 123,272 KB
実行使用メモリ 4,500 KB
最終ジャッジ日時 2023-09-21 14:03:27
合計ジャッジ時間 7,102 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 12 ms
4,500 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 12 ms
4,380 KB
testcase_05 AC 13 ms
4,380 KB
testcase_06 AC 1 ms
4,384 KB
testcase_07 AC 2 ms
4,384 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 4 ms
4,380 KB
testcase_10 AC 4 ms
4,376 KB
testcase_11 AC 4 ms
4,376 KB
testcase_12 AC 4 ms
4,380 KB
testcase_13 AC 4 ms
4,380 KB
testcase_14 AC 7 ms
4,380 KB
testcase_15 AC 12 ms
4,376 KB
testcase_16 AC 12 ms
4,376 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 5 ms
4,380 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 6 ms
4,380 KB
testcase_21 AC 3 ms
4,376 KB
testcase_22 AC 7 ms
4,380 KB
testcase_23 AC 6 ms
4,380 KB
testcase_24 AC 4 ms
4,380 KB
testcase_25 AC 3 ms
4,380 KB
testcase_26 AC 7 ms
4,376 KB
testcase_27 AC 4 ms
4,380 KB
testcase_28 AC 3 ms
4,376 KB
evil_hand_1.txt AC 428 ms
11,688 KB
evil_hand_2.txt AC 2 ms
4,380 KB
evil_hand_3.txt AC 1 ms
4,380 KB
evil_random_1.txt AC 97 ms
5,436 KB
evil_random_2.txt AC 205 ms
7,312 KB
evil_random_3.txt AC 204 ms
7,384 KB
evil_random_4.txt AC 427 ms
11,480 KB
evil_random_5.txt AC 205 ms
7,500 KB
evil_random_6.txt AC 99 ms
5,028 KB
evil_random_7.txt AC 432 ms
10,776 KB
evil_random_8.txt AC 431 ms
10,804 KB
evil_random_9.txt AC 432 ms
10,688 KB
権限があれば一括ダウンロードができます

ソースコード

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