题目大意
在一个二维直角坐标系内，从((0,0))出发，每一步可以选择向上下左右中的一个方向行进一个长度，有(q)次独立的询问，求(k)步后走到((x,y))的方案数
问题解决
考虑每次走可以选择走(x)方向或者(y)方向，然后减一个(k)，很难分析问题，想办法将两个量独立开来
我们可以将坐标系旋转(45^o),把坐标扩大到原来的(sqrt{2})倍，然后发现，在旋转之后，每一步就变成将横坐标和纵坐标都改变一，于是(x,y)便是独立的了，这一步很妙
然后可以当做两个问题分别求解
设旋转后的坐标是(x',y')显然最后的方案就是
[C_k^{frac{k-x'}{2}} imes C_k^{frac{k-y'}{2}}
]
可以这样来考虑，对于单独一个(x)或(y),总共可以走(k)步，其中需要(x')步走到规定的地方，然后有(k-x')步是无用的，由于最后要在(x')处，所以需要反复横跳，也就是有(frac{k-x'}{2})是可以自己分配的，要在(k)步中选(frac{k-x'}{2})步乱走，也就是(C_k^{frac{k-x'}{2}})了
然后这道题需要取摸所以在算组合数的时候需要算乘法逆元，这里有一步优化预处理出(n!)的逆元
[n!^{-1} imes n=(n-1)!^{-1}
]
证明如下
[n!=1^{-1} imes 2^{-1} imes... imes (n)^{-1}
]
[(n-1)^{-1}!=1^{-1} imes 2^{-1} imes ... imes (n-1)^{-1}
]
所以
[n! imes n=1^{-1} imes 2^{-1} imes... imes (n)^{-1} imes n=(n-1)^{-1}
]
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL TT=998244353;
const int maxn=1e6;
LL Q,Fc[maxn+5],Ni[maxn+5];
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){ch=getchar();}
while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
LL QSM(LL a,LL b){
LL s=1,w=a;
while(b){if(b&1)s=s*w%TT;w=w*w%TT;b>>=1;}
return s;
}
LL C(LL x,LL y){
return (Fc[x]*Ni[y])%TT*Ni[x-y]%TT;
}
int main(){
freopen("puppet.in","r",stdin);
freopen("puppet.out","w",stdout);
Q=read();Fc[0]=1;
for(int i=1;i<=maxn;i++)Fc[i]=(Fc[i-1]*i)%TT;
Ni[maxn]=QSM(Fc[maxn],TT-2);
for(int i=maxn-1;i>=0;i--)Ni[i]=Ni[i+1]*(i+1)%TT;
while(Q--){
int k=read(),x=read(),y=read();
if(((x+y&1)^(k&1))||(x+y>k)){printf("0
");continue;}
int x_=x+y,y_=x-y;
printf("%lld
",C(k,k-x_>>1)*C(k,k-y_>>1)%TT);
}
return 0;
}