2020 CCPC-Wannafly Winter Camp Day 1 C

发表于 更新于 分类于 ，

Problem C. 染色图

色图？哪里有色图？

Statement

在一张无向图中，如果存在一种方案，使得给每个结点染上一种颜色 $c_i \in [1,k]$ 后，任意一对相邻结点的颜色不同，则称这张无向图可以 $k$ 染色。在有 $n$ 个节点的、可以 $k$ 染色的所有简单图中，选出边数最多的一个，我们记其边数为 $g(n,k)$。

现在，给定 $n,l,r$，求 $\sum_{i=l}^{r} g(n,i)$ 对 $998244353$ 取余后的结果。有 $T$ 组测试数据。

$1 \leq T \leq 1000$

$1 \leq l \leq r \leq n \leq 10^9$

Solution

考虑一张有 $n$ 个结点染上 $k$ 种颜色，每种颜色使用了 $a_i$ 次。既然只有同色是不能连边的，那么我们把除了同色的团只玩的边全部连起来。一个大小为 $x$ 的团有 $\frac{x(x+1)}2$ 条边，那么总边数应该是
$$
\binom{n}{2} -
\sum_{i=1}^{k} \binom{a_i}{2}
$$
不难发现，要最大化总边数其实也就是要最小化 $\sum_{i=1}^k a_i^2$。为满足这一点，$a_i$ 应当均分。如果 $a_i$ 不是均分，即存在 $i,j$ 使得 $|a_i-a_j| \geq 2$，那么令 $a_i = a_j = \frac{a_i+a_j}{2}$，$\sum_{i=1}^k a_i^2$ 显然变小。所以，$a_i$ 肯定是均分，即有 $n \bmod k$ 个 $a_i$ 等于 $\lfloor \frac nk \rfloor + 1$，剩下的 $k - n \bmod k$ 个 $a_i$ 等于 $\lfloor \frac nk \rfloor$。

又考虑到 $n \bmod k$ 其实就等于 $n - k\lfloor \frac nk \rfloor$，所以，我们得出一个很长很长的式子
$$
g(n, k) = \binom {n}{2} - (n - k\lfloor \frac nk \rfloor) \cdot \binom {\lfloor \frac nk \rfloor + 1} {2} - (k - n + k\lfloor \frac nk \rfloor) \cdot \binom {\lfloor \frac nk \rfloor} {2}
$$
队友 Luowaterbi 化简了很久很久，结果好像是
$$
g(n, k) = \frac 12
(
n^2 - n -
2n \lfloor \frac nk \rfloor +
k \lfloor \frac nk \rfloor +
k \lfloor \frac nk \rfloor ^ 2
)
$$
太久远了我也不知道是不是对的建议自己化简一遍

然后大力往上套数论分块就过辣！时间复杂度 $O(T \sqrt n)$。

Code

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;
const int M = 1e3;
const int mod = 998244353;

ll qpow (ll a, ll b) {
	ll ret = 1;
	while (b) {
		if (b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}

ll inv (ll a) {
	return qpow(a, mod - 2);
}

int main () {
	int T;
	scanf("%d", &T);
	while (T--) {
		ll n, l0, r0;
		scanf("%lld%lld%lld", &n, &l0, &r0);
		ll ans = 0;
		for (int l = l0, r;l <= r0;l = r + 1) {
			ll k = n / l;
			r = min(n / k, r0);
			ll len = r - l + 1;
			ll cur = 0;
			cur += (n * n - n) % mod * len % mod;
			cur -= 2 * n * len % mod * k % mod;
			cur += ((l + r) * len / 2) % mod * k % mod;
			cur += ((l + r) * len / 2) % mod * k % mod * k % mod;
			cur = (cur % mod + mod) % mod;
			ans = (ans + cur) % mod;
		}
		printf("%lld\n", ans * inv(2) % mod);
	}
}