結果
問題 | No.1574 Swap and Repaint |
ユーザー |
![]() |
提出日時 | 2021-04-13 21:40:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,167 ms / 10,000 ms |
コード長 | 13,070 bytes |
コンパイル時間 | 5,652 ms |
コンパイル使用メモリ | 291,116 KB |
最終ジャッジ日時 | 2025-01-20 17:13:05 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endifusing ll = long long;using ld = long double;using ull = long long;#define all(s) (s).begin(),(s).end()#define rep2(i, m, n) for (int i = (m); i < (n); ++i)#define rep(i, n) rep2(i, 0, n)#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)#define drep(i, n) drep2(i, n, 0)#define rever(vec) reverse(vec.begin(), vec.end())#define sor(vec) sort(vec.begin(), vec.end())#define fi first#define se second#define P pair<ll,ll>#define REP(i, n) for (int i = 0; i < (n); ++i)const ll mod = 998244353;//const ll mod = 1000000007;const ll inf = 2000000000000000000ll;static const long double pi = 3.141592653589793;template<class T>void vcin(vector<T> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}void YesNo(bool a){if(a){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}void YESNO(bool a){if(a){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}template<class T,class U> void chmax(T& t,const U& u){if(t<u) t=u;}template<class T,class U> void chmin(T& t,const U& u){if(t>u) t=u;}template<class T> void ifmin(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}template<class T> void ifmax(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}template<typename T,typename ...Args>auto make_vector(T x,int arg,Args ...args){if constexpr(sizeof...(args)==0)return vector<T>(arg,x);else returnvector(arg,make_vector<T>(x,args...));}ll modPow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }void gbjsmzmfuuvdf(){ios::sync_with_stdio(false);std::cin.tie(nullptr);cout<< fixed << setprecision(20);}using mint = modint998244353;struct S{mint value;int size;};using F = mint;S op(S a, S b){ return {a.value+b.value, a.size+b.size}; }S e(){ return {mint(0),1}; }S mapping(F f, S x){ return {x.value+x.size*f, x.size}; }F composition(F f, F g){ return f+g; }F id(){ return mint(0); }mint k[200100];void com(){k[0]=1;for(int i=1;i<200100;i++){k[i]=k[i-1]*i;}}enum Mode {FAST = 1,NAIVE = -1,};template <class T, Mode mode = FAST>struct FormalPowerSeries : std::vector<T> {using std::vector<T>::vector;using std::vector<T>::size;using std::vector<T>::resize;using F = FormalPowerSeries;F &operator+=(const F &g){for(int i=0;i<int(min((*this).size(),g.size()));i++){(*this)[i]+=g[i];}return *this;}F &operator+=(const T &t){assert(int((*this).size()));(*this)[0]+=t;return *this;}F &operator-=(const F &g) {for(int i=0;i<int(min((*this).size(),g.size()));i++){(*this)[i]-=g[i];}return *this;}F &operator-=(const T &t){assert(int((*this).size()));(*this)[0]-=t;return *this;}F &operator*=(const T &g) {for(int i=0;i<int((*this).size());i++){(*this)[i]*=g;}return *this;}F &operator/=(const T &g) {T div=g.inv();for(int i=0;i<int((*this).size());i++){(*this)[i]*=div;}return *this;}F &operator<<=(const int d) {int n=(*this).size();(*this).insert((*this).begin(),d,0);(*this).resize(n);return *this;}F &operator>>=(const int d) {int n=(*this).size();(*this).erase((*this).begin(),(*this).begin()+min(n, d));(*this).resize(n);return *this;}F &operator=(const std::vector<T> &v) {int n = (*this).size();for(int i = 0; i < n; ++i) (*this)[i] = v[i];return *this;}F operator-() const {F ret = *this;return ret * -1;}F &operator*=(const F &g) {if(mode==FAST) {int n=(*this).size();auto tmp=atcoder::convolution(*this,g);for(int i=0;i<n;++i){(*this)[i]=tmp[i];}return *this;}else{int n = (*this).size(), m = g.size();for(int i = n - 1; i >= 0; --i) {(*this)[i] *= g[0];for(int j = 1; j < std::min(i + 1, m); j++)(*this)[i] += (*this)[i - j] * g[j];}return *this;}}F &operator/=(const F &g) {if(mode == FAST){int n = (*this).size();(*this) = atcoder::convolution(*this, g.inv());return *this;}else{assert(g[0] != T(0));T ig0 = g[0].inv();int n = (*this).size(), m = g.size();for(int i = 0; i < n; ++i) {for(int j = 1; j < std::min(i + 1, m); ++j)(*this)[i] -= (*this)[i - j] * g[j];(*this)[i] *= ig0;}return *this;}}F &operator%=(const F &g) { return *this-=*this/g*g; }F operator*(const T &g) const { return F(*this)*=g;}F operator-(const T &g) const { return F(*this)-=g;}F operator*(const F &g) const { return F(*this)*=g;}F operator-(const F &g) const { return F(*this)-=g;}F operator+(const F &g) const { return F(*this)+=g;}F operator/(const F &g) const { return F(*this)/=g;}F operator%(const F &g) const { return F(*this)%=g;}F operator<<(const int d) const { return F(*this)<<=d;}F operator>>(const int d) const { return F(*this)>>=d;}void onemul(const int d,const T c){int n=(*this).size();for(int i=n-d-1;i>=0;i--){(*this)[i+d]+=(*this)[i]*c;}}void onediv(const int d,const T c){int n=(*this).size();for(int i=0;i<n-d;i++){(*this)[i+d]-=(*this)[i]*c;}}T eval(const T &t) const {int n = (*this).size();T res = 0, tmp = 1;for(int i = 0; i < n; ++i){res += (*this)[i] * tmp, tmp *= t;}return res;}F inv(int deg = -1) const {int n = (*this).size();assert(mode == FAST and n and (*this)[0] != 0);if(deg == -1) deg = n;assert(deg > 0);F res{(*this)[0].inv()};while(int(res.size()) < deg) {int m = res.size();F f((*this).begin(), (*this).begin() + std::min(n, m * 2)), r(res);f.resize(m * 2), atcoder::internal::butterfly(f);r.resize(m * 2), atcoder::internal::butterfly(r);for(int i = 0; i < m * 2; ++i) f[i] *= r[i];atcoder::internal::butterfly_inv(f);f.erase(f.begin(), f.begin() + m);f.resize(m * 2), atcoder::internal::butterfly(f);for(int i = 0; i < m * 2; ++i) f[i] *= r[i];atcoder::internal::butterfly_inv(f);T iz = T(m * 2).inv();iz *= -iz;for(int i = 0; i < m; ++i) f[i] *= iz;res.insert(res.end(), f.begin(), f.begin() + m);}res.resize(deg);return res;}F &diff_inplace() {int n = (*this).size();for(int i = 1; i < n; ++i) (*this)[i - 1] = (*this)[i] * i;(*this)[n - 1] = 0;return *this;}F diff() const { F(*this).diff_inplace();}F &integral_inplace() {int n = (*this).size(), mod = T::mod();std::vector<T> inv(n);{inv[1] = 1;for(int i = 2; i < n; ++i)inv[i] = T(mod) - inv[mod % i] * (mod / i);}for(int i = n - 2; i >= 0; --i) (*this)[i + 1] = (*this)[i] * inv[i + 1];(*this)[0] = 0;return *this;}F integral() const { return F(*this).integral_inplace(); }F &log_inplace() {int n = (*this).size();assert(n and (*this)[0] == 1);F f_inv = (*this).inv();(*this).diff_inplace();(*this) *= f_inv;(*this).integral_inplace();return *this;}F log() const { return F(*this).log_inplace(); }F &deriv_inplace() {int n = (*this).size();assert(n);for(int i = 2; i < n; ++i) (*this)[i] *= i;(*this).erase((*this).begin());(*this).push_back(0);return *this;}F deriv() const { return F(*this).deriv_inplace(); }F &exp_inplace() {int n = (*this).size();assert(n and (*this)[0] == 0);F g{1};(*this)[0] = 1;F h_drv((*this).deriv());for(int m = 1; m < n; m *= 2) {F f((*this).begin(), (*this).begin() + m);f.resize(2 * m), atcoder::internal::butterfly(f);auto mult_f = [&](F &p) {p.resize(2 * m);atcoder::internal::butterfly(p);for(int i = 0; i < 2 * m; ++i) p[i] *= f[i];atcoder::internal::butterfly_inv(p);p /= 2 * m;};if(m > 1) {F g_(g);g_.resize(2 * m), atcoder::internal::butterfly(g_);for(int i = 0; i < 2 * m; ++i) g_[i] *= g_[i] * f[i];atcoder::internal::butterfly_inv(g_);T iz = T(-2 * m).inv();g_ *= iz;g.insert(g.end(), g_.begin() + m / 2, g_.begin() + m);}F t((*this).begin(), (*this).begin() + m);t.deriv_inplace();{F r{h_drv.begin(), h_drv.begin() + m - 1};mult_f(r);for(int i = 0; i < m; ++i) t[i] -= r[i] + r[m + i];}t.insert(t.begin(), t.back());t.pop_back();t *= g;F v((*this).begin() + m, (*this).begin() + std::min(n, 2 * m));v.resize(m);t.insert(t.begin(), m - 1, 0);t.push_back(0);t.integral_inplace();for(int i = 0; i < m; ++i) v[i] -= t[m + i];mult_f(v);for(int i = 0; i < std::min(n - m, m); ++i)(*this)[m + i] = v[i];}return *this;}F exp() const { return F(*this).exp_inplace(); }F &pow_inplace(long long k) {int n = (*this).size(), l = 0;assert(k >= 0);if(!k){for(int i = 0; i < n; ++i) (*this)[i] = !i;return *this;}while(l < n and (*this)[l] == 0) ++l;if(l > (n - 1) / k or l == n) return *this = F(n);T c = (*this)[l];(*this).erase((*this).begin(), (*this).begin() + l);(*this) /= c;(*this).log_inplace();(*this).resize(n - l * k);(*this) *= k;(*this).exp_inplace();(*this) *= c.pow(k);(*this).insert((*this).begin(), l * k, 0);return *this;}F pow(const long long k) const { return F(*this).pow_inplace(); }void spacemul(vector<pair<int, T>> g) {int n = (*this).size();auto [d, c] = g.front();if (d == 0) g.erase(g.begin());else c = 0;for(int i=n-1;i>=0;i--){(*this)[i] *= c;for (auto &[j, b] : g) {if (j > i) break;(*this)[i] += (*this)[i-j] * b;}}}void spacediv(vector<pair<int, T>> g) {int n = (*this).size();auto [d, c] = g.front();assert(d == 0 && c != T(0));T ic = c.inv();g.erase(g.begin());for(int i=0;i<n;i++){for (auto &[j, b] : g) {if (j > i) break;(*this)[i] -= (*this)[i-j] * b;}(*this)[i] *= ic;}}};using fps = FormalPowerSeries<atcoder::modint998244353, FAST>;mint g(ll a,ll b){if(a==1){return mint(1);}if(b==1){return mint(1)/mint(2);}if(a==b){return mint(1)/mint(mint(2).pow(a-1)*k[a-1]);}return mint(1)/mint(mint(2).pow(b))*(mint(2)/mint(k[b-1])-mint(1)/mint(k[b]));}int main() {gbjsmzmfuuvdf();com();ll n;cin>>n;mint h=mint(4).pow(n-1);for(int i=1;i<=n-1;i++){h*=i;}vector<mint> a(n),b(n);lazy_segtree<S, op, e, F, mapping, composition, id> seg(n);for(int i=0;i<n;i++){seg.apply(i,g(n-i,1));}for(int i=2;i<n;i++){seg.apply(i-1,n-1,g(n,i));}for(int i=2;i<=n;i++){seg.apply(n-1,g(i,i));}for(int i=0;i<n;i++){ll x;cin>>x;a[i]=x;}mint ans=0;for(int i=0;i<n;i++){ans+=a[i]*seg.prod(i,i+1).value;b[i]=seg.prod(i,i+1).value;}for(int i=n-1;i>=0;i--){a.push_back(a[i]);b.push_back(b[i]);}n*=2;rever(b);vector<mint> c=convolution(a,b);for(int i=n;i<int(c.size());i++){c[i%n]+=c[i];}c.resize(n);rever(c);fps f(n);f[0]=1;cout<<(c[0]*h/mint(2)).val()<<endl;ll k=min(int(sqrt(n/2)*8),int(n));vector<vector<pair<int,mint>>> F(k+1);vector<mint> p;F[0]={{0,mint(1)}};for(int i=1;i<=n/2;i++){ll v=i%k;if(v==i){for(int j=0;j<int(F[i-1].size());j++){F[i].push_back({F[i-1][j].fi,(n/2-3)*F[i-1][j].se});F[i].push_back({(F[i-1][j].fi-1+n)%n,F[i-1][j].se});F[i].push_back({(F[i-1][j].fi+1)%n,F[i-1][j].se});}map<int,mint> M;for(int j=0;j<int(F[i].size());j++){M[F[i][j].fi]+=F[i][j].se;}F[i].resize(0);for(auto e:M){F[i].push_back({e.fi,e.se});}mint ans=0;for(int j=0;j<int(F[i].size());j++){ans+=F[i][j].se*c[F[i][j].fi];}cout<<(ans*h/mint(2)).val()<<endl;}else{mint ans=0;for(int j=0;j<int(F[v].size());j++){ans+=F[v][j].se*c[F[v][j].fi];}cout<<(ans*h/mint(2)).val()<<endl;}if(i%k==k-1){if(int(p.size())==0){vector<pair<ll,mint>> tmp;for(int j=0;j<int(F[k-1].size());j++){F[k].push_back({F[k-1][j].fi,(n/2-3)*F[k-1][j].se});F[k].push_back({(F[k-1][j].fi-1+n)%n,F[k-1][j].se});F[k].push_back({(F[k-1][j].fi+1)%n,F[k-1][j].se});}map<int,mint> M;for(int j=0;j<int(F[k].size());j++){M[F[k][j].fi]+=F[k][j].se;}vector<pair<int,int>> S;for(auto e:M){if(e.fi>=n/2){S.push_back({e.fi-n,e.se.val()});}else{S.push_back({e.fi,e.se.val()});}}sor(S);for(int j=0;j<int(S.size());j++){p.push_back(S[j].se);}}auto d=convolution(c,p);for(int j=0;j<int(c.size());j++){c[j]=0;}for(int j=0;j<int(d.size());j++){c[(j-k+n)%n]+=d[j];}}}}