ARC124F Chance Meeting
syzf2222
·
·
题解
你告诉我这是铜牌题我是不大相信的，其实红题就了不起了。
改为从 (0,0) 到 (H,W) 写起来方便一些。
考虑枚举相遇的坐标 (a,b)，设 f_{a,b} 为都走到 (a,b) 且是第一次相遇的方案数。
则答案为 \sum f_{a,b}f_{a,W-b}，因为从 (a,b) 出发走到终点也是类似的结构。
考虑容斥。首先钦定会在 (a,b) 相遇，方案数为 \dbinom{H+b+b}{b,b,a,H-a}。
然后考虑枚举真实的第一次相遇点，发现一定是在 (a,i)(i<b) 这些点上。故：
f_{a,b}=\dbinom{H+b+b}{b,b,a,H-a}-\sum_{i<b}f_{a,i}\binom{2b-2i}{b-i}
注意到这个式子把 \dfrac{1}{a!(H-a)!} 提出来就跟 a 没有关系了。
也就是说如果我们计算出 F_b=\dfrac{(H+b+b)!}{b!b!}-\sum\limits_{i<b} F_i\dbinom{2b-2i}{b-i}，则 f_{a,b}=\dfrac{F_b}{a!(H-a)!}。
```
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
const int maxn=1e6+10;
const int mod=998244353;
const int G=3;
const int iG=(mod+1)/3;
inline int ksm(int x,int y){
int res=1;
while(y){
if(y&1)res=1ll*res*x%mod;
x=1ll*x*x%mod;y>>=1;
}return res;
}
#define inf 1e9
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int fac[maxn],ifc[maxn],inv[maxn],tr[maxn];
inline void ntt(int *f,int len,int flg){
for(int i=0;i<len;i++)
if(i<tr[i])swap(f[i],f[tr[i]]);
for(int i=2;i<=len;i<<=1){
int l=i/2,w=ksm(flg?G:iG,(mod-1)/i);
for(int j=0;j<len;j+=i){
int wi=1;
for(int k=j;k<j+l;k++){
int t=1ll*wi*f[k+l]%mod;
f[k+l]=(f[k]-t+mod)%mod;
f[k]=(f[k]+t)%mod;
wi=1ll*wi*w%mod;
}
}
}if(!flg){
int iv=ksm(len,mod-2);
for(int i=0;i<len;i++)
f[i]=1ll*f[i]*iv%mod;
}
}
inline int com(int x,int y){
if(x<0||y<0||x<y)return 0;
return 1ll*fac[x]*ifc[y]%mod*ifc[x-y]%mod;
}
int n,m,f[maxn],ans,kk,A[maxn],B[maxn];
inline void solve(int l,int r){
if(l==r){
f[l]=(f[l]+1ll*fac[n+l+l]*ifc[l]%mod*ifc[l])%mod;
return;
}int mid=(l+r)>>1;solve(l,mid);
int len=1;for(;len<=2*(r-l+1);len<<=1);
for(int i=0;i<len;i++)
tr[i]=(tr[i>>1]>>1)|((i&1)?len>>1:0);
for(int i=0;i<=len;i++)A[i]=B[i]=0;
for(int i=l;i<=mid;i++)A[i-l]=f[i];
for(int i=1;i<=r-l;i++)B[i]=com(i+i,i);
ntt(A,len,1),ntt(B,len,1);
for(int i=0;i<len;i++)A[i]=1ll*A[i]*B[i]%mod;
ntt(A,len,0);
for(int i=mid+1;i<=r;i++)
f[i]=(f[i]-A[i-l]+mod)%mod;
solve(mid+1,r);
}
int main(){
fac[0]=ifc[0]=inv[1]=1;
for(int i=2;i<=N;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=N;i++)fac[i]=1ll*fac[i-1]*i%mod;
for(int i=1;i<=N;i++)ifc[i]=1ll*ifc[i-1]*inv[i]%mod;
n=read()-1,m=read()-1;solve(0,m);
for(int i=0;i<=n;i++)kk=(kk+1ll*ifc[i]*ifc[n-i]%mod*ifc[i]%mod*ifc[n-i])%mod;
for(int i=0;i<=m;i++)
ans=(ans+1ll*f[i]*f[m-i])%mod;
printf("%d\n",1ll*ans*kk%mod);
return 0;
}
```
深深地感到自己的弱小。