QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#229304#7632. Balanced Arraysucup-team055#AC ✓120ms36808kbC++173.2kb2023-10-28 15:44:192023-10-28 15:44:19

Judging History

你现在查看的是最新测评结果

  • [2023-10-28 15:44:19]
  • 评测
  • 测评结果:AC
  • 用时:120ms
  • 内存:36808kb
  • [2023-10-28 15:44:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)

struct mint{
    static  constexpr int m=998244353;
    int x;
    mint():x(0){}
    mint(ll x_):x(x_%m){if(x<0)x+=m;}
    mint &operator+=(mint b){if((x+=b.x)>=m) x-=m;return *this;}
    mint &operator-=(mint b){if((x-=b.x)<0) x+=m;return *this;}
    mint &operator*=(mint b){x=(ll)(x)*b.x%m;return *this;}
    mint pow(ll e) const {
        mint r=1,b=*this;
        while(e){
            if(e&1) r*=b;
            b*=b;
            e/=2;
        }
        return r;
    }
    mint inv() const{
        return pow(m-2);
    }
    mint &operator/=(mint b){return *this *= b.inv();}
    friend mint operator+(mint a,mint b){return a+=b;}
    friend mint operator-(mint a,mint b){return a-=b;}
    friend mint operator*(mint a,mint b){return a*=b;}
    friend mint operator/(mint a,mint b){return a/=b;}
};

mint G=3;
void ntt(bool inv,vector<mint> &a){
    int n=a.size(),s=__lg(n);
    assert((1<<s)==n);
    static vector<mint> ep,iep;
    while(ep.size()<=s){
        ep.push_back(G.pow((G.m-1)>>ep.size()));
        iep.push_back(ep.back().inv());
    }
    vector<mint> b(n);
    rep(i,1,s+1){
        int w=(1<<(s-i));
        mint base = inv ? iep[i] : ep[i], now=1;
        for(int y=0;y<n/2;y+=w){
            rep(x,0,w){
                auto l=a[(y<<1)|x];
                auto r=now * a[(y<<1)|x|w];
                b[y|x]=l+r;
                b[y|x|n>>1]=l-r;
            }
            now*=base;
        }
        swap(a,b);
    }
}

vector<mint> mult(vector<mint> &a,vector<mint> &b){
    const int n=a.size(),m=b.size();
    int z=1;
    while(z<n+m-1) z<<=1;
    auto a2=a,b2=b;
    a2.resize(z),b2.resize(z);
    ntt(false,a2),ntt(false,b2);
    rep(i,0,z) a2[i]*=b2[i];
    ntt(true,a2);
    a2.resize(n+m-1);
    mint iz=mint(z).inv();
    for(int i=0;i<n+m-1;i++) a2[i]*=iz;
    return a2;
}

struct combination{
    vector<mint> fact_rev;
    vector<mint> fact;
    combination(int len){
        fact.resize(len+1);
        fact_rev.resize(len+1);
        fact[0]=1;
        rep(i,0,len) fact[i+1]=fact[i]*(i+1);
        fact_rev[len]=fact[len].inv();
        for(int i=len;i>0;i--) fact_rev[i-1]=fact_rev[i]*i;
    }
    mint FACT(int x){
        if(x<0) return 0;
        return fact[x];
    }
    mint FACT_R(int x) {
        if (x < 0) return 0;
        return fact_rev[x];
    }
    mint REV(int x){
        if(x<=0) return 0;
        return fact[x-1]*fact_rev[x];
    }
};

void solve(){
    ll N,M;
    cin>>N>>M;
    vector<mint> A(M+1),B(M+1),C(M+1);
    combination table(2*M+2*N+100);
    rep(i,0,M+1){
        A[i]=table.FACT(i)*table.FACT(i-1)*table.FACT_R(2*i);
        B[i]=table.REV(i+1)*table.FACT_R(i)*table.FACT_R(i)*table.FACT_R(N-2*i-1);
        C[i]=table.FACT(2*i+N-1)*table.FACT_R(i)*table.FACT_R(i-1);
    }
    C[0]=0;
    auto tmp=mult(B,C);
    mint ans=0;
    rep(i,1,M+1){
        ans+=A[i]*tmp[i];
    }
    ans.x++;
    ans.x=(ans.x%ans.m+ans.m)%ans.m;
    cout<<ans.x<<"\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3532kb

input:

2 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 107ms
memory: 36796kb

input:

500000 500000

output:

984531374

result:

ok 1 number(s): "984531374"

Test #3:

score: 0
Accepted
time: 7ms
memory: 10780kb

input:

500000 1

output:

219705876

result:

ok 1 number(s): "219705876"

Test #4:

score: 0
Accepted
time: 94ms
memory: 28972kb

input:

1 500000

output:

500001

result:

ok 1 number(s): "500001"

Test #5:

score: 0
Accepted
time: 104ms
memory: 32752kb

input:

500000 353535

output:

33730077

result:

ok 1 number(s): "33730077"

Test #6:

score: 0
Accepted
time: 105ms
memory: 34456kb

input:

353535 500000

output:

182445298

result:

ok 1 number(s): "182445298"

Test #7:

score: 0
Accepted
time: 103ms
memory: 36748kb

input:

499999 499999

output:

933220940

result:

ok 1 number(s): "933220940"

Test #8:

score: 0
Accepted
time: 112ms
memory: 36808kb

input:

499999 499998

output:

899786345

result:

ok 1 number(s): "899786345"

Test #9:

score: 0
Accepted
time: 93ms
memory: 32196kb

input:

377773 400009

output:

206748715

result:

ok 1 number(s): "206748715"

Test #10:

score: 0
Accepted
time: 31ms
memory: 16576kb

input:

499999 100001

output:

482775773

result:

ok 1 number(s): "482775773"

Test #11:

score: 0
Accepted
time: 98ms
memory: 35584kb

input:

444445 488884

output:

70939759

result:

ok 1 number(s): "70939759"

Test #12:

score: 0
Accepted
time: 120ms
memory: 35104kb

input:

488885 444449

output:

591315327

result:

ok 1 number(s): "591315327"

Test #13:

score: 0
Accepted
time: 7ms
memory: 10804kb

input:

500000 111

output:

313439156

result:

ok 1 number(s): "313439156"

Test #14:

score: 0
Accepted
time: 99ms
memory: 32660kb

input:

333333 444444

output:

403492103

result:

ok 1 number(s): "403492103"

Test #15:

score: 0
Accepted
time: 108ms
memory: 32544kb

input:

499994 343433

output:

334451699

result:

ok 1 number(s): "334451699"

Test #16:

score: 0
Accepted
time: 95ms
memory: 34068kb

input:

477774 411113

output:

63883341

result:

ok 1 number(s): "63883341"

Test #17:

score: 0
Accepted
time: 97ms
memory: 29092kb

input:

123456 432109

output:

238795570

result:

ok 1 number(s): "238795570"

Test #18:

score: 0
Accepted
time: 102ms
memory: 30140kb

input:

131331 467777

output:

834790039

result:

ok 1 number(s): "834790039"

Test #19:

score: 0
Accepted
time: 5ms
memory: 10792kb

input:

500000 2

output:

304727284

result:

ok 1 number(s): "304727284"

Test #20:

score: 0
Accepted
time: 0ms
memory: 3420kb

input:

1111 111

output:

98321603

result:

ok 1 number(s): "98321603"

Test #21:

score: 0
Accepted
time: 97ms
memory: 35280kb

input:

416084 493105

output:

916827025

result:

ok 1 number(s): "916827025"

Test #22:

score: 0
Accepted
time: 41ms
memory: 13824kb

input:

53888 138663

output:

57263952

result:

ok 1 number(s): "57263952"

Test #23:

score: 0
Accepted
time: 96ms
memory: 29192kb

input:

219161 382743

output:

304889787

result:

ok 1 number(s): "304889787"

Test #24:

score: 0
Accepted
time: 90ms
memory: 26796kb

input:

181392 318090

output:

12528742

result:

ok 1 number(s): "12528742"

Test #25:

score: 0
Accepted
time: 89ms
memory: 28984kb

input:

135930 422947

output:

554153000

result:

ok 1 number(s): "554153000"

Test #26:

score: 0
Accepted
time: 49ms
memory: 19316kb

input:

280507 210276

output:

812816587

result:

ok 1 number(s): "812816587"

Test #27:

score: 0
Accepted
time: 105ms
memory: 30800kb

input:

253119 420465

output:

124024302

result:

ok 1 number(s): "124024302"

Test #28:

score: 0
Accepted
time: 30ms
memory: 15704kb

input:

446636 97448

output:

150388382

result:

ok 1 number(s): "150388382"

Test #29:

score: 0
Accepted
time: 27ms
memory: 14020kb

input:

284890 126665

output:

786559507

result:

ok 1 number(s): "786559507"

Test #30:

score: 0
Accepted
time: 7ms
memory: 7592kb

input:

186708 28279

output:

607509026

result:

ok 1 number(s): "607509026"

Extra Test:

score: 0
Extra Test Passed