Submission #1912339
Source Code Expand
#include<vector>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<ctime>
using namespace std;
#define ll long long
#define rep(i,x,y) for(ll i=x;i<y;++i)
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
ll read(){ ll x=0,f=1; char ch=getchar(); for(;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x*f; }
void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
const ll mod=998244353,N=1000010;
ll n,m,inv[N+5],fac[N+5],pre[N+5],ans;
ll C(ll n,ll m){ return fac[n+m]*pre[n]%mod*pre[m]%mod; }
ll get(ll x1,ll y1,ll x2,ll y2){ return (x1<=x2&&y1<=y2)?C(x2-x1,y2-y1):0; }
void add(ll &x,ll y){ x=(x+y)%mod; }
void del(ll &x,ll y){ x=(x-y)%mod; }
ll ppow(ll x,ll k){ ll ans=1; while(k){ if (k&1) ans=ans*x%mod; x=x*x%mod; k>>=1; }return ans; }
int main(){
n=read(); m=read(); if (n>m) swap(n,m); inv[0]=inv[1]=fac[0]=pre[0]=1;
For(i,2,N) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
For(i,1,N) fac[i]=fac[i-1]*i%mod,pre[i]=pre[i-1]*inv[i]%mod;
ll v1=C(n-1,m),v2=C(n,m-1),tmp=0;
For(i,1,n+m){
add(tmp,v1+v2);
i&1?(del(v1,get(0,0,i/2,i/2)*get(i/2,i/2+1,n-1,m)),del(v2,get(0,0,i/2,i/2)*get(i/2+1,i/2,n,m-1)),0):
(add(v1,get(0,0,i/2-1,i/2)*get(i/2,i/2,n-1,m)),add(v2,get(0,0,i/2,i/2-1)*get(i/2,i/2,n,m-1)),0);
add(ans,tmp*inv[i]);
}
writeln((ans*ppow(C(n,m),mod-2)%mod+mod)%mod);
}
/*
struct tr{
ll head[N],nxt[N],vet[N],n,tot;
void insert(ll x,ll y){ nxt[++tot]=head[x]; head[x]=tot; vet[tot]=y; }
void init(){
n=read();
For(i,2,n){
ll x=read(),y=read();
insert(x,y); insert(y,x);
}
}
void dfs(ll x,ll pre){
sz[x]=1; ll ans=0;
for(ll i=head[x];i;i=nxt[i]) if (vet[i]^pre) dfs(vet[i],x),sz[x]+=sz[vet[i]],ans=max(ans,sz[vet[i]]);
ans=max(ans,n-sz[x]); if (ans<=n/2) rt=x;
}
}a,b;
int main(){
a.read(); b.read(); b.dfs(1,0);
}*/
Submission Info
Submission Time |
|
Task |
F - Yes or No |
User |
SHENZHEBEI |
Language |
C++14 (GCC 5.4.1) |
Score |
2000 |
Code Size |
2068 Byte |
Status |
AC |
Exec Time |
62 ms |
Memory |
23552 KB |
Judge Result
Set Name |
Sample |
Partial |
All |
Score / Max Score |
0 / 0 |
1500 / 1500 |
500 / 500 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt |
Partial |
sample_01.txt, sample_02.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_2_01.txt, subtask_2_02.txt, subtask_2_03.txt, subtask_2_04.txt, subtask_2_05.txt, subtask_2_06.txt, subtask_2_07.txt, subtask_2_08.txt, subtask_2_09.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_28.txt, subtask_2_29.txt, subtask_2_30.txt, subtask_2_31.txt, subtask_2_32.txt, subtask_2_33.txt, subtask_2_34.txt, subtask_2_35.txt, subtask_2_36.txt, subtask_2_37.txt, subtask_2_38.txt, subtask_2_39.txt, subtask_2_40.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
33 ms |
23552 KB |
sample_02.txt |
AC |
33 ms |
23552 KB |
sample_03.txt |
AC |
33 ms |
23552 KB |
sample_04.txt |
AC |
33 ms |
23552 KB |
sample_05.txt |
AC |
33 ms |
23552 KB |
subtask_1_01.txt |
AC |
33 ms |
23552 KB |
subtask_1_02.txt |
AC |
33 ms |
23552 KB |
subtask_1_03.txt |
AC |
33 ms |
23552 KB |
subtask_1_04.txt |
AC |
33 ms |
23552 KB |
subtask_1_05.txt |
AC |
33 ms |
23552 KB |
subtask_1_06.txt |
AC |
33 ms |
23552 KB |
subtask_1_07.txt |
AC |
33 ms |
23552 KB |
subtask_1_08.txt |
AC |
33 ms |
23552 KB |
subtask_1_09.txt |
AC |
33 ms |
23552 KB |
subtask_1_10.txt |
AC |
33 ms |
23552 KB |
subtask_1_11.txt |
AC |
33 ms |
23552 KB |
subtask_1_12.txt |
AC |
33 ms |
23552 KB |
subtask_1_13.txt |
AC |
34 ms |
23552 KB |
subtask_1_14.txt |
AC |
35 ms |
23552 KB |
subtask_1_15.txt |
AC |
39 ms |
23552 KB |
subtask_1_16.txt |
AC |
39 ms |
23552 KB |
subtask_1_17.txt |
AC |
39 ms |
23552 KB |
subtask_1_18.txt |
AC |
39 ms |
23552 KB |
subtask_1_19.txt |
AC |
39 ms |
23552 KB |
subtask_1_20.txt |
AC |
39 ms |
23552 KB |
subtask_1_21.txt |
AC |
39 ms |
23552 KB |
subtask_1_22.txt |
AC |
39 ms |
23552 KB |
subtask_1_23.txt |
AC |
39 ms |
23552 KB |
subtask_1_24.txt |
AC |
38 ms |
23552 KB |
subtask_1_25.txt |
AC |
38 ms |
23552 KB |
subtask_2_01.txt |
AC |
33 ms |
23552 KB |
subtask_2_02.txt |
AC |
33 ms |
23552 KB |
subtask_2_03.txt |
AC |
33 ms |
23552 KB |
subtask_2_04.txt |
AC |
62 ms |
23552 KB |
subtask_2_05.txt |
AC |
62 ms |
23552 KB |
subtask_2_06.txt |
AC |
62 ms |
23552 KB |
subtask_2_07.txt |
AC |
62 ms |
23552 KB |
subtask_2_08.txt |
AC |
62 ms |
23552 KB |
subtask_2_09.txt |
AC |
62 ms |
23552 KB |
subtask_2_10.txt |
AC |
62 ms |
23552 KB |
subtask_2_11.txt |
AC |
62 ms |
23552 KB |
subtask_2_12.txt |
AC |
62 ms |
23552 KB |
subtask_2_13.txt |
AC |
62 ms |
23552 KB |
subtask_2_14.txt |
AC |
62 ms |
23552 KB |
subtask_2_15.txt |
AC |
62 ms |
23552 KB |
subtask_2_16.txt |
AC |
62 ms |
23552 KB |
subtask_2_17.txt |
AC |
62 ms |
23552 KB |
subtask_2_18.txt |
AC |
59 ms |
23552 KB |
subtask_2_19.txt |
AC |
56 ms |
23552 KB |
subtask_2_20.txt |
AC |
40 ms |
23552 KB |
subtask_2_21.txt |
AC |
40 ms |
23552 KB |
subtask_2_22.txt |
AC |
41 ms |
23552 KB |
subtask_2_23.txt |
AC |
40 ms |
23552 KB |
subtask_2_24.txt |
AC |
40 ms |
23552 KB |
subtask_2_25.txt |
AC |
40 ms |
23552 KB |
subtask_2_26.txt |
AC |
41 ms |
23552 KB |
subtask_2_27.txt |
AC |
40 ms |
23552 KB |
subtask_2_28.txt |
AC |
41 ms |
23552 KB |
subtask_2_29.txt |
AC |
41 ms |
23552 KB |
subtask_2_30.txt |
AC |
46 ms |
23552 KB |
subtask_2_31.txt |
AC |
49 ms |
23552 KB |
subtask_2_32.txt |
AC |
62 ms |
23552 KB |
subtask_2_33.txt |
AC |
62 ms |
23552 KB |
subtask_2_34.txt |
AC |
62 ms |
23552 KB |
subtask_2_35.txt |
AC |
62 ms |
23552 KB |
subtask_2_36.txt |
AC |
61 ms |
23552 KB |
subtask_2_37.txt |
AC |
46 ms |
23552 KB |
subtask_2_38.txt |
AC |
41 ms |
23552 KB |
subtask_2_39.txt |
AC |
60 ms |
23552 KB |
subtask_2_40.txt |
AC |
44 ms |
23552 KB |