题解：P5495 【模板】Dirichlet 前缀和

zyrqwq · 2025-11-22 23:14:54 · 题解

题目分析

我们先学习一个 SOSDP。

问题：给定长度为 2^n 的数组 F，对于每个 mask，计算：S_{mask}=∑ sub⊆mask F_{sub}。

其中 sub \subseteq mask 表示 sub 的二进制表示是 mask 的二进制表示的子集。

做法：

只固定前 $i$ 个比特位（比特位 $0$ 到 $i-1$），让第 $i$ 位及之后的比特位自由变化时，所有子集的和。转移就很简单了。对于第 $i$ 个比特位（$i$ 从 $0$ 到 $n-1$）： - 如果 $mask$ 的第 $i$ 位是 $0$：$dp_{i + 1,mask}=dp_{i,mask}

（这一位只能是 0，直接继承）

如果 mask 的第 i 位是 1： dp_{i +1,mask}=dp_{i,mask}+dp_{i,mask⊕(1<<i)}
（这一位可以是 1 或 0，分别对应两种子集）

那我们回到这道题。

首先 i|k 等价于在质数指数空间中：i 的每个维度指数 ≤ k 的对应维度指数。

那么，根据唯一分解定理，每个素数看成一维，然后就相当于是子集和，用高维前缀和即可。对每个素数 p，执行：

for(int j = 1; p * j <= n; j++) 
    a[p * j] += a[j];

高维前缀和就差不多是这么写。

for(int i = 0; i < n; i++) {
    for(int S = 0; S < (1 << n); S++) {
        if(S >> i & 1) { // 判第 i 位是不是 1。
            f[S] += f[S ^ (1 << i)];
        }
    }
}

状态压缩，可以自己思考。

代码

#include <bits/stdc++.h>
typedef unsigned int uint;
using namespace std;
uint seed;
inline uint getnext() {
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed;
}
int n;
uint a[20000005], ans;
bool f[20000005];
int main () {
    cin >> n >> seed;
    for(int i = 1; i <= n; i++) a[i] = getnext();
    for(int i = 2; i <= n; i++) {
        if(f[i]) continue;
        for(int j = 1; i * j <= n; j++)
            a[i * j] += a[j], f[j * i] = 1;
    }
    for (int i = 1; i <= n; i++) ans ^= a[i];
    cout << ans;
    return 0;
}