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

题目分析

我们先学习一个 SOSDP。

问题：给定长度为

2^n

的数组

F

，对于每个

mask

，计算：

S_{mask}=∑ sub⊆mask F_{sub}

。

其中

sub \subseteq mask

表示

sub

的二进制表示是

mask

的二进制表示的子集。

做法：

dp_{i,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

，执行：

CPP

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

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

CPP

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

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

代码

CPP

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

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

文章操作

题目分析

代码

相关推荐

评论

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