QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#665651 | #9476. 012 Grid | Kevin5307 | AC ✓ | 430ms | 56940kb | C++23 | 4.8kb | 2024-10-22 14:36:45 | 2024-10-22 14:36:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace Polynomial
{
using ll=long long;
using poly=vector<ll>;
const ll mod=998244353;
ll ksm(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
inline int sz(const poly &p)
{
return p.size();
}
const poly operator +(const poly &a,const poly &b)
{
int p=sz(a),q=sz(b);
int n=max(p,q);
poly ret(n,0);
for(int i=0;i<n;i++)
{
if(i<p) ret[i]+=a[i];
if(i<q) ret[i]+=b[i];
if(ret[i]>=mod) ret[i]-=mod;
}
return ret;
}
const poly operator -(const poly &a,const poly &b)
{
int p=sz(a),q=sz(b);
int n=max(p,q);
poly ret(n,0);
for(int i=0;i<n;i++)
{
if(i<p) ret[i]+=a[i];
if(i<q) ret[i]+=mod-b[i];
if(ret[i]>=mod) ret[i]-=mod;
}
return ret;
}
poly operator *(poly a,poly b)
{
const ll g=3;
int len=sz(a)+sz(b);
int m=1;
while(m<sz(a)+sz(b)) m*=2;
a.resize(m);
b.resize(m);
vector<int> rev(m);
for(int i=0;i<m;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)*(m>>1));
for(int i=0;i<m;i++)
if(rev[i]<i)
{
swap(a[i],a[rev[i]]);
swap(b[i],b[rev[i]]);
}
for(int i=1;i<m;i<<=1)
{
ll gn=ksm(g,(mod-1)/i/2);
for(int j=0;j<m;j+=(i<<1))
{
ll g0=1;
for(int k=0;k<i;k++,g0=g0*gn%mod)
{
{
ll x=a[j+k],y=g0*a[i+j+k]%mod;
a[j+k]=(x+y)%mod;
a[i+j+k]=(x+mod-y)%mod;
}
{
ll x=b[j+k],y=g0*b[i+j+k]%mod;
b[j+k]=(x+y)%mod;
b[i+j+k]=(x+mod-y)%mod;
}
}
}
}
for(int i=0;i<m;i++)
a[i]=a[i]*b[i]%mod;
for(int i=0;i<m;i++)
if(rev[i]<i)
swap(a[i],a[rev[i]]);
for(int i=1;i<m;i<<=1)
{
ll gn=ksm(g,(mod-1)/i/2*(mod-2));
for(int j=0;j<m;j+=(i<<1))
{
ll g0=1;
for(int k=0;k<i;k++,g0=g0*gn%mod)
{
ll x=a[j+k],y=g0*a[i+j+k]%mod;
a[j+k]=(x+y)%mod;
a[i+j+k]=(x+mod-y)%mod;
}
}
}
ll val=ksm(m,mod-2);
for(int i=0;i<m;i++)
a[i]=a[i]*val%mod;
a.resize(len-1);
return a;
}
poly inv(poly p,int deg)
{
p.resize(deg);
if(deg==1) return {ksm(p[0],mod-2)};
poly w=inv(p,(deg+1)/2);
poly g=w+w-p*w*w;
g.resize(deg);
return g;
}
poly deriv(poly p)
{
for(int i=0;i<sz(p);i++)
p[i]=p[i]*i%mod;
p.erase(p.begin());
return p;
}
poly integ(poly p)
{
p.insert(p.begin(),0);
for(int i=0;i<sz(p);i++)
p[i]=p[i]*ksm(i,mod-2)%mod;
return p;
}
poly ln(poly p)
{
return integ(deriv(p)*inv(p,sz(p)));
}
poly exp(poly p,int deg)
{
p.resize(deg);
if(deg==1)
return {1};
poly g=exp(p,(deg+1)/2);
g=g*(poly{1}-ln(g)+p);
g.resize(deg);
return g;
}
const poly operator %(poly a,poly b)
{
if(sz(a)<sz(b)) return a;
int n=sz(a),m=sz(b);
int d=n-m+1;
poly a2=a,b2=b;
reverse(a2.begin(),a2.end());
reverse(b2.begin(),b2.end());
a2.resize(d);
b2.resize(d);
poly q=a2*inv(b2,d);
q.resize(d);
reverse(q.begin(),q.end());
q=a-b*q;
q.resize(m-1);
return q;
}
const poly operator /(poly a,poly b)
{
if(sz(a)<sz(b)) return a;
int n=sz(a),m=sz(b);
int d=n-m+1;
poly a2=a,b2=b;
reverse(a2.begin(),a2.end());
reverse(b2.begin(),b2.end());
a2.resize(d);
b2.resize(d);
poly q=a2*inv(b2,d);
q.resize(d);
reverse(q.begin(),q.end());
return q;
}
}
using namespace Polynomial;
ll fact[1001000],rfact[1001000];
ll C(int n,int k)
{
if(k<0||k>n) return 0;
return fact[n]*rfact[k]%mod*rfact[n-k]%mod;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
fact[0]=rfact[0]=1;
for(int i=1;i<1001000;i++)
{
fact[i]=fact[i-1]*i%mod;
rfact[i]=rfact[i-1]*ksm(i,mod-2)%mod;
}
int h,w;
cin>>h>>w;
ll ans=0;
poly f1(w+1),g1(h+1);
for(int i=0;i<h;i++)
g1[h-i-1]=rfact[h-i-1]*rfact[h-i]%mod;
for(int j=0;j<w;j++)
f1[w-j-1]=rfact[w-j-1]*rfact[w-j]%mod;
poly h1=f1*g1;
for(int i=0;i<sz(h1);i++)
ans=(ans+h1[i]*fact[i]%mod*fact[i+1])%mod;
poly f2(h+1),g2(h+1);
for(int i=0;i<h;i++)
f2[h-i]=1;
for(int j=1;j<h;j++)
g2[h-j]=1;
poly h2=f2*g2;
for(int i=h+1;i<sz(h2);i++)
{
int d=i-h;
int d1=w;
ans=(ans+h2[i]*fact[d+d1-2]%mod*fact[d+d1-1]%mod*rfact[d-1]%mod*rfact[d]%mod*rfact[d1-1]%mod*rfact[d1])%mod;
}
poly f3(w+1),g3(w+1);
for(int i=1;i<w;i++)
f3[w-i]=1;
for(int j=0;j<w;j++)
g3[w-j]=1;
poly h3=f3*g3;
for(int i=w+1;i<sz(h3);i++)
{
int d=i-w;
int d1=h;
ans=(ans+h3[i]*fact[d+d1-2]%mod*fact[d+d1-1]%mod*rfact[d-1]%mod*rfact[d]%mod*rfact[d1-1]%mod*rfact[d1])%mod;
}
poly f4(w+1),g4(h+1);
for(int i=1;i<w;i++)
f4[w-i-1]=rfact[w-i-1]*rfact[w-i]%mod;
for(int j=1;j<h;j++)
g4[h-j-1]=rfact[h-j-1]*rfact[h-j]%mod;
poly h4=f4*g4;
for(int i=0;i<sz(h4);i++)
ans=(ans+h4[i]*fact[i]%mod*fact[i+1])%mod;
cout<<(ans+2)%mod<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 105ms
memory: 19244kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 114ms
memory: 19248kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 412ms
memory: 54864kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 113ms
memory: 19432kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 102ms
memory: 19464kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 114ms
memory: 19240kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 106ms
memory: 19256kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 110ms
memory: 19252kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 107ms
memory: 19188kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 106ms
memory: 19200kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 110ms
memory: 19200kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 102ms
memory: 19436kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 109ms
memory: 19272kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 123ms
memory: 20316kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 120ms
memory: 19768kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 121ms
memory: 19868kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 117ms
memory: 19880kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 119ms
memory: 19932kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 121ms
memory: 20064kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 122ms
memory: 20144kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 123ms
memory: 20212kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 123ms
memory: 20236kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 120ms
memory: 20156kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 426ms
memory: 54184kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 250ms
memory: 36540kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 235ms
memory: 35100kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 184ms
memory: 28612kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 419ms
memory: 55632kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 267ms
memory: 37524kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 284ms
memory: 37080kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 222ms
memory: 34728kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 222ms
memory: 34844kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 269ms
memory: 38004kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 426ms
memory: 54836kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 430ms
memory: 56756kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 416ms
memory: 56940kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: 0
Accepted
time: 109ms
memory: 19480kb
input:
1 1
output:
3
result:
ok "3"
Test #38:
score: 0
Accepted
time: 176ms
memory: 27792kb
input:
1 100000
output:
8828237
result:
ok "8828237"
Test #39:
score: 0
Accepted
time: 172ms
memory: 27848kb
input:
100000 2
output:
263711286
result:
ok "263711286"
Test #40:
score: 0
Accepted
time: 114ms
memory: 19252kb
input:
50 50
output:
634767411
result:
ok "634767411"
Extra Test:
score: 0
Extra Test Passed