牛客Wannafly挑战赛11E 白兔的刁难

传送门

如果大力推单位根反演就可以获得一个 \(k^2logn\) 的好方法

\[ans_{t}=\frac{1}{k}\sum_{i=0}^{k-1}(w_k^{-t})^i(w_k^i+1)^n
\]

(其实可以看出推出来的式子就是 \(IDFT\) 的形式)

或者可以发现这道题就是求 \((1+x)^n\) 的循环卷积的系数

而题目中 \(k\) 一定是 \(2\) 的幂，所以带入 \(w_k^i\) 求出点值然后 \(IDFT\) 即可

\(n\) 直接对 \(mod-1\) 取模就好了

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn(2e6 + 5);

const int mod(998244353);

inline int Pow(ll x, int y) {

	register ll ret = 1;

	for (; y; y >>= 1, x = x * x % mod)

		if (y & 1) ret = ret * x % mod;

	return ret;

}

inline void Inc(int &x, int y) {

	x = x + y >= mod ? x + y - mod : x + y;

}

int n, k, w[maxn], a[maxn], len, r[maxn], inv, l, ans;

char s[1000005];

int main() {

	register int i, j, t, x, y, z;

	scanf(" %s%d", s + 1, &k), len = strlen(s + 1);

	for (i = 1; i <= len; ++i) n = ((ll)n * 10 + s[i] - '0') % (mod - 1);

	w[0] = 1, w[1] = Pow(3, (mod - 1) / k), inv = Pow(k, mod - 2);

	while ((1 << l) < k) ++l;

	for (i = 2; i < k; ++i) w[i] = (ll)w[i - 1] * w[1] % mod;

	for (i = 0; i < k; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));

	for (i = 0; i < k; ++i) a[i] = Pow(w[i] + 1, n), w[i] = Pow(w[i], mod - 2);

	for (i = 0; i < k; ++i) if (i < r[i]) swap(a[i], a[r[i]]);

	for (i = 1; i < k; i <<= 1)

		for (j = 0, t = i << 1; j < k; j += t)

			for (z = 0; z < i; ++z) {

				x = a[j + z], y = (ll)a[j + z + i] * w[k / t * z] % mod;

				a[j + z] = x + y >= mod ? x + y - mod : x + y;

				a[j + z + i] = x - y < 0 ? x - y + mod : x - y;

			}

	for (i = 0; i < k; ++i) a[i] = (ll)a[i] * inv % mod, ans ^= a[i];

	printf("%d\n", ans);

	return 0;

}