結果
問題 | No.1504 ヌメロニム |
ユーザー |
![]() |
提出日時 | 2021-05-07 22:55:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 649 ms / 2,000 ms |
コード長 | 1,183 bytes |
コンパイル時間 | 7,867 ms |
コンパイル使用メモリ | 259,156 KB |
最終ジャッジ日時 | 2025-01-21 08:39:31 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 61 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; using ll=long long; using mint=modint998244353; const ll mod=998244353; vector<mint> A(300000,0); vector<mint> Y(300001,0); vector<mint> g1(2,1); vector<mint> g2(2,1); vector<mint> inv(2,1); int N; void dfs(int l,int r){ if(l+1>=r){ return; } int x=(l+r)>>1; dfs(l,x); dfs(x,r); vector<mint> a(x-l); vector<mint> b(r-x); for(int i=l;i<x;i++){ a[x-i-1]=(A[i].val())^1; }for(int i=x;i<r;i++){ b[i-x]=A[i].val(); } vector<mint> c=convolution(a,b); for(int i=0;i<(int)(c.size());i++){ Y[i]+=c[i]; } return; } int main(){ cin>>N; string S; cin>>S; for(int i=0;i<N;i++){ if(S[i]=='i'){ A[i]=0; }else{ A[i]=1; } } inv[0]=0; for(ll i=2;i<400003;i++){ g1.push_back(g1[i-1]*i); inv.push_back(((-inv[mod%i])*(mod/i))); g2.push_back(g2[i-1]*inv[i]); } dfs(0,N); for(int i=0;i<=N;i++){ Y[i]*=g1[i]; } vector<mint> Z(N+1); for(int i=0;i<=N;i++){ Z[N-i]=Y[i]; } vector<mint> X=convolution(Z,g2); ll ANS=0; for(int i=0;i<=N;i++){ ANS^=(X[i]*g2[N-i]).val(); } cout<<ANS<<"\n"; }