【MX-S3】梦熊周赛 · 提高组 3 & FeOI Round 1

标签：kc 周赛 S3 text sum Round int ll

野心

---

Journey

题意：
\(\text{range}(a, b, c)\) 表示序列

\[[a, a + c, a + 2c, \cdots, a + kc] \]

其中 \(k\) 是满足 \(a + kc < b\) 的最大非负整数。

给定大小为 \(n \le 2 \times 10^7\) 的数组 \(g\)，求

\[\sum_{a = 1}^n\sum_{b = a + 1}^n\sum_{c = 1}^n\sum_{i \in \text{range}(a, b, c)} g_i \]

---

数据范围暗示很明显了，只放过线性做法。

每个 \(g_i\) 会被 \(a + kc = i\) 且 \(b > i\) 的三元组贡献到。

设 \(f(i)\) 表示 \(a + kc = i\) 的 \((a, c)\) 对数

\[\begin{aligned} f(i) &= \sum_{a = 1}^n\sum_{c = 1}^n[a + kc = i]\\ \\ &= n + \sum_{a = 1}^{i - 1}d(i - a)\\ \\ &= n + \sum_{a = 1}^{i - 1}d(i)\\ \end{aligned} \]

因此只要把 \(d(i)\) 筛出来然后做一遍前缀和即可。

最后再乘上 \(b\) 的 \(n - i + 1\) 种取值。

#include<bits/stdc++.h>
#define eb emplace_back
#define ep emplace
using namespace std;

using ll = long long;
constexpr int N = 2e7 + 5, P = 1e9 + 7;

int n; ll A, B, C, g[N];

ll d[N], s[N], iv[64];
int v[N], p[N], idx, c[N];

ll qpow(ll a, int b) {
	ll c = 1;
	while(b) {
		if(b & 1) c = c * a % P;
		b >>= 1;
		a = a * a % P;
	}
	return c;
}

void init() {
	for(int i = 1; i <= 60; ++ i) iv[i] = qpow(i, P - 2);
	d[1] = 1;
	for(int i = 2; i <= n; ++ i) {
		if(!v[i]) {
			c[i] = d[i] = 2;
			p[++ idx] = i;
		}
		for(int j = 1, o; j <= idx && p[j] <= n / i; ++ j) {
			o = i * p[j];
			v[o] = 1;
			if(i % p[j] == 0) {
				d[o] = d[i] * iv[c[i]] % P * (c[i] + 1) % P;
				c[o] = c[i] + 1;
				break;
			}
			d[o] = d[i] * 2 % P;
			c[o] = 2;
		}
	}
	for(int i = 2; i <= n; ++ i) d[i] = (d[i] + d[i - 1]) % P;
}

inline int f(int i) {
	return (n + d[i - 1]) % P;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> A >> B >> C, init();
	cin >> g[n];
	for(int i = n; i > 1; -- i) {
		g[i - 1] = (A * g[i] % P * g[i] + B * g[i] + C) % P;
	}
	ll ans = 0;
	for(int i = 1; i <= n; ++ i) {
		ans = (ans + g[i] * f(i) % P * (n - i + 1)) % P;
	}
	cout << ans;
	return 0;
}

标签：kc,周赛,S3,text,sum,Round,int,ll
From： https://www.cnblogs.com/Luxinze/p/18364892