QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#659117 | #9476. 012 Grid | ucup-team5318# | AC ✓ | 99ms | 32192kb | C++14 | 2.7kb | 2024-10-19 18:43:53 | 2024-10-19 18:43:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;
const int N=4e5+5, mod=998244353, i2=(mod+1)/2;
int qpow(int x,int y=mod-2){
int res=1;
while(y){
if(y%2) res=res*x%mod;
x=x*x%mod;
y/=2;
}
return res;
}
namespace ntt{
const int LG=19, S=1<<LG;
int P[S];
void init(){
rep(i,0,LG-1){
int stp=qpow(3,(mod-1)>>(i+1));
P[1<<i]=1;
rep(j,(1<<i)+1,(2<<i)-1){
P[j]=P[j-1]*stp%mod;
}
}
}
void DIF(vi &a){
per(i,LG-1,0){
int len=1<<i;
for(int j=0;j<S;j+=len*2){
int idx=len;
rep(k,j,j+len-1){
int A=a[k], B=a[k+len];
a[k]=(A+B)%mod, a[k+len]=(A-B+mod)*P[idx++]%mod;
}
}
}
}
void DIT(vi &a){
rep(i,0,LG-1){
int len=1<<i;
for(int j=0;j<S;j+=len*2){
int idx=len;
rep(k,j,j+len-1){
int A=a[k], B=a[k+len]*P[idx++]%mod;
a[k]=(A+B)%mod, a[k+len]=(A-B+mod)%mod;
}
}
}
int iv=qpow(i2, LG);
reverse(a.begin()+1,a.end());
for(int &x:a){
(x*= iv )%=mod;
}
}
vi mul(vi a,vi b){
a.resize(S);
b.resize(S);
DIF(a); DIF(b);
rep(i,0,S-1){
(a[i]*= b[i] )%=mod;
}
DIT(a);
return a;
}
}
using ntt::mul;
int fac[N], ifac[N];
void init(){
fac[0]=1;
rep(i,1,N-1){
fac[i]=fac[i-1]*i%mod;
}
ifac[N-1]=qpow(fac[N-1]);
per(i,N-1,1){
ifac[i-1]=ifac[i]*i%mod;
}
}
int C(int m,int n){
return n<0 || n>m? 0: fac[m]*ifac[n]%mod*ifac[m-n]%mod;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifndef ONLINE_JUDGE
assert(freopen(".in","r",stdin));
assert(freopen(".out","w",stdout));
#endif
ntt::init();
init();
int n,m; cin>>n>>m;
int ans=0;
// rep(i,0,n-1){
// rep(j,0,m-1){
// (ans+= C(i+j,i)*C(i+j,i)-C(i+j,i-1)*C(i+j,j-1) )%=mod;
// }
// }
vi x(n), y(m), z;
rep(i,0,n-1){
x[i]=ifac[i]*ifac[i]%mod;
}
rep(i,0,m-1){
y[i]=ifac[i]*ifac[i]%mod;
}
z=mul(x,y);
rep(i,0,n+m-1){
(ans+= fac[i]*fac[i]%mod*z[i] )%=mod;
}
rep(i,0,n-1){
x[i]=(i==0? 0: ifac[i-1]*ifac[i+1]%mod);
}
rep(i,0,m-1){
y[i]=(i==0? 0: ifac[i-1]*ifac[i+1]%mod);
}
z=mul(x,y);
rep(i,0,n+m-1){
(ans-= fac[i]*fac[i]%mod*z[i] )%=mod;
}
(ans*= 2 )%=mod;
rep(i,1,n-2){
(ans+= ( C(m-2+i,i-1)*C(m-2+i,i-1)-C(m-2+i,i)*C(m-2+i,i-2) )%mod*(n-1-i) )%=mod;
}
rep(i,1,m-2){
(ans+= ( C(n-2+i,i-1)*C(n-2+i,i-1)-C(n-2+i,i)*C(n-2+i,i-2) )%mod*(m-1-i) )%=mod;
}
ans+= 2;
(ans-= C(n+m-2,n-1)*C(n+m-2,n-1)-C(n+m-2,n-2)*C(n+m-2,m-2) )%=mod;
// (ans+= C())
(ans+= mod )%=mod;
cout<< ans <<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 84ms
memory: 25916kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 80ms
memory: 25916kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 92ms
memory: 32116kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 80ms
memory: 25716kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 88ms
memory: 25708kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 82ms
memory: 25756kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 80ms
memory: 25916kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 79ms
memory: 25740kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 83ms
memory: 25692kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 85ms
memory: 25792kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 86ms
memory: 25912kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 83ms
memory: 25860kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 82ms
memory: 25772kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 84ms
memory: 25972kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 76ms
memory: 25840kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 81ms
memory: 25876kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 76ms
memory: 25932kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 89ms
memory: 25876kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 76ms
memory: 26120kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 86ms
memory: 26008kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 77ms
memory: 25988kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 83ms
memory: 26124kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 88ms
memory: 25896kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 90ms
memory: 31404kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 87ms
memory: 28360kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 87ms
memory: 27888kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 83ms
memory: 27352kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 92ms
memory: 31460kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 87ms
memory: 28980kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 89ms
memory: 28392kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 85ms
memory: 27920kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 83ms
memory: 27868kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 88ms
memory: 29216kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 83ms
memory: 32064kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 82ms
memory: 32152kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 99ms
memory: 32192kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: 0
Accepted
time: 88ms
memory: 25696kb
input:
1 1
output:
3
result:
ok "3"
Test #38:
score: 0
Accepted
time: 86ms
memory: 27316kb
input:
1 100000
output:
8828237
result:
ok "8828237"
Test #39:
score: 0
Accepted
time: 86ms
memory: 27272kb
input:
100000 2
output:
263711286
result:
ok "263711286"
Test #40:
score: 0
Accepted
time: 83ms
memory: 25900kb
input:
50 50
output:
634767411
result:
ok "634767411"
Extra Test:
score: 0
Extra Test Passed