結果
問題 | No.1771 A DELETEQ |
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
#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;