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

Convolution

https://ac.nowcoder.com/acm/contest/11255/H

题目大意

题目重新定义了 $\otimes$ 运算符： $\displaystyle x=\prod p_i^{a_i},y = \prod p_i^{b_i},x \otimes y = \prod p_i^{|a_i-b_i|}$

并且给出长度为 $n(1\le n\le 10^6)$ 的 $a_i$ ，以及常数 $c(1\le c\le10^9)$ ，定义 $\displaystyle b_i=\sum\limits_{1\le j,k\le n, j\otimes k=i}a_jk^c$

我们需要求解 $b_1...b_n$ 的异或和是多少？

Solution

参考题解

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

$\displaystyle x\otimes y=\prod p_i^{|a_i-b_i|}=\prod p_i^{max(a_i.b_i)-min(a_i,b_i)}=\frac{lcm(x,y)}{\gcd(x,y)}=\frac{xy}{\gcd(x,y)}$

从质因数幂次的关系转换到 $x,y$ 和他们对应 $\gcd$ 之间的关系就更加容易处理 $j\otimes k = i$ 这个关系式了。

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

$b_i=\displaystyle \sum\limits_{j=1}^n\sum\limits_{k=1}^n\sum\limits_{\frac{jk}{\gcd(j,k)}=i}a_jk^c$

我们考虑枚举 $g=\gcd(j,k)$

$\displaystyle b_i = \sum\limits_{j=1}^n\sum\limits_{k=1}^n\sum\limits_{g=1}\sum\limits_{\frac{jk}{g^2}=i}a_jk^c$

这样由于最后一个求和条件还是涉及除法，我们再把这个除法消掉，我们设 $x=\frac{j}{g},y=\frac{k}{g}$

$\displaystyle b_i=\sum\limits_{x=1}^n\sum\limits_{y=1}^n\sum\limits_{g=1}^{\min(\frac{n}{x},\frac{n}{y})}\sum\limits_{xy=i}a_{xg}(yg)^c\\$

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

$\displaystyle b_i=\sum\limits_{xy=i}y^c\sum\limits_{g=1}^{\min(\frac{n}{x},\frac{n}{y})}a_{xg}g^c$

计算答案的时候我们枚举 $x$ ，对于 $x*y=n$ 来说，可能的 $y$ 选择长度是 $n+\frac{n}{2}+\frac{n}{3}...+\frac{n}{n}$ ，这个复杂度是 $n\log(n)$ ，然后根据选择的 $y$ ，又可以确定的更新 $i$ 所以全部的 $b_i$ 都可以在 $O(n\log(n))$ 的时间找到。

还需要注意的一点是，由于原先我们定义的是 $\frac{jk}{\gcd(jk)}=i$ ，现在我们改成了 $xy=i$ 那么在 $x,y$ 之间就不能有任何其他的公因子了，例如 $x=2,y=4,g=2$ ，这样的不能现在计算，因为这样的式子后续一定会枚举到 $x=1,y=2,g=4$ ，其实这样这些对应着都是 $j=4,k=8$ ，那么我们就要避免这样的重复计算，我们当且仅当 $\gcd(x,y)=1$ 的时候计算一下 $b_{xy}$ 的值就能保证不多算。

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;
}

2021牛客暑期多校训练营文章被收录于专栏

））补题-ing