题解 P5495 Dirichlet 前缀和

· · 题解

思路

可以对这道题中的模型进行抽象化，即：对于任意数论函数 \operatorname{f}，积性函数 \operatorname{g}，在 O(n \ln\ln n) 的时间复杂度内求出其狄利克雷卷积 \operatorname{h}。（\operatorname{f}、\operatorname{h} 均用长度为 n 的整数序列表示。）

将每个质数视为一个维度，则狄利克雷卷积就是一个带系数的高维前缀和，考虑分别处理每一个维度 p_i。每个 p^k 都是一个物品，每个物品只转移一次，所以是一个 01 背包（DP 统计所有方案的价值总和）。物品 p^k 的体积为 p^k（这里总体积是每个物品的体积相乘），价值为 g(p^k)（价值也相乘）。核心代码如下：

for(int i = 1; i <= tot; i++) {
    for(int j = n / pri[i]; j >= 1; j--) {
        int t = pri[i];
        for(long long k = j * pri[i]; k <= n; k *= pri[i]) {
            f[k] += f[j] * g[t];
            t *= pri[i];
        }
    }
}

时间复杂度为：

\sum\limits_{p \in prime} \sum\limits_{i=1} \frac{n}{p^i} = O(n \ln \ln n)

（这一解法只利用了 \operatorname{g} 是积性函数的性质，所以可以推广到任意积性函数上，而不仅仅是常函数 1 或其他题解中提到的欧拉函数、莫比乌斯函数等。）

本题为上述模型在 \operatorname{g} = \operatorname{I} 时的特例，核心代码如下：

for(int i = 1; i <= tot; i++) {
    for(int j = n / pri[i]; j >= 1; j--) {
        for(long long k = j * pri[i]; k <= n; k *= pri[i]) {
            f[k] += f[j];
        }
    }
}

也因为在这道题中 \operatorname{g} = \operatorname{I}，所以可以直接跑一个只有 p_i 一个物品的完全背包，常数更小。

for(int j = 1; j <= tot; j++) {
    for(int i = 1; i * pri[j] <= n; i++) {
        f[i * pri[j]] += f[i];
    }
}

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 20000000 + 5;
const int MAXM = 2000000 + 5;

uint seed;
uint f[MAXN];
int pri[MAXM], tot;
bool vis[MAXN];
int n;

inline uint getnext(){
    seed^=seed<<13;
    seed^=seed>>17;
    seed^=seed<<5;
    return seed;
}

void init() {
    for(int i = 2; i <= n; i++) {
        if(!vis[i]) {
            pri[++tot] = i;
        }
        for(int j = 1; j <= tot && i * pri[j] <= n; j++) {
            vis[i * pri[j]] = true;
            if(i % pri[j] == 0) {
                break;
            }
        }
    }
}

int main() {
    scanf("%d%u", &n, &seed);
    for(int i = 1; i <= n; i++) {
        f[i] = getnext();
    }
    init();
    for(int i = 1; i <= tot; i++) {
        for(int j = n / pri[i]; j >= 1; j--) {
            for(long long k = j * pri[i]; k <= n; k *= pri[i]) {
                f[k] += f[j];
            }
        }
    }
    for(int i = 2; i <= n; i++) {
        f[i] ^= f[i - 1];
    }
    printf("%u\n", f[n]);

    return 0;
}