QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#658591 | #9476. 012 Grid | ucup-team5319# | AC ✓ | 82ms | 28352kb | C++14 | 4.6kb | 2024-10-19 17:06:23 | 2024-10-19 17:06:26 |
Judging History
answer
//Linkwish's code
#include<bits/stdc++.h>
#define endl '\n'
#define si inline
#define fi first
#define se second
using namespace std;
typedef long long ll;typedef __int128 li;typedef long double ld;
typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef const int ci;typedef const ll cl;ci iinf=1e9;cl linf=LLONG_MAX;
template<typename T>si bool gmax(T &x,const T y){if(x<y)return x=y,1;return 0;}
template<typename T>si bool gmin(T &x,const T y){if(y<x)return x=y,1;return 0;}
namespace LinkWish{
ci N=(1<<19),M=N,mod=998244353;
si int qpow(int x,int y){
int res=1;
for(;y;x=1ll*x*x%mod,y>>=1)if(y&1)res=1ll*res*x%mod;
return res;
}
si int GMod(ci x){return x>mod?x-mod:x;}
int lena=N,lenb=N;
int A[M],B[M];
int lg,lim,P[M];
si void calclim(){lim=1<<(lg=__lg(lena+lenb)+1);}
si void Init(){
calclim();
for(int i=0,j=1,w;i<lg;i++){
w=qpow(3,(mod-1)>>(i+1)),P[j++]=1;
for(;j<(2<<i);j++)P[j]=1ll*P[j-1]*w%mod;
}
}
si void DIF(int *a){
for(int i=lg-1,len=lim>>1;~i;i--,len>>=1){
for(int j=0;j<lim;j+=(len<<1)){
for(int k=j,x,y,cur=len;k<j+len;k++,cur++){
x=a[k],y=a[k+len];
a[k]=GMod(x+y),a[k+len]=1ll*(x-y+mod)*P[cur]%mod;
}
}
}
}
si void DIT(int *a){
for(int i=0,len=1;i<lg;i++,len<<=1){
for(int j=0;j<lim;j+=(len<<1)){
for(int k=j,x,y,cur=len;k<j+len;k++,cur++){
x=a[k],y=1ll*a[k+len]*P[cur]%mod;
a[k]=GMod(x+y),a[k+len]=GMod(x-y+mod);
}
}
}
reverse(a+1,a+lim);
for(int i=0,inv=qpow(lim,mod-2);i<lim;i++)a[i]=1ll*a[i]*inv%mod;
}
int n=400003;
vector<int> e[N];
int fac[N],inv[N];
si void init(){
fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=qpow(fac[n],mod-2);for(int i=n-1;~i;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
si int C(int x,int y){
if(x<0||y<0||x<y)return 0;
return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int sz[N],cnt[N];
void dfs(int x,int fa){
sz[x]=1;
for(int to:e[x])if(to!=fa)dfs(to,x),sz[x]+=sz[to];
cnt[sz[x]]++,cnt[n-sz[x]]++;
}
void mian(){
init();
int n, m; scanf("%d %d", &n, &m);
lena=n, lenb = m-1, Init();
// for(int i=0;i<=n;i++){
// A[i]=inv[i];
// B[i]=1ll*cnt[n-i+1]*fac[n-i+1]%mod;
// }
A[0] = 0; for (int i = 1; i <= n; i++) A[i] = 1ll * inv[i - 1] * inv[i - 1] % mod;
B[0] = 0; for (int i = 1; i < m; i++) B[i] = 1ll * inv[i - 1] * inv[i - 1] % mod;
DIF(A),DIF(B);
for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%mod;
DIT(A);
int ans = 0;
for (int i = 2; i < n + m; i++) ans = (ans + 1ll * fac[i - 2] * fac[i - 2] % mod * A[i]) % mod;
// printf("%d\n", ans);
memset(A, 0, sizeof A); memset(B, 0, sizeof B);
A[0] = 0; for (int i = 1; i <= n; i++) A[i] = 1ll * inv[i] * (i == 1 ? 0 : inv[i - 2]) % mod;
B[0] = 0; for (int i = 1; i < m; i++) B[i] = 1ll * inv[i] * (i == 1 ? 0 : inv[i - 2]) % mod;
// for (int i = 1; i <= n; i++) printf("@ %d\n", A[i]);
// for (int i = 1; i < m; i++) printf("# %d\n", B[i]);
DIF(A),DIF(B);
for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%mod;
DIT(A);
// for (int i = 2; i < n + m; i++) printf("! %d %lld\n", A[i], 1ll * fac[i - 2] * fac[i - 2] % mod * A[i] % mod);
for (int i = 2; i < n + m; i++) ans = (ans + 1ll * (mod - fac[i - 2]) * fac[i - 2] % mod * A[i]) % mod;
ans = ans * 2 % mod;
for (int d = 1; d <= n; d++) {
int c1 = 1ll * C(d + m - 2, d - 1) * C(d + m - 2, d - 1) % mod;
int c2 = d == 1 ? 0 : int(1ll * C(d + m - 2, d) * C(d + m - 2, d - 2) % mod);
ans = (ans + 1ll * c1 * (n - d + 1)) % mod; ans = (ans + 1ll * (mod - c2) * (n - d + 1)) % mod;
// printf("%d\n", ans);
}
for (int d = 1; d <= m - 2; d++) {
int c1 = 1ll * C(d + n - 2, d - 1) * C(d + n - 2, d - 1) % mod;
int c2 = d == 1 ? 0 : int(1ll * C(d + n - 2, d) * C(d + n - 2, d - 2) % mod);
ans = (ans + 1ll * c1 * (m - d - 1)) % mod; ans = (ans + 1ll * (mod - c2) * (m - d - 1)) % mod;
}
printf("%d\n", (ans + 2) % mod);
}
}
signed main(){
// #ifndef ONLINE_JUDGE
// assert(freopen("in.in","r",stdin));
// #endif
// ios::sync_with_stdio(0);
// cin.tie(0),cout.tie(0);
LinkWish::mian();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 26508kb
input:
2 2
output:
11
result:
ok "11"
Test #2:
score: 0
Accepted
time: 4ms
memory: 28140kb
input:
20 23
output:
521442928
result:
ok "521442928"
Test #3:
score: 0
Accepted
time: 76ms
memory: 27040kb
input:
200000 200000
output:
411160917
result:
ok "411160917"
Test #4:
score: 0
Accepted
time: 6ms
memory: 28316kb
input:
8 3
output:
2899
result:
ok "2899"
Test #5:
score: 0
Accepted
time: 8ms
memory: 27168kb
input:
10 9
output:
338037463
result:
ok "338037463"
Test #6:
score: 0
Accepted
time: 0ms
memory: 27412kb
input:
3 3
output:
64
result:
ok "64"
Test #7:
score: 0
Accepted
time: 9ms
memory: 26500kb
input:
9 4
output:
39733
result:
ok "39733"
Test #8:
score: 0
Accepted
time: 4ms
memory: 27236kb
input:
36 33
output:
545587245
result:
ok "545587245"
Test #9:
score: 0
Accepted
time: 4ms
memory: 27924kb
input:
35 39
output:
62117944
result:
ok "62117944"
Test #10:
score: 0
Accepted
time: 0ms
memory: 26300kb
input:
48 10
output:
264659761
result:
ok "264659761"
Test #11:
score: 0
Accepted
time: 4ms
memory: 26484kb
input:
46 30
output:
880000821
result:
ok "880000821"
Test #12:
score: 0
Accepted
time: 6ms
memory: 28352kb
input:
25 24
output:
280799864
result:
ok "280799864"
Test #13:
score: 0
Accepted
time: 4ms
memory: 27680kb
input:
17 10
output:
624958192
result:
ok "624958192"
Test #14:
score: 0
Accepted
time: 7ms
memory: 26840kb
input:
4608 9241
output:
322218996
result:
ok "322218996"
Test #15:
score: 0
Accepted
time: 6ms
memory: 27048kb
input:
3665 6137
output:
537704652
result:
ok "537704652"
Test #16:
score: 0
Accepted
time: 3ms
memory: 27036kb
input:
4192 6186
output:
971816887
result:
ok "971816887"
Test #17:
score: 0
Accepted
time: 9ms
memory: 26512kb
input:
4562 4403
output:
867628411
result:
ok "867628411"
Test #18:
score: 0
Accepted
time: 9ms
memory: 28156kb
input:
8726 3237
output:
808804305
result:
ok "808804305"
Test #19:
score: 0
Accepted
time: 5ms
memory: 26560kb
input:
5257 8166
output:
488829288
result:
ok "488829288"
Test #20:
score: 0
Accepted
time: 6ms
memory: 27480kb
input:
8013 7958
output:
215666893
result:
ok "215666893"
Test #21:
score: 0
Accepted
time: 0ms
memory: 26844kb
input:
8837 5868
output:
239261227
result:
ok "239261227"
Test #22:
score: 0
Accepted
time: 10ms
memory: 28276kb
input:
8917 5492
output:
706653412
result:
ok "706653412"
Test #23:
score: 0
Accepted
time: 0ms
memory: 26852kb
input:
9628 5378
output:
753685501
result:
ok "753685501"
Test #24:
score: 0
Accepted
time: 75ms
memory: 26912kb
input:
163762 183794
output:
141157510
result:
ok "141157510"
Test #25:
score: 0
Accepted
time: 35ms
memory: 26984kb
input:
83512 82743
output:
114622013
result:
ok "114622013"
Test #26:
score: 0
Accepted
time: 33ms
memory: 26904kb
input:
84692 56473
output:
263907717
result:
ok "263907717"
Test #27:
score: 0
Accepted
time: 22ms
memory: 27388kb
input:
31827 74195
output:
200356808
result:
ok "200356808"
Test #28:
score: 0
Accepted
time: 73ms
memory: 28040kb
input:
189921 163932
output:
845151158
result:
ok "845151158"
Test #29:
score: 0
Accepted
time: 36ms
memory: 27420kb
input:
27157 177990
output:
847356039
result:
ok "847356039"
Test #30:
score: 0
Accepted
time: 38ms
memory: 26776kb
input:
136835 39390
output:
962822638
result:
ok "962822638"
Test #31:
score: 0
Accepted
time: 38ms
memory: 26880kb
input:
118610 18795
output:
243423874
result:
ok "243423874"
Test #32:
score: 0
Accepted
time: 38ms
memory: 27724kb
input:
122070 19995
output:
531055604
result:
ok "531055604"
Test #33:
score: 0
Accepted
time: 40ms
memory: 28164kb
input:
20031 195670
output:
483162363
result:
ok "483162363"
Test #34:
score: 0
Accepted
time: 82ms
memory: 27524kb
input:
199992 199992
output:
262099623
result:
ok "262099623"
Test #35:
score: 0
Accepted
time: 82ms
memory: 27596kb
input:
200000 199992
output:
477266520
result:
ok "477266520"
Test #36:
score: 0
Accepted
time: 77ms
memory: 28148kb
input:
199999 199996
output:
165483205
result:
ok "165483205"
Test #37:
score: 0
Accepted
time: 4ms
memory: 27876kb
input:
1 1
output:
3
result:
ok "3"
Test #38:
score: 0
Accepted
time: 24ms
memory: 26776kb
input:
1 100000
output:
8828237
result:
ok "8828237"
Test #39:
score: 0
Accepted
time: 21ms
memory: 27148kb
input:
100000 2
output:
263711286
result:
ok "263711286"
Test #40:
score: 0
Accepted
time: 0ms
memory: 27036kb
input:
50 50
output:
634767411
result:
ok "634767411"
Extra Test:
score: 0
Extra Test Passed