QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#658311 | #9476. 012 Grid | ucup-team1004# | AC ✓ | 289ms | 61804kb | C++14 | 2.6kb | 2024-10-19 16:36:46 | 2024-10-19 16:36:47 |
Judging History
answer
#include<bits/stdc++.h>
#define clr(a) memset(a,0,sizeof(a))
using namespace std;
const int N=2.1e6+10,mod=998244353,inv3=(mod+1)/3;
inline int Mod(int a){return a<mod?a:a-mod;}
int l;
typedef long long ll;
ll fastpow(ll a,int b)
{
ll s=1;
for(;b;b>>=1,a=a*a%mod)
if(b&1) s=s*a%mod;
return s;
}
void dif(int *a)
{
ll x,y,wn;
for(int i=l>>1;i;i>>=1)
{
wn=fastpow(3,(mod-1)/i/2);
for(int j=0;j<l;j+=(i<<1))
for(int k=0,w=1;k<i;k++,w=w*wn%mod)
{
x=a[j+k],y=a[i+j+k];
a[j+k]=Mod(x+y);
a[i+j+k]=(x-y+mod)*w%mod;
}
}
}
void dit(int *a)
{
ll x,y,wn;
for(int i=1;i<l;i<<=1)
{
wn=fastpow(inv3,(mod-1)/i/2);
for(int j=0;j<l;j+=(i<<1))
for(int k=0,w=1;k<i;k++,w=w*wn%mod)
{
x=a[j+k],y=1ll*a[i+j+k]*w%mod;
a[j+k]=Mod(x+y),a[i+j+k]=Mod(x-y+mod);
}
}
x=fastpow(l,mod-2);
for(int i=0;i<l;i++) a[i]=a[i]*x%mod;
}
void mul(ll *a,ll *b,int n,int m,ll *c)
{
static int A[N],B[N];
for(l=1;l<=n+m;l<<=1);
for(int i=0;i<l;i++) A[i]=B[i]=0;
for(int i=0;i<=n;i++) A[i]=a[i];
for(int i=0;i<=m;i++) B[i]=b[i];
dif(A),dif(B);
for(int i=0;i<l;i++) A[i]=1ll*A[i]*B[i]%mod;
dit(A);
for(int i=0;i<=n+m;i++) c[i]=A[i];
for(int i=n+m+1;i<l;i++) c[i]=0;
}
ll a[N],b[N],c[N],fac[N],ifac[N];
int n,m;
void init(int n)
{
fac[0]=ifac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
ifac[n]=fastpow(fac[n],mod-2);
for(int i=n-1;i;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
}
void pls(ll &a,ll b){a=(a+b)%mod;}
ll F(int a,int b){return a<0||b<0?0:ifac[a]*ifac[b]%mod*fac[a+b]%mod;}
ll sq(ll x){return x*x%mod;}
int main()
{
ll ans=2;
scanf("%d%d",&n,&m);
init(n+m);
for(int i=0;i<n;i++) a[i]=sq(ifac[i]);
for(int i=0;i<m;i++) b[i]=sq(ifac[i]);
mul(a,b,n-1,m-1,c);
for(int i=0;i<n+m-1;i++)
pls(ans,c[i]*sq(fac[i]));
a[0]=b[0]=0;
for(int i=1;i<n;i++) a[i]=ifac[i-1]*ifac[i+1]%mod;
for(int i=1;i<m;i++) b[i]=ifac[i-1]*ifac[i+1]%mod;
mul(a,b,n-1,m-1,c);
for(int i=2;i<n+m-1;i++)
pls(ans,(mod-c[i])*sq(fac[i]));
clr(a),clr(b);
for(int i=0;i<n-1;i++) a[i]=sq(ifac[i]);
for(int i=0;i<m-1;i++) b[i]=sq(ifac[i]);
mul(a,b,n-1,m-1,c);
for(int i=0;i<n+m-1;i++)
pls(ans,c[i]*sq(fac[i]));
a[0]=b[0]=0;
for(int i=1;i<n-1;i++) a[i]=ifac[i-1]*ifac[i+1]%mod;
for(int i=1;i<m-1;i++) b[i]=ifac[i-1]*ifac[i+1]%mod;
mul(a,b,n-1,m-1,c);
for(int i=2;i<n+m-1;i++)
pls(ans,(mod-c[i])*sq(fac[i]));
clr(a),clr(b);
for(int i=1;i<n;i++)
{
pls(ans,(n-i)*sq(F(i-1,m-1)));
pls(ans,(mod-(n-i))*F(i-2,m)%mod*F(i,m-2));
}
for(int i=1;i<m;i++)
{
pls(ans,(m-i)*sq(F(i-1,n-1)));
pls(ans,(mod-(m-i))*F(i-2,n)%mod*F(i,n-2));
}
printf("%lld\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 44916kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 4ms
memory: 44800kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 289ms
memory: 61656kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 6ms
memory: 44768kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 8ms
memory: 46816kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 4ms
memory: 44856kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 0ms
memory: 44852kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 3ms
memory: 44920kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 3ms
memory: 44728kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 3ms
memory: 44852kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 3ms
memory: 44792kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 5ms
memory: 44764kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 3ms
memory: 44920kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 9ms
memory: 44896kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 8ms
memory: 44996kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 6ms
memory: 50948kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 14ms
memory: 44912kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 8ms
memory: 45012kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 13ms
memory: 44868kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 16ms
memory: 46912kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 13ms
memory: 44908kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 16ms
memory: 45028kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 12ms
memory: 44948kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 285ms
memory: 61676kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 133ms
memory: 55460kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 138ms
memory: 48008kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 69ms
memory: 55288kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 280ms
memory: 61780kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 134ms
memory: 52436kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 143ms
memory: 55748kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 133ms
memory: 55824kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 148ms
memory: 47884kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 146ms
memory: 48584kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 285ms
memory: 61804kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 284ms
memory: 61736kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 284ms
memory: 58260kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: 0
Accepted
time: 7ms
memory: 44924kb
input:
1 1
output:
3
result:
ok "3"
Test #38:
score: 0
Accepted
time: 59ms
memory: 45544kb
input:
1 100000
output:
8828237
result:
ok "8828237"
Test #39:
score: 0
Accepted
time: 72ms
memory: 47764kb
input:
100000 2
output:
263711286
result:
ok "263711286"
Test #40:
score: 0
Accepted
time: 0ms
memory: 44792kb
input:
50 50
output:
634767411
result:
ok "634767411"
Extra Test:
score: 0
Extra Test Passed