题意：求正 \(n\) 烷理论上有多少种 \(k\) 氯代物
数据范围：\(1\le t\le 10\)，\(1\le n\le 10^6\)，\(\sum n\le 10^6\)，\(1\le k\le 2n+2\)。
\(本质不同的方案数=\frac{总方案数+强制对称的方案数}{2}\), 总方案数中不对称的算了两次，需要除去，但是对称的只算了一次，所以要补上。求总方案可以枚举 \(A_1\) 和 \(A_n\) 的值，中间部分是经典的容斥。钦定 \(x\) 个 \(A_i \ge 3\)，用剩下的 \(k-A_1-A_n-3x\) 个氯插板法即可，容斥系数为 \((-1)^x\)。强制对称的答案类似，只需要计算一半长度即可，需要根据 \(n\) 和 \(k\) 的奇偶性讨论。
复习
方程 \(x_1+x_2+...+x_n=k (x > 0, x\in \Z)\) 的解数 = \(\tbinom{k-1}{n-1}\)
方程 \(x_1+x_2+...+x_n=k (x \ge 0, x\in \Z)\) 的解数 = \(\tbinom{n+k-1}{n-1}\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e6+5,P=998244353,inv2=499122177;
int T,n,k,fac[N],inv[N];
int C(int n,int m){if(!m)return 1;if(n<m)return 0;return fac[n]*inv[n-m]%P*inv[m]%P;
}
int calc(int x,int y){if(y<0)return 0;if(!x)return !y;int res=0;for(int i=0;i<=min(x,y/3);i++){if(i&1)res=(res-C(y-3*i+x-1,x-1)*C(x,i)%P+P)%P;else res=(res+C(y-3*i+x-1,x-1)*C(x,i)%P)%P;}return res;
}
#undef int
int main(){
#define int long long ios::sync_with_stdio(0),cin.tie(0);fac[0]=fac[1]=inv[0]=inv[1]=1;for(int i=2;i<N;i++)fac[i]=fac[i-1]*i%P,inv[i]=(P-P/i)*inv[P%i]%P;for(int i=2;i<N;i++)inv[i]=inv[i-1]*inv[i]%P;for(cin>>T;T;T--){cin>>n>>k;if(n==1){cout<<1<<'\n';continue;}int ans=0;for(int i=0;i<=3;i++)for(int j=0;j<=3;j++)ans=(ans+calc(n-2,k-i-j))%P;if(n&1){for(int i=0;i<=3;i++){for(int j=0;j<=2;j++){if(!((k+j)&1))ans=(ans+calc(n/2-1,(k-j)/2-i))%P;}}}else {for(int i=0;i<=3;i++){if(!((k+2*i)&1))ans=(ans+calc(n/2-1,(k-2*i)/2))%P;}}cout<<ans*inv2%P<<'\n';}return 0;
}