2020 CCPC-Wannafly Winter Camp Day 1 C | Nanako

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$ 条边,那么总边数应该是

不难发现,要最大化总边数其实也就是要最小化 $\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$,所以,我们得出一个很长很长的式子

队友 Luowaterbi 化简了很久很久,结果好像是

太久远了我也不知道是不是对的建议自己化简一遍

然后大力往上套数论分块就过辣!时间复杂度 $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);
}
}

欢迎关注我的其它发布渠道