赛后一血来写篇题解。

默认下标从 \(0\) 开始。

首先将原序列中的 \(1\) 用 \(0\) 代替，\(-1\) 用 \(1\) 代替，问题转化为，有多少个 \(01\) 序列，满足恰好有 \(\dfrac{n-k}{2}\) 个 \(i\) 满足 \(i,(i+1)\bmod n,(i+2)\bmod n,\cdots,(i+m-1)\bmod n\) 位置上 \(1\) 的个数为奇数。

记 \(b_i=a_i\oplus a_{(i+1)\bmod n}\oplus a_{(i+2)\bmod n}\oplus\cdots\oplus a_{(i+m-1)\bmod n}\)，\(c_i=a_i\oplus a_{(i+m)\bmod n}\)，那么有 \(b_i\oplus b_{i+1}=c_i\)。也就是说 \(b,c\) 之间形成双射。但是我们并不能直接通过对 \(b\) 或者 \(c\) 计数来对 \(a\) 计数，因为我们考虑连边 \(i\to (i+m)\bmod n\)，那么这样图上显然会形成 \(d=\gcd(n,m)\) 个环，每个环环长为 \(l=\dfrac{n}{d}\)，而对于一组 \(c\)，存在一组 \(a\) 与之对应的充要条件是 \(\forall i\in[0,l-1],\oplus_{j\equiv i\pmod{d}}c_j=0\)，换句话说，对于每个 \(i\)，\(c\) 中下标模 \(d\) 余 \(i\) 的位置上的异或和均为 \(0\)，这点容易证明，这里不再赘述。

先考虑只有一个环的情况，打表发现 \(\gcd(n,m)=1\) 的答案为：

• \(\dbinom{n}{k}\)（\(m\) 为奇数）
• \(2\dbinom{n}{k}\)（\(m,k\) 均为偶数）
• \(0\)（\(m\) 为偶数，\(k\) 为奇数）

为什么？先考虑 \(m\) 为奇数的情况。我们考虑所有恰好有 \(k\) 个 \(1\) 的 \(b\) 序列，显然它对应的 \(c\) 序列满足所有数异或和为 \(0\)，因此只要 \(a_0\) 确定了 \(a\) 序列也就确定了。很显然的一件事是，假设 \(a_0=0\) 时候的 \(a\) 序列为 \(a0\)，\(a_0=1\) 时候的 \(a\) 序列为 \(a1\)，那么有 \(a0_i\oplus a1_i=1\)。而因为 \(m\) 是奇数，所以 \(\oplus_{i=0}^{m-1}a0_i,\oplus_{i=0}^{m-1}a1_i\) 中恰好有一者是 \(1\)，这样存在 \(a_0\) 的唯一选择满足我们构造出来的 \(\oplus_{i=0}^{m-1}a_i\) 等于我们选择的 \(b_0\)，这样方案数就是 \(\dbinom{n}{k}\)。

这样一来其实 \(m\) 是奇数，但是 \(\gcd(n,m)\ne 1\) 也很容易解决了。还是考虑对 \(b\) 序列计数，因为总共有 \(d\) 个环，所以相当于，确定 \(b\) 序列以及 \(a_0,a_1,\cdots,a_{d-1}\) 之后 \(a\) 序列就确定了，而正如上文所述，\(b\) 序列能够对应出至少一个 \(a\) 序列的充要条件是对于每个 \(i\)，\(c\) 中下标模 \(d\) 余 \(i\) 的位置上的异或和均为 \(0\)，用 \(b\) 的语言来描述，就是对于所有 \(i\)，\(\bmod d=i\) 的位置上 \(b_i\) 的异或和相同。而 \(a_0\sim a_{d-1}\) 的填法，根据上面 \(\gcd(n,m)=1\) 情况的推论，恰好有一半是合法的，因此有 \(2^{d-1}\) 种。这样用 poly 的语言描述答案就是 \(2^{d-1}[x^k](\sum\limits_{i=0}^l[i\bmod 2=0]\dbinom{l}{i}x^i)^d+[x^k](\sum\limits_{i=0}^l[i\bmod 2=1]\dbinom{l}{i}x^i)^d\)。至于怎么快速求我们最后再讲。

接下来考虑 \(m\) 是偶数的情况，\(\gcd(n,m)\ne 1\) 的情况。我们再打个表发现，如果 \(\dfrac{m}{d}\) 为奇数，那么答案还是上面那个式子。这是对于每个 \(\bmod d\) 的等价类，因为其统计入答案的部分个数是奇数，因此我们改变 \(a_0\) 的值也就改变了 \(b_0\)，改变 \(a_1,a_2,\cdots,a_{d-1}\) 的值同理，因此确定了 \(b\) 以后，确定 \(a_0\sim a_{d-1}\) 的合法方案还是 \(2^{d-1}\)。但是 \(\dfrac{m}{d}\) 为偶数的情况就不是这样了，因为改变 \(a_0\) 不会改变 \(b_0\)，因此这种情况下一组 \(b\) 合法的条件就不再只是对于所有 \(i\)，\(\bmod d=i\) 的位置上 \(b_i\) 的异或和相同，还有个额外条件：每个等价类中 \(0\) 的个数都是奇数（别问我为什么是这个，打表打出来的）。因此答案是 \(2^{d}[x^k](\sum\limits_{i=0}^l[i\bmod 2\ne(\dfrac{n}{d})\bmod 2]\dbinom{l}{i}x^i)^d\)。

现在问题变为计算 \([x^k](\sum\limits_{i=0}^l[i\bmod 2=c]\dbinom{l}{i}x^i)^d\)，其中 \(c\in\{0,1\}\)。很显然的想法是 FFT，但是 \(n\le 5\times 10^6\)，DFT 直接 T 飞，但是我们发现 \(c=0\) 的时候式子是 \((\dfrac{(1+x)^l+(1-x)^l}{2})^d\)，\(c=1\) 时候是 \((\dfrac{(1+x)^l-(1-x)^l}{2})^d\)，于是你其实不用 DFT，计算 \(f(\omega_n^t)\) 时候直接把它带进去快速幂即可。而 IDFT 只用求单点，因此也可以 \(O(n)\)。这样复杂度虽然 \(O(n\log n)\)，但瓶颈只有快速幂，可以通过。

const int MAXN=5e6;
const int MOD=998244353;
const int pr=3;
const int ipr=332748118;
const int INV2=MOD+1>>1;
int qpow(int x,int e){int ret=1;for(;e;e>>=1,x=1ll*x*x%MOD)if(e&1)ret=1ll*ret*x%MOD;return ret;}
int n,m,k,d,fac[MAXN+5],ifac[MAXN+5];
void init_fac(int n){
	for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++)ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
	for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;
}
int binom(int n,int k){
	if(k<0||n<k)return 0;
	return 1ll*fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;
}
int calc(int c){
	int l=n/d,LEN=1;while(LEN<=n)LEN<<=1;
	int w0=qpow(pr,(MOD-1)/LEN),iw0=qpow(ipr,1ll*(MOD-1)/LEN*k%(MOD-1)),res=0;
	for(int i=0,pw=1,ipw=1;i<LEN;i++){
		int pw1=qpow(1+pw,l),pw2=qpow(1-pw+MOD,l);
		int coef0=qpow(1ll*INV2*(pw1+pw2)%MOD,d);
		int coef1=qpow(1ll*INV2*(pw1-pw2+MOD)%MOD,d);
		if(c==0)res=(res+1ll*coef0*ipw)%MOD;
		else if(c==1)res=(res+1ll*coef1*ipw)%MOD;
		else res=(res+1ll*(coef0+coef1)*ipw)%MOD;
		pw=1ll*pw*w0%MOD;ipw=1ll*ipw*iw0%MOD;
	}return 1ll*res*qpow(LEN,MOD-2)%MOD;
}
int main(){
	init_fac(MAXN);
	int qu;scanf("%d",&qu);
	while(qu--){
		scanf("%d%d%d",&n,&m,&k);
		if((k&1)!=(n&1)){puts("0");continue;}
		k=(n-k)/2;d=__gcd(n,m);
		if((m/d)%2)printf("%d\n",1ll*calc(2)*qpow(2,d-1)%MOD);
		else printf("%d\n",1ll*calc(1-(n/d)%2)*qpow(2,d)%MOD);
	}
	return 0;
}