【狄利克雷前缀和 / 后缀和】算法学习


1. 狄利克雷前缀和

问题描述

有数列 /(/{a/}/),求数列 /(/{b/}/) 满足

/[b_k = /sum_{i|k} a_i
/]

数列长度 /(n /le 2 /times 10 ^ 7/)。

分析

考虑质因数分解,某个数 /(x = /prod/limits p_{i} ^ {/alpha_i}/), 将其写成行向量 /((/alpha_1,/alpha_2, /dots,/alpha_k)/)。 那么每次乘一个素数 /(p_i/),使得 /(/alpha_i + 1/)。 于是可以用这个向量描述贡献 /(x /to x/cdot p_i/) 。这本质上是个 /(k/) 维前缀和的过程。

可是素数是无限多的,我们考虑状态压缩,发现只需要用原来的数表示这个向量即可。状态数 /(O(n)/)。

P5495
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
typedef long long ll;
typedef double db;
using namespace std;
#define PII pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define fin(haha) freopen(#haha".in","r",stdin);
inline int read(){
	register int x=0,f=0,ch=getchar();
	while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
	while('0'<=ch&&ch<='9')x=x*10+(ch^'0'),ch=getchar();
	return f?-x:x;
}

const int MAX = 2e7 + 5;
#define uint unsigned int
uint seed;
inline uint getnext(){
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return seed;
}
uint a[MAX], b[MAX];
int p[MAX], f[MAX];
void init(int N) {
	for(int i=2;i<=N;++i) {
		if(!f[i]) f[i] = 1,p[++p[0]] = i;
		for(int j=1;j<=p[0] && i*p[j]<=N;++j) {
			f[i*p[j]] = 1;
			if(i % p[j] == 0)break;
		}
	}
}
signed main(){
	int n = read(); cin>>seed;
	for(int i=1;i<=n;++i) a[i] = getnext();
	init(n);
	for(int i=1;i<=p[0];++i) {
		for(int j=1; j*p[i] <= n;++j) {
			a[j * p[i]] += a[j];
		}
	}
	uint ans = 0;
	for(int i=1;i<=n;++i) ans ^= a[i];
	cout << ans << endl;
	return 0;
}

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/tech/pnotes/288888.html

(0)
上一篇 2022年9月11日 23:40
下一篇 2022年9月11日 23:54

相关推荐

发表回复

登录后才能评论