結果

問題 No.2166 Paint and Fill
ユーザー hotman78hotman78
提出日時 2023-07-23 09:56:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 7,456 ms / 10,000 ms
コード長 8,203 bytes
コンパイル時間 6,731 ms
コンパイル使用メモリ 298,016 KB
実行使用メモリ 199,672 KB
最終ジャッジ日時 2023-10-24 16:37:51
合計ジャッジ時間 161,612 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 233 ms
78,964 KB
testcase_01 AC 942 ms
14,976 KB
testcase_02 AC 2,291 ms
167,084 KB
testcase_03 AC 317 ms
79,984 KB
testcase_04 AC 316 ms
79,968 KB
testcase_05 AC 314 ms
79,964 KB
testcase_06 AC 314 ms
79,964 KB
testcase_07 AC 315 ms
79,952 KB
testcase_08 AC 2,447 ms
106,240 KB
testcase_09 AC 2,437 ms
106,368 KB
testcase_10 AC 2,449 ms
106,528 KB
testcase_11 AC 2,441 ms
106,348 KB
testcase_12 AC 2,438 ms
106,220 KB
testcase_13 AC 7,450 ms
196,716 KB
testcase_14 AC 7,456 ms
196,148 KB
testcase_15 AC 7,422 ms
196,912 KB
testcase_16 AC 7,346 ms
196,684 KB
testcase_17 AC 7,451 ms
197,376 KB
testcase_18 AC 6,869 ms
196,948 KB
testcase_19 AC 6,786 ms
197,300 KB
testcase_20 AC 6,900 ms
199,672 KB
testcase_21 AC 6,805 ms
199,564 KB
testcase_22 AC 5,010 ms
192,540 KB
testcase_23 AC 5,692 ms
198,616 KB
testcase_24 AC 5,604 ms
199,064 KB
testcase_25 AC 5 ms
7,660 KB
testcase_26 AC 5 ms
7,660 KB
testcase_27 AC 2,581 ms
14,972 KB
testcase_28 AC 2,624 ms
15,096 KB
testcase_29 AC 1,914 ms
11,288 KB
testcase_30 AC 4,613 ms
14,984 KB
testcase_31 AC 4,622 ms
14,984 KB
testcase_32 AC 4,618 ms
14,984 KB
testcase_33 AC 4,617 ms
14,984 KB
testcase_34 AC 4,631 ms
14,984 KB
testcase_35 AC 4,639 ms
14,984 KB
testcase_36 AC 4,626 ms
14,984 KB
testcase_37 AC 4,627 ms
14,984 KB
testcase_38 AC 4,633 ms
14,984 KB
testcase_39 AC 4,713 ms
14,984 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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();
    }
}
0