2021牛客暑期多校训练营4 H、Convolution

题目大意

题目重新定义了运算符：

并且给出长度为的，以及常数，定义

我们需要求解的异或和是多少？

Solution

参考题解

我们优先就要转换这个符号的定义，不然这个题目就没办法下手了。

从质因数幂次的关系转换到和他们对应之间的关系就更加容易处理这个关系式了。

那么我们重新写出的定义式

我们考虑枚举

这样由于最后一个求和条件还是涉及除法，我们再把这个除法消掉，我们设

然后可以发现最后面的可以提到前面去，最终把式子写成这样

计算答案的时候我们枚举，对于来说，可能的选择长度是，这个复杂度是，然后根据选择的，又可以确定的更新所以全部的都可以在的时间找到。

还需要注意的一点是，由于原先我们定义的是，现在我们改成了那么在之间就不能有任何其他的公因子了，例如，这样的不能现在计算，因为这样的式子后续一定会枚举到，其实这样这些对应着都是，那么我们就要避免这样的重复计算，我们当且仅当的时候计算一下的值就能保证不多算。

const int MOD = 998244353;
const int N = 1e6 + 7;
ll n, c, a[N];
int p[N], f[N], b[N];

inline int add(int a, int b) {
    if (a + b >= MOD)    return a + b - MOD;
    return a + b;
}

int solve() {
    n = read(), c = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        p[i] = qpow(i, c, MOD);
    }
    for (int x = 1; x <= n; ++x) {
        for (int g = 1; g * x <= n; ++g) {
            f[g] = add(f[g - 1], p[g] * a[x * g] % MOD);
        }
        for (int y = 1; x * y <= n; ++y) {
            if (gcd(x, y) == 1) {
                b[x * y] = add(b[x * y], p[y] * f[min(n / x, n / y)] % MOD);
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; ++i)    res ^= b[i];
    print(res);

    return 1;
}