萌新求助
查看原帖
萌新求助
1221384
QwQ_lopgov_QwQ楼主2024/8/10 08:10
//inline int count(int x) { return (!x) ? (0) : (1 + count(x & (x - 1))); }
inline void XOR(int a[], int fwt[], int type)
{
	for (int i = 0; i < n; i++) fwt[i] = a[i];
	//{
	//	if (count(i) & 1) fwt[i] = mod - a[i];
	//	else fwt[i] = a[i];
	//}
	for (int len = 2; len <= n; len <<= 1)
	{
		for (int l = 0, mid = l + (len >> 1) - 1, r = len - 1; l < n; l += len, r += len, mid += len)
		{
			for (int a = l, b = mid + 1; b <= r; a++, b++)
			{
				(fwt[a] *= type) %= mod, (fwt[b] *= type) %= mod;
				(fwt[a] += fwt[b]) %= mod;
				(((fwt[b] += fwt[a] - 3 * fwt[b]) %= mod) += mod) %= mod;
			}
		}
	}
}

定义 a⊕b=popcount(a AND b) mod 2a \oplus b = \text{popcount}(a\ \text{AND}\ b)\ \text{mod}\ 2,令 FWTa,i=∑j⊕i=0aj−∑j⊕i=1ajFWT_{a, i} = \sum \limits_{j\oplus i=0} a_j - \sum \limits_{j\oplus i=1} a_j。

按这个的话,FWTFWT 的初始化不应该是代码中注释掉的部分吗?

2024/8/10 08:10
加载中...