https://atcoder.jp/contests/abc162/tasks

E - Sum of gcd of Tuples (Hard)

 

题意：m个数，每个数取值范围1到K，问所有可能数列的gcd之和。

莫比乌斯反演

枚举所有gcd，计算gcd为该值的可能数。

∑i=1n∑j=1n∑k=1n[gcd=D]=∑i=1n/D∑j=1n/D∑k=1n/D[gcd=1]=∑i=1n/D∑j=1n/D∑k=1n/D∑d∣gcdμ(d)=∑d=1n/Dμ(d)⌊n/Dd⌋⌊n/Dd⌋⌊n/Dd⌋=∑d=1n/Dμ(d)⌊n/Dd⌋3\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n[gcd=D]\\ =\sum_{i=1}^{n/D}\sum_{j=1}^{n/D}\sum_{k=1}^{n/D}[gcd=1]\\ =\sum_{i=1}^{n/D}\sum_{j=1}^{n/D}\sum_{k=1}^{n/D}\sum_{d|gcd}\mu(d)\\ =\sum_{d=1}^{n/D}\mu(d)\lfloor{\frac{n/D}{d}}\rfloor\lfloor{\frac{n/D}{d}}\rfloor\lfloor{\frac{n/D}{d}}\rfloor\\ =\sum_{d=1}^{n/D}\mu(d)\lfloor{\frac{n/D}{d}}\rfloor^3\\

最后一步是因为 d∣gcd  ⟺  d∣i⋀d∣j⋀d∣kd|gcd\iff d|i\bigwedge d|j \bigwedge d|k

再数论分块，预处理莫比乌斯函数前缀和。

以上是m=3的时候，其他情况类似，就改一下幂次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
const ll mod = 1e9 + 7;
int n, K;
ll ans;
int mu[N], p[N], tot;
bool flg[N];
void getMu() {
	mu[1] = 1;
	for (int i = 2; i < N; ++i) {
		if (!flg[i]) p[++tot] = i, mu[i] = -1;
		for (int j = 1; j <= tot && i * p[j] < N; ++j) {
			flg[i * p[j]] = 1;
			if (i % p[j] == 0) {
				mu[i * p[j]] = 0;
				break;
			}
			mu[i * p[j]] = -mu[i];
		}
		mu[i] += mu[i - 1];
	}
}
ll Pow(ll a, int b) {
	ll res = 1;
	while (b) {
		if (b & 1)res = res * a%mod;
		a = a * a%mod;
		b >>= 1;
	}
	return res;
}
ll cal(int k) {
	ll res = 0;
	for (int l = 1, r; l <= k; l = r + 1) {
		r = k / (k / l);
		res = (res + Pow(k / l, n)*(mu[r] - mu[l - 1]) % mod) % mod;
	}
	return res;
}
int main() {
	getMu();
	scanf("%d%d", &n, &K);
	for (int i = 1; i <= K; i++) {
		ans = (ans + i * cal(K / i)) % mod;
	}
	cout << ans << endl;
	return 0;
}

 

F - Select Half

 

题意：n个数选n/2个，不能选相邻的数，求选中数的和的最大值。

dp

显然是个01背包，但是范围太大。

但是由于要选n/2个且不能相邻，所以在每一个位置都有至少要选和最多选几个。算一下发现相差不超过2，所以就用map维护 dp[i][j]dp[i][j] 值，只更新范围内的j。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
const ll mod = 1e9 + 7;
map<int, ll>dp[N];
int n;
ll a[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
	dp[1][1] = a[1]; dp[1][0] = 0;
	dp[2][0] = 0; dp[2][1] = max(a[1], a[2]);
	for (int i = 3; i <= n; i++) {
		int L = n / 2 - (int)ceil(0.5*(n - i + 1)), R = (int)ceil(0.5*i);
		for (int j = L; j <= R; j++) {
			if (!dp[i - 1].count(j) && !dp[i - 2].count(j - 1))continue;
			else if (dp[i - 1].count(j) && !dp[i - 2].count(j - 1))dp[i][j] = dp[i - 1][j];
			else if (dp[i - 2].count(j - 1) && !dp[i - 1].count(j))dp[i][j] = dp[i - 2][j - 1] + a[i];
			else dp[i][j] = max(dp[i - 1][j], dp[i - 2][j - 1] + a[i]);
		}
	}
	printf("%lld\n", dp[n][n / 2]);
	return 0;
}