結果
問題 | No.2166 Paint and Fill |
ユーザー | hotman78 |
提出日時 | 2023-07-23 09:56:50 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 7,508 ms / 10,000 ms |
コード長 | 8,203 bytes |
コンパイル時間 | 6,540 ms |
コンパイル使用メモリ | 297,928 KB |
実行使用メモリ | 199,452 KB |
最終ジャッジ日時 | 2024-09-24 07:56:16 |
合計ジャッジ時間 | 161,340 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 233 ms
78,836 KB |
testcase_01 | AC | 948 ms
14,644 KB |
testcase_02 | AC | 2,299 ms
166,964 KB |
testcase_03 | AC | 314 ms
79,740 KB |
testcase_04 | AC | 315 ms
79,880 KB |
testcase_05 | AC | 313 ms
79,736 KB |
testcase_06 | AC | 314 ms
79,804 KB |
testcase_07 | AC | 316 ms
79,724 KB |
testcase_08 | AC | 2,456 ms
106,184 KB |
testcase_09 | AC | 2,457 ms
106,192 KB |
testcase_10 | AC | 2,451 ms
106,472 KB |
testcase_11 | AC | 2,440 ms
106,168 KB |
testcase_12 | AC | 2,445 ms
106,048 KB |
testcase_13 | AC | 7,508 ms
196,464 KB |
testcase_14 | AC | 7,486 ms
196,220 KB |
testcase_15 | AC | 7,441 ms
196,780 KB |
testcase_16 | AC | 7,370 ms
196,564 KB |
testcase_17 | AC | 7,388 ms
197,240 KB |
testcase_18 | AC | 6,790 ms
196,824 KB |
testcase_19 | AC | 6,779 ms
197,156 KB |
testcase_20 | AC | 6,898 ms
199,404 KB |
testcase_21 | AC | 6,822 ms
199,452 KB |
testcase_22 | AC | 5,003 ms
192,348 KB |
testcase_23 | AC | 5,682 ms
198,684 KB |
testcase_24 | AC | 5,594 ms
198,812 KB |
testcase_25 | AC | 5 ms
7,424 KB |
testcase_26 | AC | 5 ms
7,404 KB |
testcase_27 | AC | 2,582 ms
14,772 KB |
testcase_28 | AC | 2,639 ms
14,892 KB |
testcase_29 | AC | 1,913 ms
11,084 KB |
testcase_30 | AC | 4,619 ms
14,772 KB |
testcase_31 | AC | 4,645 ms
14,772 KB |
testcase_32 | AC | 4,643 ms
14,772 KB |
testcase_33 | AC | 4,626 ms
14,776 KB |
testcase_34 | AC | 4,628 ms
14,900 KB |
testcase_35 | AC | 4,644 ms
14,776 KB |
testcase_36 | AC | 4,668 ms
14,776 KB |
testcase_37 | AC | 4,650 ms
14,776 KB |
testcase_38 | AC | 4,643 ms
14,780 KB |
testcase_39 | AC | 4,655 ms
14,832 KB |
ソースコード
#pragma GCC optimize("Ofast") #pragma GCC target("avx2") #include<bits/stdc++.h> #include<atcoder/modint.hpp> #include<atcoder/convolution.hpp> using namespace std; using namespace atcoder; using mint=atcoder::static_modint<998244353>; #define rep(i,a,b) for(int i=(a);i<(b);++i) #define all(n) (n).begin(),(n).end() array<mint,1000000>fact; using lint=long long; istream& operator>>(istream& in,mint& y){ long long x; in>>x; y=mint(x); return in; } ostream& operator>>(ostream& out,const mint& y){ out<<y.val(); return out; } using poly=vector<mint>; int sz(const poly&x){return x.size();} poly shrink(poly x){ while(sz(x)>=1&&x.back().val()==0)x.pop_back(); return x; } poly pre(const poly&x,int n){ auto res=x; res.resize(n); return res; } poly operator+(const poly& x,const poly& y){ poly res(max(x.size(),y.size())); rep(i,0,x.size())res[i]+=x[i]; rep(i,0,y.size())res[i]+=y[i]; return res; } poly operator-(const poly& x){ poly res(x.size()); rep(i,0,x.size())res[i]=-x[i]; return res; } poly operator-(const poly&x,const poly&y){ return x+(-y); } poly operator*(const poly&x,const poly&y){ return atcoder::convolution(x,y); } poly& operator+=(poly& x,const poly& y){ return x=(x+y); } poly& operator-=(poly& x,const poly& y){ return x=(x-y); } poly& operator*=(poly& x,const poly& y){ return x=(x*y); } istream& operator>>(istream& in,poly& y){ int n=sz(y); rep(i,0,n)in>>y[i]; return in; } ostream& operator<<(ostream& out,const poly& y){ int n=sz(y); rep(i,0,n){ if(i)out<<' '; out<<y[i].val(); } return out; } poly inv(const poly& x){ int n=sz(x); if(n==1)return poly{x[0].inv()}; auto c=inv(pre(x,(n+1)/2)); return pre(c*(poly{2}-c*x),n); } pair<poly,poly> divmod(const poly&a,const poly& b){ assert(!b.empty()); if(b.back().val()==0)return divmod(a,shrink(b)); if(a.empty())return make_pair(poly{},poly{}); if(a.back().val()==0)return divmod(shrink(a),b); int n=max(0,sz(a)-sz(b)+1); if(n==0)return make_pair(poly{},a); auto c=a; auto d=b; reverse(c.begin(),c.end()); reverse(d.begin(),d.end()); d.resize(n); c*=inv(d); c.resize(n); reverse(c.begin(),c.end()); return make_pair(c,pre(a-c*b,(int)b.size()-1)); } poly multipoint_evalution(const poly&a,const poly&b){ int n=b.size(); vector<poly>v(n*2); rep(i,0,n){ v[i+n]=poly{-mint(b[i]),mint(1)}; } for(int i=n-1;i>=1;--i){ v[i]=v[i*2]*v[i*2+1]; } poly ans(n); v[0]=a; rep(i,1,n*2){ v[i]=divmod(v[i/2],v[i]).second; if(i>=n)ans[i-n]=v[i][0]; } return ans; } vector<mint> shift(vector<mint>a,int t,int m=-1){ int n=a.size(); if(m==-1){ return shift(a,t,n); }else if(m==0){ return vector<mint>(); }else if(m<n){ auto p=shift(a,t,n); p.resize(m); return p; }else if(m>n){ int z=max(n,m-n); auto p=shift(a,t,z); auto q=shift(a,t+z,n); p.insert(p.end(),q.begin(),q.end()); p.resize(m); return p; } //前計算 vector<mint>fact(n,1),expx(n,1),expr(n,1),v(n,1); rep(i,1,n)fact[i]=fact[i-1]*i; expx[n-1]=fact[n-1].inv(); for(int i=n-2;i>=0;--i)expx[i]=expx[i+1]*(i+1); rep(i,0,n)expr[i]=expx[i]*(i%2?-1:1); rep(i,1,n)v[i]=v[i-1]*(t-i+1); rep(i,0,n)v[i]*=expx[i]; // 下降冪表示に変換 rep(i,0,n)a[i]*=expx[i]; a=atcoder::convolution(a,expr); a.resize(n); // shift rep(i,0,n)a[i]*=fact[i]; reverse(all(a)); a=atcoder::convolution(a,v); a.resize(n); reverse(all(a)); rep(i,0,n)a[i]*=expx[i]; // 標本点に変換 a=atcoder::convolution(a,expx); a.resize(n); rep(i,0,n)a[i]*=fact[i]; return a; } template<typename T> array<T,4> mul(const array<T,4>& a,const array<T,4>& b){ array<T,4>res; res.fill(T()); rep(i,0,2)rep(k,0,2)rep(j,0,2){ res[i+k*2]+=a[i+j*2]*b[j+k*2]; } return res; } array<vector<mint>,4> shift(array<vector<mint>,4> a){ int n=a[0].size(); // rep(t,0,1)rep(j,0,n)cout<<a[t][j].val()<<" \n"[j==n-1]; rep(i,0,4)a[i]=shift(a[i],0,n*4); // rep(t,0,1)rep(j,0,n*4)cout<<a[t][j].val()<<" \n"[j==n*4-1]; array<vector<mint>,4>b; rep(i,0,4)b[i].resize(n*2); rep(j,0,n*2){ auto c=mul(array<mint,4>{a[0][j*2],a[1][j*2],a[2][j*2],a[3][j*2]},array<mint,4>{a[0][j*2+1],a[1][j*2+1],a[2][j*2+1],a[3][j*2+1]}); rep(i,0,4)b[i][j]=c[i]; } return b; } void solve2(){ lint n,k; cin>>n>>k; if(k>=mint::mod()){ cout<<0<<endl; return; } array<vector<mint>,4>a=array<vector<mint>,4>{vector{mint(n)*2,mint(n-1)*2,mint(n-2)*2},vector{mint(0),mint(n),mint(n*2-1)},vector(3,mint(1)),vector(3,mint(0))}; lint i=1; for(;i*i*3<k;i*=2){ a=shift(a); } lint j=0; array<mint,4> ans=array{mint(1),mint(0),mint(0),mint(1)}; // auto ans2=ans; for(;(j+1)*i<k;++j){ ans=mul(ans,array<mint,4>{a[0][j],a[1][j],a[2][j],a[3][j]}); } auto get=[&](lint k){ return array<mint,4>{mint(n-k)*2,mint(k)*(n*2-k+1)/2,mint(1),mint(0)}; }; // cerr<<i<<j<<endl; // rep(l,0,j*i){ // ans2=mul(ans2,get(l)); // } // cout<<ans[0].val()<<endl; // cout<<ans2[0].val()<<endl; for(lint l=j*i;l<k;++l){ ans=mul(ans,get(l)); } // { // auto ans=mul(mul(get(4),get(5)),mul(get(6),get(7))); // cout<<ans[0].val()<<endl; // } cout<<ans[0].val()<<endl; } void solve1(int n){ vector<pair<long long,long long>>v(n); rep(i,0,n)cin>>v[i].second>>v[i].first; auto v2=v; sort(v.begin(),v.end()); int sz=1; while(sz<n+101010)sz*=2; auto tmp=mint(2).inv(); auto get=[&](lint k)->array<poly,4> { return array<poly,4>{poly{-mint(k*2),mint(2)},poly{mint(-k*(k-1)/2),mint(k)},poly{mint(1)},poly{mint(0)}}; }; auto prod=[&](auto prod,const vector<array<poly,4>>& x)->array<poly,4> { if(x.size()==0)return array<poly,4>{poly{mint(1)},poly{mint(0)},poly{mint(0)},poly{mint(1)}}; if(x.size()==1)return x[0]; return mul(prod(prod,vector(x.begin(),x.begin()+x.size()/2)),prod(prod,vector(x.begin()+x.size()/2,x.end()))); }; vector<poly>div(sz*2,poly{mint(1)}); const auto one=array<poly,4>{poly{mint(1)},poly{mint(0)},poly{mint(0)},poly{mint(1)}}; vector<array<poly,4>>res(sz*2,one); int tmp2=0; rep(i,0,n){ rep(j,i?v[i-1].first:0,v[i].first){ res[sz+tmp2]=get(j); tmp2++; } div[sz+tmp2]=poly{-mint(v[i].second),mint(1)}; tmp2++; } for(int i=sz-1;i>=1;--i){ res[i]=mul(res[i*2],res[i*2+1]); } for(int i=sz-1;i>=1;--i){ div[i]=div[i*2]*div[i*2+1]; } vector<mint> ans(n); map<pair<long long,long long>,mint> ans2; int cnt=0; auto dfs=[&](auto dfs,int i,array<poly,4>now)->void { rep(j,0,4)now[j]=divmod(now[j],div[i]).second; if(cnt<n&&i-sz==v[cnt].first+cnt){ ans2[v[cnt]]=now[0].empty()?0:now[0][0]; cnt++; } if(sz<=i)return; dfs(dfs,i*2,now); dfs(dfs,i*2+1,mul(now,res[i*2])); }; dfs(dfs,1,one); rep(i,0,n){ cout<<ans2[v2[i]].val()<<endl; } // rep(i,1,sz*2){ // if(i>=2)res[i]=mul(res[i/2],res[i]); // rep(j,0,4){ // res[i][j]=divmod(res[i][j],div[i]).second; // } // if(i>=sz&&i<n+sz){ // ans2[v[i-sz]]=res[i][0].empty()?0:res[i][0][0]; // } // } // rep(i,0,n){ // rep(j,0,v[i].first)res[i].emplace_back(get(j)); // res[i]=vector{prod(prod,res[i])}; // rep(j,0,4){ // res[i].back()[j]=divmod(res[i].back()[j],poly{-mint(v[i].second),mint(1)}).second; // if(res[i].back()[j].empty())res[i].back()[j]=poly{mint(0)}; // } // ans2[v[i]]=res[i].back()[0][0]; // } } int main(){ int t; cin>>t; if(t>5){ solve1(t); return 0; } while(t--){ solve2(); } }