51nod1690 区间求和2

Vexoben

Sep 28, 2018

It takes 8 minutes to read this article.

题目链接： 51nod1690 区间求和2

（刷新以获取数学公式）

题意

给出一个长度为 $n$ 的数组 $a$ 。区间 $[L,R]$ 的值为 $\sum_{i = 0}^{R- L}a[L + i]a[R-i]$

求所有长度为质数的区间的值的总和

n ≤ 100000

题解

一个很显然的想法是对于每一个数对 $(i, j)$ 计算他们的贡献

对于长度为 $2$ 的区间，我们先预处理掉。这样剩下的区间长度都是奇数。

用 $f(x)$ 表示不超过 $x$ 的奇质数个数。

那么数对 $(i,j)$ 对答案的贡献就是 $a[i]*a[j]*(f_{min(i + j - 1,\ 2n + 1 - i - j)} -f_{j - i})$

当 $i + j - 1 ≤ n$ ，它等于 $a[i] * a[j] * (f_{i + j - 1} - f_{j - i})$ 当 $i + j - 1 > n$ ，它等于 $a[i] * a[j] * (f_{2n + 1 - i - j} - f_{i - j})$

然后就是FFT计算了。负贡献那部分需要指标翻转。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1 << 18;
const int mod = 1e9 + 7;
const double pi = acos(-1.0);

LL ans = 0, tmp[N];
int n, l, lim, rev[N];
int a[N], f[N], pri[N];
struct cpx {
	double x, y;
	cpx (double _x = 0, double _y = 0) : x(_x), y(_y) {}
	cpx operator + (const cpx &b) const { return cpx(x + b.x, y + b.y); }
	cpx operator - (const cpx &b) const { return cpx(x - b.x, y - b.y); }
	cpx operator * (const cpx &b) const {
		return cpx(x * b.x - y * b.y, x * b.y + y * b.x);
	}
}x[N], y[N], z[N], w[N];

void read(int &x) {
	x = 0;
	char c = getchar();
	while (c > '9' || c < '0') c = getchar();
	while (c >= '0' && c <= '9')
		x = (x << 3) + (x << 1) + c - '0', c = getchar();
}

void init() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		read(a[i]);
	for (int i = 1; i < n; ++i) {
		ans += 2LL * a[i] * a[i + 1];
		ans %= mod;
	}
	for (int i = 2; i <= n + n + 5; ++i) {
		if (pri[i]) continue;
		for (int j = i + i; j <= n + n + 5; j += i) {
			pri[j] = 1;
		}
	}
	for (int i = 3; i <= n + n + 5; ++i)
		f[i] = f[i - 1] + (!pri[i]);
}

void FFT(cpx *a, int n) {
	for (int i = 0; i < n; ++i) {
		if (i < rev[i]) swap(a[i], a[rev[i]]);
	}
	for (int t = n >> 1, i = 2; i <= n; i <<= 1, t >>= 1) {
		int mid = i >> 1;
		for (int j = 0; j < n; j += i) {
			for (int k = 0; k < mid; ++k) {
				cpx x = a[j + k], y = a[j + k + mid] * w[t * k];
				a[j + k] = x + y;
				a[j + k + mid] = x - y;
			}
		}
	}
}

int main() {
	init();
	
	for (int i = 1; i <= n; ++i) {
		x[i] = cpx(a[i], 0);
		y[i] = cpx(a[i], 0);
		z[i] = cpx(a[i], 0);
	}

	lim = 1, l = 0;
	while (lim < n + n + 2) lim <<= 1, ++l;
	for (int i = 0; i < lim; ++i) {
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << l - 1);
		w[i] = cpx(cos(2.0 * pi * i / lim), sin(2.0 * pi * i / lim));
	}
	FFT(x, lim); FFT(y, lim); 	
	for (int i = 0; i < lim; ++i) {
		x[i] = x[i] * y[i];
		w[i].y = -w[i].y;
	}
	FFT(x, lim);
	for (int i = 0; i < lim; ++i) {
		x[i].x /= lim;
		w[i].y = -w[i].y;
		tmp[i] = (LL) (x[i].x + 0.5);
		tmp[i] %= mod;
	}
	for (int i = 3; i <= n + 1; ++i) {
		if (i & 1) continue;
		ans += 1LL * f[i - 1] * tmp[i] % mod;
		ans %= mod;
	}

	for (int i = n + 2; i <= n + n; ++i) {
		if (i & 1) continue;
		ans += 1LL * f[2 * n  + 1 - i] * tmp[i];
		ans %= mod;
	}
	
	memset(x, 0, sizeof x);
	memset(y, 0, sizeof y);
	
	for (int i = 1; i <= n; ++i) {
		x[i] = z[i];
		y[i] = z[i];
	}
	reverse(y + 1, y + n + 1);
	FFT(x, lim); FFT(y, lim);
	for (int i = 0; i < lim; ++i) {
		x[i] = x[i] * y[i];
		w[i].y = -w[i].y;
	}
	FFT(x, lim);
	for (int i = 0; i < lim; ++i) {
		x[i].x /= lim;
		w[i].y = -w[i].y;
		tmp[i] = (LL) (x[i].x + 0.5);
		tmp[i] %= mod;
	}
	for (int i = 0; i < n; ++i) {
		if (i & 1) continue;
		ans -= 2LL * f[i] * tmp[i + n + 1];
		ans %= mod;
	}

	ans = (ans % mod + mod) % mod;
	cout << ans << endl;
	return 0;
}