結果

問題 No.2166 Paint and Fill
ユーザー hotman78hotman78
提出日時 2022-12-19 23:42:57
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,337 bytes
コンパイル時間 3,234 ms
コンパイル使用メモリ 252,768 KB
実行使用メモリ 14,660 KB
最終ジャッジ日時 2024-04-29 02:35:15
合計ジャッジ時間 37,224 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,548 KB
testcase_01 AC 692 ms
14,660 KB
testcase_02 AC 7,623 ms
7,552 KB
testcase_03 AC 146 ms
7,216 KB
testcase_04 AC 149 ms
7,252 KB
testcase_05 AC 147 ms
7,392 KB
testcase_06 AC 148 ms
7,376 KB
testcase_07 AC 145 ms
7,380 KB
testcase_08 AC 2,584 ms
7,348 KB
testcase_09 AC 2,518 ms
7,464 KB
testcase_10 AC 2,521 ms
7,484 KB
testcase_11 AC 2,577 ms
7,484 KB
testcase_12 AC 2,538 ms
7,328 KB
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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


array<mint,4> mul(const array<mint,4>& a,const array<mint,4>& b){
    array<mint,4>res;
    res.fill(0);
    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 main(){
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--){
        solve2();
    }
}
0