QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#656961 | #9476. 012 Grid | ucup-team3161# | AC ✓ | 116ms | 35252kb | C++20 | 4.3kb | 2024-10-19 13:56:42 | 2024-10-19 13:56:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ulll __uint128_t
#define eb emplace_back
#define po pop_back
#define mid ((l+r)/2)
#define mod FM.reduce
const int N=(1<<23)+5;
int fc[N],invfc[N];
int MOD,g1,lim,lim1,invl,r[N],g[2][N];
struct FastMod
{
ull p,w;FastMod(ull p=2):p(p),w((ull)(((ulll)(1)<<64)/p)) {}
ull reduce(ull x) {ull d=(ull)(((ulll)(w)*x)>>64),r=x-p*d;return r>=p?r-p:r;}
}FM;
void W(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;}
void W(int &x,ll y) {x=mod(x+y);}
void W(int &x,ull y) {x=mod(x+y);}
int W1(int x,int y) {x+=y;return x<MOD?x:x-MOD;}
int qpow(int x,int y)
{int res=1;for(;y;y>>=1,x=mod(1ll*x*x)) if(y&1) res=mod(1ll*res*x);return res;}
void initg()
{
int t=MOD-1;vector<int> p;
for(int i=2;i*i<=t;++i) if(!(t%i)) {p.eb(i);while(!(t%i)) t/=i;}
if(t>1) p.eb(t);
for(int i=2;;++i)
{
bool fl=1;for(auto j:p) if(qpow(i,(MOD-1)/j)==1) {fl=0;break;}
if(fl) {g1=i;break;}
}
}
void init(int n)
{
int l=0;lim=1;while(lim<n) ++l,lim*=2;invl=qpow(lim,MOD-2);
for(int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<l-1);
if(lim>lim1)
{
for(int i=1,t1,t2,t3,t4;i<lim;i*=2)
{
t1=qpow(g1,(MOD-1)/(i*2));t2=qpow(t1,MOD-2);t3=t4=1;
for(int j=0;j<i;++j,t3=mod(1ll*t3*t1),t4=mod(1ll*t4*t2))
g[0][i+j]=t3,g[1][i+j]=t4;
}lim1=lim;
}
}
void init1(int n)
{
fc[0]=1;for(int i=1;i<=n;++i) fc[i]=mod(1ll*fc[i-1]*i);
invfc[n]=qpow(fc[n],MOD-2);
for(int i=n;i;--i) invfc[i-1]=mod(1ll*invfc[i]*i);
}
int bn(int x,int y) {return x<y || y<0?0:mod(mod(1ll*fc[x]*invfc[y])*invfc[x-y]);}
int calc(int i,int j) {return mod(mod(1ll*bn(i+j-2,i-1)*bn(i+j-2,i-1))-mod(1ll*bn(i+j-2,i)*bn(i+j-2,j))+MOD);}
struct Poly
{
vector<int> a;Poly(vector<int> _a={}) {a=_a;}
Poly mv(int x)
{
Poly res;res.a.resize(a.size()+x);
copy(a.begin(),a.end(),res.a.begin()+x);return res;
}
void NTT(bool fl)
{
a.resize(lim);for(int i=0;i<lim;++i) if(i<r[i]) swap(a[i],a[r[i]]);
for(int i=1,t1,t2;i<lim;i*=2) for(int j=0;j<lim;j+=i*2) for(int k=0;k<i;++k)
{
t1=a[j+k];t2=mod(1ll*g[fl][i+k]*a[i+j+k]);
a[j+k]=W1(t1,t2);a[i+j+k]=W1(t1,MOD-t2);
}if(fl) for(int i=0;i<lim;++i) a[i]=mod(1ll*a[i]*invl);
}
Poly operator + (const Poly &t) const
{
Poly res(a);if(a.size()<t.a.size()) res.a.resize(t.a.size());
for(int i=0;i<t.a.size();++i) W(res.a[i],t.a[i]);return res;
}
Poly operator - (const Poly &t) const
{
Poly res(a);if(a.size()<t.a.size()) res.a.resize(t.a.size());
for(int i=0;i<t.a.size();++i) W(res.a[i],MOD-t.a[i]);return res;
}
Poly operator * (Poly t) const
{
int n=a.size()+t.a.size()-1;Poly res(a);init(n);t.NTT(0);res.NTT(0);
for(int i=0;i<lim;++i) res.a[i]=mod(1ll*res.a[i]*t.a[i]);res.NTT(1);
res.a.resize(n);return res;
}
Poly operator * (int t) const
{Poly res(a);for(auto &i:res.a) i=mod(1ll*i*t);return res;}
Poly operator += (const Poly &t) {(*this)=(*this)+t;return *this;}
Poly operator -= (const Poly &t) {(*this)=(*this)-t;return *this;}
Poly operator *= (const Poly &t) {(*this)=(*this)*t;return *this;}
Poly operator *= (int t) {for(auto &i:a) i=mod(1ll*i*t);return (*this);}
Poly inv(int n)
{
if(a.size()<n) a.resize(n);if(n==1) return Poly({qpow(a[0],MOD-2)});
Poly t=inv((n+1)/2),t1(vector<int>(a.begin(),a.begin()+n));
init(n*2-1);t.NTT(0);t1.NTT(0);
for(int i=0;i<lim;++i) t.a[i]=mod((2-mod(1ll*t.a[i]*t1.a[i])+MOD)*t.a[i]);
t.NTT(1);t.a.resize(n);return t;
}
void deriv() {if(!a.empty()) {for(int i=1;i<a.size();++i) a[i-1]=mod(1ll*a[i]*i);a.po();}}
}f,f1;
int n,m,ans;
int main()
{
MOD=998244353;FM=FastMod(MOD);initg();
scanf("%d %d",&n,&m);ans=1;init1(1e6);
f.a.resize(n);f1.a.resize(m);
for(int i=0;i<n;++i) f.a[i]=mod(1ll*invfc[i]*invfc[i]);
for(int i=0;i<m;++i) f1.a[i]=mod(1ll*invfc[i]*invfc[i]);
f*=f1;
for(int i=0;i<f.a.size();++i) W(ans,mod(1ll*f.a[i]*fc[i])*fc[i]);
f.a.resize(n);f1.a.resize(m);
for(int i=0;i<n;++i) f.a[i]=mod(1ll*invfc[i+1]*invfc[i-1]);
for(int i=0;i<m;++i) f1.a[i]=mod(1ll*invfc[i+1]*invfc[i-1]);
f*=f1;
for(int i=0;i<f.a.size();++i) W(ans,mod(1ll*(MOD-f.a[i])*fc[i])*fc[i]);
ans=mod(ans*2);
W(ans,MOD-calc(n,m));
for(int i=1;i<n;++i) W(ans,1ll*calc(i,m)*(n-i-1));
for(int i=1;i<m;++i) W(ans,1ll*calc(n,i)*(m-i-1));
printf("%d\n",ans);return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 14020kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 7ms
memory: 18208kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 100ms
memory: 34392kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 3ms
memory: 18148kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 7ms
memory: 18208kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 11ms
memory: 18144kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 7ms
memory: 18176kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 0ms
memory: 18220kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 7ms
memory: 18148kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 7ms
memory: 18432kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 3ms
memory: 18136kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 11ms
memory: 14048kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 11ms
memory: 18148kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 14ms
memory: 18392kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 13ms
memory: 14384kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 10ms
memory: 18344kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 9ms
memory: 18396kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 14ms
memory: 18400kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 10ms
memory: 18476kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 14ms
memory: 18396kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 14ms
memory: 18476kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 14ms
memory: 18396kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 10ms
memory: 18392kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 107ms
memory: 32616kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 58ms
memory: 24136kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 57ms
memory: 28392kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 33ms
memory: 26956kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 107ms
memory: 34860kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 59ms
memory: 29628kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 62ms
memory: 24108kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 54ms
memory: 23824kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 57ms
memory: 23848kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 59ms
memory: 24616kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 108ms
memory: 35252kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 116ms
memory: 33240kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 114ms
memory: 33704kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: 0
Accepted
time: 7ms
memory: 16176kb
input:
1 1
output:
3
result:
ok "3"
Test #38:
score: 0
Accepted
time: 32ms
memory: 26864kb
input:
1 100000
output:
8828237
result:
ok "8828237"
Test #39:
score: 0
Accepted
time: 32ms
memory: 20836kb
input:
100000 2
output:
263711286
result:
ok "263711286"
Test #40:
score: 0
Accepted
time: 7ms
memory: 18208kb
input:
50 50
output:
634767411
result:
ok "634767411"
Extra Test:
score: 0
Extra Test Passed