結果
問題 | No.1574 Swap and Repaint |
ユーザー |
![]() |
提出日時 | 2021-08-15 09:47:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,469 ms / 10,000 ms |
コード長 | 1,682 bytes |
コンパイル時間 | 3,882 ms |
コンパイル使用メモリ | 158,296 KB |
最終ジャッジ日時 | 2025-01-23 22:24:16 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <cstdio> #include <iostream> #include <vector> #include <atcoder/all> using namespace std; using namespace atcoder; using mint=modint998244353; mint f[999999], invf[999999], p2[999999], i2[999999]; void fac(int n){ f[0]=1; for(int i=1; i<=n; i++) f[i]=f[i-1]*i; invf[n]=f[n].inv(); for(int i=n-1; i>=0; i--) invf[i]=invf[i+1]*(i+1); p2[1]=2, i2[1]=mint(2).inv(), p2[0]=i2[0]=1; for(int i=2; i<=n; i++){ p2[i]=p2[i-1]*2; i2[i]=i2[i-1]*i2[1]; } } mint comb(int x, int y){ if(!(0<=y && y<=x)) return 0; return f[x]*invf[y]*invf[x-y]; } int main() { int n; cin>>n; fac(2*n); mint a[100010]; for(int i=0; i<n; i++){ int a1; cin>>a1; a[i]=a1; } vector<mint> s(n); s[0]=i2[1], s[n-1]=0; for(int i=1; i<n-1; i++) s[i]=s[i-1]+i2[i]*(invf[i]-invf[i+1]*i2[1]); for(int i=0; i<n; i++) s[n-1]+=i2[i]*invf[i]; vector<mint> va(3*n); for(int i=0; i<n; i++){ va[i]=a[i]; va[n+i]=a[n-1-i]; va[2*n+i]=a[i]; } auto v1=convolution(va, s); vector<mint> v2(n+1); const int d=3000; vector<mint> v0(2*d+1); for(int k=0; k<=d; k++) v0[2*k]=comb(d, k); for(int k=0; k<=n; k+=d){ for(int i=0; i+k<=n && i<d; i++) for(int j=0; j<=i; j++) v2[k+i]+=comb(i, j)*v1[2*n-1+k+i-2*j]; v1=convolution(v1, v0); v1.resize(3*n); } for(int k=0; k<=n; k++) v2[k]*=invf[k]; vector<mint> v3(n+1); for(int k=0; k<=n; k++) v3[k]=mint(n-3).pow(k)*invf[k]; v3=convolution(v3, v2); for(int k=0; k<=n; k++){ mint ans=v3[k]*f[k]*p2[2*(n-1)]*f[n-1]; printf("%d\n", ans.val()); } return 0; }