結果

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

ソースコード

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 }; }
  int N = 1; while(N<n) N*=2;
  int hN = N/2;
  vector<m32> hInv = powsumFPS(A,hN);
  auto tmp = vectorm32_slice(atcoder::convolution(hInv, A), hN, N);
  tmp = vectorm32_slice(atcoder::convolution(tmp, hInv), 0, n - hN);
  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] = -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);
    vector<m32> G = convolution({1,2}, invFPS({1,MOD-1}, x+1));
    G.resize(x+1);
    //for(auto g : G) cout << g << " "; cout << endl;
    
    auto B = powFPS(G, y);
    rep(i,x) B[i+1] += B[i];
    //for(auto g : B) cout << g << " "; cout << endl;
    
    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