为了方便，不妨先将$n$和$m$都减小1，其意义即为移动的次数
注意到老鼠向下移动和猫向上移动对于第2个条件是等价的，对于第1个条件即要求都恰好移动$n$次，那么对应的方案数即为${2n\choose n}$，乘上此系数后不妨将两种操作都看作仅有老鼠向下移动$2n$次
此时，即猫只能向右移动，因此相遇的位置必然在第$n+1$行
定义$f(x)$表示双方最终位于$(n+1,x+1)$且不存在一次操作后双方在同一个位置上的方案数，枚举双方相遇的位置，不难得到答案即为${2n\choose n}\sum_{i=0}^{m}f(i)f(m-i)$
先不考虑不在同一个位置上的条件，总方案数即为${n+2x\choose x}{n+x\choose n}$，将其记作$g(x)$，对于不合法的方案不妨去枚举其上一次相遇的位置，此时限制即之后不再相遇
具体的，可以看作在坐标系中从$(0,0)$走到$(n,0)$，每一步可以从$(x,y)$移动到$(x+1,y\pm 1)$，求除了起点和终点以外不与$x$轴有公共点的路径数
不难发现这即为$2H_{n-1}$（其中$H$为卡特兰数），也即有$f(x)=g(x)-2\sum_{i=0}^{x-1}H_{x-i-1}g(i)$
时间复杂度为$o(n+m\log m)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 600005 4 #define L (1<<19) 5 #define mod 998244353 6 #define ll long long 7 int n,m,ans,fac[N],inv[N],rev[L],a[L],b[L],g[N],f[N]; 8 int C(int n,int m){ 9 return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod; 10 } 11 int qpow(int n,int m){ 12 int s=n,ans=1; 13 while (m){ 14 if (m&1)ans=(ll)ans*s%mod; 15 s=(ll)s*s%mod; 16 m>>=1; 17 } 18 return ans; 19 } 20 void ntt(int *a,int p){ 21 for(int i=0;i<L;i++) 22 if (i<rev[i])swap(a[i],a[rev[i]]); 23 for(int i=2;i<=L;i<<=1){ 24 int s=qpow(3,(mod-1)/i); 25 if (p)s=qpow(s,mod-2); 26 for(int j=0;j<L;j+=i) 27 for(int k=0,ss=1;k<(i>>1);k++,ss=(ll)ss*s%mod){ 28 int x=a[j+k],y=(ll)a[j+k+(i>>1)]*ss%mod; 29 a[j+k]=(x+y)%mod,a[j+k+(i>>1)]=(x-y+mod)%mod; 30 } 31 } 32 if (p){ 33 int s=qpow(L,mod-2); 34 for(int i=0;i<L;i++)a[i]=(ll)a[i]*s%mod; 35 } 36 } 37 int main(){ 38 scanf("%d%d",&n,&m); 39 n--,m--; 40 fac[0]=inv[0]=inv[1]=1; 41 for(int i=1;i<N;i++)fac[i]=(ll)fac[i-1]*i%mod; 42 for(int i=2;i<N;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod; 43 for(int i=1;i<N;i++)inv[i]=(ll)inv[i-1]*inv[i]%mod; 44 for(int i=0;i<L;i++)rev[i]=(rev[i>>1]>>1)+((i&1)*(L>>1)); 45 for(int i=0;i<=m;i++)a[i]=g[i]=(ll)C(n+(i<<1),i)*C(n+i,n)%mod; 46 for(int i=0;i<m;i++)b[i+1]=(ll)C((i<<1),i)*fac[i]%mod*inv[i+1]%mod; 47 ntt(a,0),ntt(b,0); 48 for(int i=0;i<L;i++)a[i]=(ll)a[i]*b[i]%mod; 49 ntt(a,1); 50 for(int i=0;i<=m;i++)f[i]=(g[i]-2*a[i]%mod+mod)%mod; 51 for(int i=0;i<=m;i++)ans=(ans+(ll)f[i]*f[m-i])%mod; 52 ans=(ll)ans*C((n<<1),n)%mod; 53 printf("%d\n",ans); 54 return 0; 55 }