如果大力推单位根反演就可以获得一个 \(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;
}