题目链接：HDU 6589

Tom 有一个长度为 $n$ 的序列 $a$，他想要进行 $k$ 种不同的操作。

对于类型为 $k$ 的操作，他会对于所有的整数 $i \in [1, n]$ 计算出 $b_i = \sum_{j = i - kx} a_j(x \ge 0, 1 \le j \le i)$ 并将 $a_i$ 替换为 $b_i \bmod 998244353$。

他想要求出 $m$ 次操作后的序列。为了减小输出量，你只需要求出 $\bigoplus_{i = 1} ^ {n} i \cdot a_i$ 的值。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 10$，$1 \le n \le 10 ^ 5$，$1 \le m \le 10 ^ 6$，$1 \le a_i \le 10 ^ 9$，$1 \le k \le 3$。

Solution

为了方便计算，我们将序列下标从 $0$ 到 $n - 1$ 标号。

考虑序列 $a, b$ 的生成函数 $A(x), B(x)$，对于操作 $k$ 有：

$$ A(x) = \sum_{i = 0} ^ {n - 1} a_i x ^ i \\ B(x) = A(x) \sum_{i = 0} ^ {\left\lfloor\frac{n}{k}\right\rfloor} x ^ {ik} $$

这样一来操作顺序就无关了，我们直接统计每种操作的次数，然后求出 $\sum x ^ {ik}$ 的若干次幂，

由于 $n, m$ 比较大，因此直接多项式快速幂常数过大无法通过本题。我们可以把 $\left(\sum x ^ {ik}\right) ^ {n}$ 化为 $\sum \binom{n - 1 + i}{i} x ^ {ik}$（考虑组合意义），直接进行一次卷积即可。

时间复杂度：$\mathcal O(T(m + kn \log n))$。

Code

/* 此处省略多项式模板 */

const int N = 1.1e6 + 5;

int T, n, m, fac[N], ifac[N];

void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % MOD;
    ifac[n] = inv(fac[n]);
    for (int i = n; i >= 1; i--) ifac[i - 1] = 1LL * ifac[i] * i % MOD;
}
int C(int n, int m) {
    if (n < m) return 0;
    return 1LL * fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
int main() {
    scanf("%d", &T);
    init(N - 5);
    for (int cs = 1; cs <= T; cs++) {
        scanf("%d%d", &n, &m);
        Vec F(n), cnt(4, 0);
        for (auto &x : F) scanf("%d", &x);
        for (int i = 1, x; i <= m; i++) {
            scanf("%d", &x);
            cnt[x]++;
        }
        for (int i = 1; i <= 3; i++) {
            if (cnt[i] == 0) continue;
            Vec G(n, 0);
            for (int j = 0; i * j < n; j++) G[i * j] = C(cnt[i] - 1 + j, j);
            F = fix(F * G, n);
        }
        long long ans = 0;
        for (int i = 0; i < n; i++) ans ^= 1LL * (i + 1) * F[i];
        printf("%lld\n", ans);
    }
    return 0;
}