QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#659212 | #9476. 012 Grid | 玩原神的都进队了 (Junlin Ye, Ruichen Dai, Chenghan Li)# | AC ✓ | 66ms | 24292kb | C++20 | 2.7kb | 2024-10-19 19:16:17 | 2024-10-19 19:16:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define mod MOD
mt19937 rnd(time(0));
const int N=1<<19,MOD=998244353;
inline void add(int& x,ll y){ x=(x+y)%mod; }
int inv[N],fac[N],ifac[N];
namespace P {
const int G=3;
int rev[N],w[N<<1];
int ksm(int a,int b=MOD-2) {
int ret=1;
for(;b;a=1ll*a*a%MOD,b=b>>1) if(b&1) ret=1ll*ret*a%MOD;
return ret;
}
void poly_init() {
inv[1]=1;
for(int i=2;i<N;++i) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
fac[0]=ifac[0]=1;
for(int i=1;i<N;++i) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*inv[i]%MOD;
for(int k=1;k<=N;k<<=1) {
int x=ksm(G,(MOD-1)/k); w[k]=1;
for(int i=1;i<k;++i) w[i+k]=1ll*x*w[i+k-1]%MOD;
}
}
int plen(int x) { int y=1; for(;y<x;y<<=1); return y; }
void ntt(int *f,bool idft,int n) {
for(int i=0;i<n;++i) {
rev[i]=(rev[i>>1]>>1);
if(i&1) rev[i]|=n>>1;
}
for(int i=0;i<n;++i) if(rev[i]<i) swap(f[i],f[rev[i]]);
for(int k=2,x,y;k<=n;k<<=1) {
for(int i=0;i<n;i+=k) {
for(int j=i;j<i+k/2;++j) {
x=f[j],y=1ll*f[j+k/2]*w[k+j-i]%MOD;
f[j]=(x+y>=MOD)?x+y-MOD:x+y,f[j+k/2]=(x>=y)?x-y:x+MOD-y;
}
}
}
if(idft) {
reverse(f+1,f+n);
for(int i=0,x=ksm(n);i<n;++i) f[i]=1ll*f[i]*x%MOD;
}
}
void poly_mul(const int *f,const int *g,int *h,int n,int m) {
static int a[N],b[N];
for(int i=0;i<n;++i) a[i]=f[i];
for(int i=0;i<m;++i) b[i]=g[i];
int len=plen(n+m-1);
ntt(a,0,len),ntt(b,0,len);
for(int i=0;i<len;++i) h[i]=1ll*a[i]*b[i]%MOD;
ntt(h,1,len);
memset(a,0,sizeof(int)*len);
memset(b,0,sizeof(int)*len);
}
}
int n,m;
inline constexpr int sqr(int x){ return (ll)x*x%mod; }
inline int binom(int u,int d){
if(u<0||d>u) return 0;
return (ll)fac[u]*ifac[d]%mod*ifac[u-d]%mod;
}
inline int calc(int x,int y){
return (sqr(binom(x+y-2,x-1))-(ll)binom(x+y-2,x)*binom(x+y-2,x-2)%mod+mod)%mod;
}
inline int calc2(int i,int j){
return (ll)sqr(fac[i+j-2])%mod*(i+j-1)%mod*
sqr(ifac[i-1])%mod*sqr(ifac[j-1])%mod*P::ksm(i*j)%mod;
}
int f[N],g[N];
signed main(){
P::poly_init();
ios::sync_with_stdio(false);
// freopen("Otomachi_Una.in","r",stdin);
// freopen("Otomachi_Una.out","w",stdout);
int n,m;
cin>>n>>m;
int ans=2;
for(int i=1;i<n||i<m;i++){
f[i]=(ll)sqr(ifac[i-1])*inv[i]%mod;
}
P::poly_mul(f,f,g,n,m);
for(int i=2;i<=n+m-2;i++){
add(ans,(ll)sqr(fac[i-2])*(i-1)%mod*g[i]%mod*2%mod);
}
// for(int i=1;i<n;i++){
// for(int j=1;j<m;j++){
// assert(calc(i,j)==calc2(i,j));
// add(ans,2*calc2(i,j));
// }
// }
for(int i=1;i<n;i++){
add(ans,(ll)calc(m,i)*(n-i+1)%mod);
}
for(int i=1;i<m;i++){
add(ans,(ll)calc(n,i)*(m-i+1)%mod);
}
add(ans,(ll)calc(n,m));
cout<<ans<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 15ms
memory: 22116kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 11ms
memory: 22180kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 65ms
memory: 24288kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 10ms
memory: 22124kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 10ms
memory: 22236kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 7ms
memory: 22240kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 14ms
memory: 22164kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 13ms
memory: 22232kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 15ms
memory: 22236kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 14ms
memory: 22064kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 7ms
memory: 22180kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 7ms
memory: 22104kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 9ms
memory: 22124kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 15ms
memory: 22192kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 11ms
memory: 22228kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 15ms
memory: 22300kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 15ms
memory: 22228kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 15ms
memory: 22244kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 15ms
memory: 22188kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 11ms
memory: 22132kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 4ms
memory: 22288kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 15ms
memory: 22240kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 12ms
memory: 22304kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 66ms
memory: 24180kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 30ms
memory: 23208kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 30ms
memory: 23144kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 18ms
memory: 22744kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 63ms
memory: 24216kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 35ms
memory: 23188kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 34ms
memory: 23144kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 33ms
memory: 23220kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 33ms
memory: 23224kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 34ms
memory: 23268kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 60ms
memory: 24176kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 65ms
memory: 24164kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 64ms
memory: 24292kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: 0
Accepted
time: 10ms
memory: 20068kb
input:
1 1
output:
3
result:
ok "3"
Test #38:
score: 0
Accepted
time: 18ms
memory: 22576kb
input:
1 100000
output:
8828237
result:
ok "8828237"
Test #39:
score: 0
Accepted
time: 23ms
memory: 22644kb
input:
100000 2
output:
263711286
result:
ok "263711286"
Test #40:
score: 0
Accepted
time: 9ms
memory: 22180kb
input:
50 50
output:
634767411
result:
ok "634767411"
Extra Test:
score: 0
Extra Test Passed