QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#229304 | #7632. Balanced Arrays | ucup-team055# | AC ✓ | 120ms | 36808kb | C++17 | 3.2kb | 2023-10-28 15:44:19 | 2023-10-28 15:44:19 |
Judging History
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