QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#235503 | #7632. Balanced Arrays | Geospiza | AC ✓ | 39ms | 35832kb | C++14 | 4.1kb | 2023-11-02 20:29:32 | 2023-11-02 20:29:32 |
Judging History
answer
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll int
#define mod 998244353
#define Ma 2000005
#define G 3
#define pb push_back
#define L (1<<22)
using namespace std;
ll mul[Ma],pre[Ma];
ll po(ll p,ll x=mod-2)
{
ll sum=1;
while (x)
{
if (x&1) sum=1ll*sum*p%mod;
p=1ll*p*p%mod;
x>>=1;
}
return sum;
}
void pri()
{
mul[0]=pre[0]=1;
for (ll i=1;i<Ma;i++)
mul[i]=1ll*mul[i-1]*i%mod;
pre[Ma-1]=po(mul[Ma-1]);
for (ll i=Ma-2;i>=0;i--)
pre[i]=1ll*pre[i+1]*(i+1)%mod;
return;
}
ll C(ll x,ll y)
{
if (x<0||y<0||x>y) return 0;
return 1ll*mul[y]*pre[x]%mod*pre[y-x]%mod;
}
inline void inc(int &x,int y){
x+=y;
if (x>=mod) x-=mod;
if (x<0) x+=mod;
}
inline void dec(int &x,int y){
x-=y;
if (x<0) x+=mod;
if (x>=mod) x-=mod;
}
int fpow(int x,int k=mod-2){
int r=1;
for (;k;k>>=1,x=1ll*x*x%mod){
if (k&1) r=1ll*r*x%mod;
}
return r;
}
int w[L],_=[]{
w[L/2]=1;
for (ll i=L/2+1,x=fpow(G,(mod-1)/L);i<L;i++)
w[i]=1ll*w[i-1]*x%mod;
for (ll i=L/2-1;i>=0;i--)
w[i]=w[i<<1];
return 0;
}();
void dft(ll *a,ll n){
for (ll k=n>>1;k;k>>=1){
for (ll i=0;i<n;i+=k<<1){
for (ll j=0;j<k;j++){
ll &x=a[i+j],y=a[i+j+k];
a[i+j+k]=1ll*(x-y+mod)*w[k+j]%mod;
inc(x,y);
}
}
}
}
void idft(ll *a,ll n){
for (ll k=1;k<n;k<<=1){
for (ll i=0;i<n;i+=k<<1){
for (ll j=0;j<k;j++){
int x=a[i+j],y=1ll*a[i+j+k]*w[k+j]%mod;
a[i+j+k]=x-y<0?x-y+mod:x-y;
inc(a[i+j],y);
}
}
}
for (ll i=0,inv=mod-(mod-1)/n;i<n;i++){
a[i]=1ll*a[i]*inv%mod;
}
std::reverse(a+1,a+n);
}
inline int norm(int n) {return 1<<std::__lg(n*2-1);}
struct poly : public std::vector <ll>
{
#define T (*this)
using std::vector <ll> ::vector;
void append(const poly &r){
insert(end(),r.begin(),r.end());
}
ll len() const{ return size();}
poly &operator ^=(const poly &r)
{
if (r.len()<len()) resize(r.len());
for (ll i=0;i<len();i++)
T[i]=1ll*T[i]*r[i]%mod;
return T;
}
poly &operator *=(int r)
{
for (ll &x:T) x=1ll*x*r%mod;
return T;
}
poly operator -() const{
poly r(T);
for (auto &x:r) x=x?mod-x:0;
return r;
}
poly operator *(int r) const {return poly(T)*=r;}
poly operator >>(int r) const{
return r>=len()?poly():poly(begin()+r,end());
}
poly pre(int k) const{
return k<len()?poly(begin(),begin()+k):T;
}
friend void dft(poly &a){(dft(a.data(),a.len()));}
friend void idft(poly &a){(idft(a.data(),a.len()));}
friend poly conv(const poly &a,const poly &b,int n)
{
poly p(a),q;
p.resize(n),dft(p);
p^=&a==&b?p:(q=b,q.resize(n),dft(q),q);
idft(p);
return p;
}
friend poly operator*(const poly &a,const poly &b){
ll len=a.len()+b.len()-1;
if (a.len()<=16||b.len()<=16){
poly c(len);
for (ll i=0;i<a.len();i++)
for (ll j=0;j<b.len();j++)
c[i+j]=(c[i+j]+1ll*a[i]*b[j]%mod)%mod;
return c;
}
return conv(a,b,norm(len)).pre(len);
}
poly inv(ll m)const{
poly x={fpow(T[0])};
for (ll k=1;k<m;k<<=1){
x.append(-((conv(pre(k*2),x,k*2)>>k)*x).pre(k));
}
return x.pre(m);
}
};
ll n,m;
void sol()
{
cin>>n>>m;
ll ans=0;
ll f=1;
for (ll i=0;i<=n&&i<=m;i++)
{
ans=(ans+1ll*f*C(i,n)*C(n,m+n-i)%mod*C(n,m+n-i+1)%mod)%mod;
f=-f;
}
ans=1ll*ans*po(n+1)%mod;
ans=(ans+mod)%mod;
printf("%d\n",ans);
return;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
pri();
int tt=1;
while (tt--)
sol();
return 0;
}
/*100 500000*/
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 30ms
memory: 35572kb
input:
2 2
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 39ms
memory: 35544kb
input:
500000 500000
output:
984531374
result:
ok 1 number(s): "984531374"
Test #3:
score: 0
Accepted
time: 26ms
memory: 35592kb
input:
500000 1
output:
219705876
result:
ok 1 number(s): "219705876"
Test #4:
score: 0
Accepted
time: 30ms
memory: 35600kb
input:
1 500000
output:
500001
result:
ok 1 number(s): "500001"
Test #5:
score: 0
Accepted
time: 29ms
memory: 35832kb
input:
500000 353535
output:
33730077
result:
ok 1 number(s): "33730077"
Test #6:
score: 0
Accepted
time: 35ms
memory: 35720kb
input:
353535 500000
output:
182445298
result:
ok 1 number(s): "182445298"
Test #7:
score: 0
Accepted
time: 35ms
memory: 35588kb
input:
499999 499999
output:
933220940
result:
ok 1 number(s): "933220940"
Test #8:
score: 0
Accepted
time: 32ms
memory: 35608kb
input:
499999 499998
output:
899786345
result:
ok 1 number(s): "899786345"
Test #9:
score: 0
Accepted
time: 38ms
memory: 35528kb
input:
377773 400009
output:
206748715
result:
ok 1 number(s): "206748715"
Test #10:
score: 0
Accepted
time: 35ms
memory: 35560kb
input:
499999 100001
output:
482775773
result:
ok 1 number(s): "482775773"
Test #11:
score: 0
Accepted
time: 35ms
memory: 35804kb
input:
444445 488884
output:
70939759
result:
ok 1 number(s): "70939759"
Test #12:
score: 0
Accepted
time: 35ms
memory: 35568kb
input:
488885 444449
output:
591315327
result:
ok 1 number(s): "591315327"
Test #13:
score: 0
Accepted
time: 34ms
memory: 35600kb
input:
500000 111
output:
313439156
result:
ok 1 number(s): "313439156"
Test #14:
score: 0
Accepted
time: 30ms
memory: 35596kb
input:
333333 444444
output:
403492103
result:
ok 1 number(s): "403492103"
Test #15:
score: 0
Accepted
time: 34ms
memory: 35604kb
input:
499994 343433
output:
334451699
result:
ok 1 number(s): "334451699"
Test #16:
score: 0
Accepted
time: 34ms
memory: 35604kb
input:
477774 411113
output:
63883341
result:
ok 1 number(s): "63883341"
Test #17:
score: 0
Accepted
time: 22ms
memory: 35528kb
input:
123456 432109
output:
238795570
result:
ok 1 number(s): "238795570"
Test #18:
score: 0
Accepted
time: 36ms
memory: 35544kb
input:
131331 467777
output:
834790039
result:
ok 1 number(s): "834790039"
Test #19:
score: 0
Accepted
time: 30ms
memory: 35572kb
input:
500000 2
output:
304727284
result:
ok 1 number(s): "304727284"
Test #20:
score: 0
Accepted
time: 26ms
memory: 35476kb
input:
1111 111
output:
98321603
result:
ok 1 number(s): "98321603"
Test #21:
score: 0
Accepted
time: 34ms
memory: 35596kb
input:
416084 493105
output:
916827025
result:
ok 1 number(s): "916827025"
Test #22:
score: 0
Accepted
time: 34ms
memory: 35720kb
input:
53888 138663
output:
57263952
result:
ok 1 number(s): "57263952"
Test #23:
score: 0
Accepted
time: 33ms
memory: 35504kb
input:
219161 382743
output:
304889787
result:
ok 1 number(s): "304889787"
Test #24:
score: 0
Accepted
time: 32ms
memory: 35588kb
input:
181392 318090
output:
12528742
result:
ok 1 number(s): "12528742"
Test #25:
score: 0
Accepted
time: 28ms
memory: 35596kb
input:
135930 422947
output:
554153000
result:
ok 1 number(s): "554153000"
Test #26:
score: 0
Accepted
time: 31ms
memory: 35600kb
input:
280507 210276
output:
812816587
result:
ok 1 number(s): "812816587"
Test #27:
score: 0
Accepted
time: 26ms
memory: 35608kb
input:
253119 420465
output:
124024302
result:
ok 1 number(s): "124024302"
Test #28:
score: 0
Accepted
time: 36ms
memory: 35604kb
input:
446636 97448
output:
150388382
result:
ok 1 number(s): "150388382"
Test #29:
score: 0
Accepted
time: 32ms
memory: 35608kb
input:
284890 126665
output:
786559507
result:
ok 1 number(s): "786559507"
Test #30:
score: 0
Accepted
time: 27ms
memory: 35580kb
input:
186708 28279
output:
607509026
result:
ok 1 number(s): "607509026"
Extra Test:
score: 0
Extra Test Passed