結果
問題 | No.2349 Power!! (Hard) |
ユーザー |
|
提出日時 | 2023-06-10 21:00:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 989 ms / 7,000 ms |
コード長 | 2,167 bytes |
コンパイル時間 | 5,525 ms |
コンパイル使用メモリ | 263,400 KB |
最終ジャッジ日時 | 2025-02-14 01:24:52 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using i64=int64_t; template<class mint> vector<mint> MiddleProd(vector<mint> f,vector<mint> g){ int N=f.size(),M=g.size(); assert(N>=M); reverse(g.begin(),g.end()); vector<mint> h=atcoder::convolution(f,g); vector<mint> res(N-M+1); for(int i=M-1;i<N;++i){ res[i-(M-1)]=h[i]; } return res; } template<class mint> vector<mint> MultiEvalGeomSeq(vector<mint> f,mint r,int M){ if(f.size()==0){ vector<mint> res(M); return res; } int N=f.size(); auto calc=[&](mint q,int K){ //q^Tr(i) を計算 vector<mint> res(K,1); mint nw=1; for(int i=1;i<K;++i){ nw*=q; res[i]=res[i-1]*nw; } return res; }; vector<mint> A=calc(r,N+M-1),B=calc(mint(1)/r,max(N,M)); for(int i=0;i<N;++i){ f[i]*=B[i]; } auto g=MiddleProd(A,f); for(int i=0;i<M;++i){ g[i]*=B[i]; } return g; } template<class mint> vector<mint> AllInv(vector<mint> f){ int n=f.size(); vector<mint> res(n+1,1); for(int i=0;i<n;++i){ res[i+1]=res[i]*f[i]; } mint t=mint(1)/res[n]; res.pop_back(); for(int i=n-1;i>=0;--i){ res[i]*=t; t*=f[i]; } return res; } void solve(){ constexpr i64 P=998244353,D=(1<<13)*119,E=(P-1)/D; using mint=atcoder::static_modint<P>; i64 A,N; cin>>A>>N; i64 L=N/D,R=N%D; auto h=[&](int n){ i64 m=n/E; vector<mint> g(m); mint t1=mint(A).pow(E*E),nw=1,cff=1; for(i64 i=0;i<m;++i){ g[i]=nw; nw*=t1*cff; cff*=t1*t1; } auto W=MultiEvalGeomSeq(g,mint(A).pow(2*E),E); vector<mint> res(E); nw=1,cff=1; for(i64 i=0;i<E;++i){ res[i]+=nw*W[i]; nw*=A*cff; cff*=A*A; } nw=mint(A).pow(m*m*E*E),cff=mint(A).pow(2*m*E); for(i64 i=m*E;i<n;++i){ res[i%E]+=nw; nw*=A*cff; cff*=A*A; } return res; }; vector<mint> X=h(D),Y=h(R); mint ans=0,t2=mint(A).pow(2*D),t3=mint(A).pow(2*L*D),t4=1,t5=1; vector<mint> Z(E); for(i64 t=0;t<E;++t){ Z[t]=-t5+1; if(Z[t]==0){ Z[t]=1; } t5*=t2; } auto H=AllInv(Z); for(i64 t=0;t<E;++t){ ans+=(t5==mint(1)?L:(-t4+1)*H[t])*X[t]+t4*Y[t]; t4*=t3; t5*=t2; } cout<<ans.val()<<endl; } int main(){ int T; cin>>T; while(T--){ solve(); } }