#830004 (C++17) No.2166 Paint and Fill

• 問題: No.2166 Paint and Fill
• ユーザー: hotman78
• 提出日時: 2023-01-03 08:46:18
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 8,203 bytes
• コンパイル時間: 3,273 ms
• コンパイル使用メモリ: 239,944 KB
• 最終ジャッジ日時: 2024-04-27 04:25:03
• 合計ジャッジ時間: 4,765 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

コンパイルメッセージ

main.cpp: In instantiation of 'std::array<T, 4> mul(const std::array<T, 4>&, const std::array<T, 4>&) [with T = std::vector<atcoder::static_modint<998244353> >]':
main.cpp:260:19:   required from here
main.cpp:66:29: error: no match for 'operator*' (operand types are 'const std::array<std::vector<atcoder::static_modint<998244353> >, 4>::value_type' {aka 'const std::vector<atcoder::static_modint<998244353> >'} and 'const std::array<std::vector<atcoder::static_modint<998244353> >, 4>::value_type' {aka 'const std::vector<atcoder::static_modint<998244353> >'})
   66 |         res[i+k*2]+=a[i+j*2]*b[j+k*2];
      |                     ~~~~~~~~^~~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ccomplex:39,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:54,
                 from main.cpp:3:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/complex:392:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const complex<_Tp>&, const complex<_Tp>&)'
  392 |     operator*(const complex<_Tp>& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/complex:392:5: note:   template argument deduction/substitution failed:
main.cpp:66:29: note:   'const std::array<std::vector<atcoder::static_modint<998244353> >, 4>::value_type' {aka 'const std::vector<atcoder::static_modint<998244353> >'} is not derived from 'const std::complex<_Tp>'
   66 |         res[i+k*2]+=a[i+j*2]*b[j+k*2];
      |                     ~~~~~~~~^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/complex:401:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const complex<_Tp>&, const _Tp&)'
  401 |     operator*(const complex<_Tp>& __x, const _Tp& __y)
      |     ^~~~~~~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/complex:401:5: note:   template argument de

ソースコード

#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;

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;
}

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;
}

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