結果
問題 | No.1574 Swap and Repaint |
ユーザー |
![]() |
提出日時 | 2021-08-15 09:31:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,409 ms / 10,000 ms |
コード長 | 3,540 bytes |
コンパイル時間 | 4,073 ms |
コンパイル使用メモリ | 189,992 KB |
最終ジャッジ日時 | 2025-01-23 22:23:22 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #include <atcoder/all> #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair<int, int> P; using mint=modint998244353; mint f[2000010], invf[2000010]; mint p2[2000020], i2[2000020]; void fac(int n){ f[0]=1; for(ll i=1; i<=n; i++) f[i]=f[i-1]*i; invf[n]=f[n].inv(); for(ll i=n-1; i>=0; i--) invf[i]=invf[i+1]*(i+1); p2[1]=2, i2[1]=mint(2).inv(); p2[0]=1, 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]; for(int i=1; i<n-1; i++){ s[i]=s[i-1]+i2[i]*(invf[i]-invf[i+1]*i2[1]); } s[n-1]=0; 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); // vector<mint> v0(3); v0[0]=v0[2]=1; // for(int k=0; k<=n; k++){ // v2[k]=v1[2*n-1+k]; // v1=convolution(v1, v0); // } { const int d=1000; 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++){ int l=2*n-1+k+i-2*j; if(l>=0){ v2[k+i]+=comb(i, j)*v1[l]; } } } 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); mint c=p2[2*(n-1)]*f[n-1]; for(int k=0; k<=n; k++){ mint ans=v3[k]*f[k]*c; printf("%d\n", ans.val()); } // mint ans=0; // for(int i=0; i<n; i++){ // ans+=a[i]*s[i]; // } // mint c=p2[2*(n-1)]*f[n-1]; // ans*=c; // cout<<ans.val()<<endl; // mint invn=mint(n-1).inv(); // mint a1[100010]; // for(int i=0; i<n; i++){ // for(int j=0; j<n; j++){ // a1[j]=0; // } // for(int j=0; j<n; j++){ // if(j==0){ // a1[j]+=mint(n-2)*a[j]; // a1[j+1]+=a[j]; // }else if(j==n-1){ // a1[j]+=mint(n-2)*a[j]; // a1[j-1]+=a[j]; // }else{ // a1[j]+=mint(n-3)*a[j]; // a1[j-1]+=a[j]; // a1[j+1]+=a[j]; // } // } // mint t=0; // for(int j=0; j<n; j++){ // a[j]=a1[j]; // t+=s[j]*a[j]; // } // ans=t*c; // cout<<ans.val()<<endl; // } return 0; }