题面

7-3 1C. 染色图  

定义一张无向图 , 是 k 可染色的当且仅当存在函数 1 满足对于 G 中的任何一条边 (，都有 (。

定义函数 ( 的值为所有包含 n 个点的无自环、无重边的 k 可染色无向图中的边数最大值。举例来说，(。

现在给出三个整数 ,，你需要求解： m

输入格式：

第一行输入一个整数 (，表示数据组数。

对于每组数据，输入三个整数 ,。

输出格式

对于每组数据，输出一行一个整数表示答案。

输入样例：

5
3 1 1
3 2 2
5 2 4
10 3 9
1000 123 789

 

输出样例：

0
2
23
280
332539617


题解

 

 

 

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 #define RE register
 5 #define FOR(i,a,b) for(RE int i=a;i<=b;++i)
 6 #define ROF(i,a,b) for(RE int i=a;i>=b;--i)
 7 #define sc(n) scanf("%d",&n)
 8 #define ll long long
 9 #define p pair<int,int>
10 
11 using namespace std;
12 
13 const int maxn = 1;
14 const int mod = 998244353;
15 
16 int t, n, l, r;
17 
18 int get(int l, int r)
19 {
20     int k1 = (n - 1) / l + 1, kk1 = (1ll * k1 * (k1 - 1) >> 1) % mod;
21     int k2 = n / l, kk2 = (1ll * k2 * (k2 - 1) / 2) % mod;
22     int len = r - l + 1, lenj = (1ll * (l + r) * len >> 1) % mod;
23     int ans = 1ll * len * kk1 % mod * n % mod;
24     ans = (ans - 1ll * k2 * kk1 % mod * lenj % mod + mod) % mod; 
25     ans = (ans + 1ll * (k2 + 1) * lenj % mod * kk2 % mod) % mod;
26     ans = (ans - 1ll * n * kk2 % mod * len % mod + mod) % mod;
27     return ans;
28 }
29 
30 void work()
31 {
32     ll ans = 0;
33     for(RE int i = l, ne; i <= r&&i < n;i = ne + 1)
34     {
35         ne = min(n / (n / i), (n - 1) / ((n - 1) / i));//给定正整数i和n满足i<=n，使得n/i=n/x成立的最大的x为n/(n/i)
36         ne = min(ne, r);
37         ans = (ans + get(i, ne)) % mod;
38     }
39     ans = (((1ll * (n - 1) * n) >> 1) % mod * (r - l + 1) % mod - ans + mod) % mod;
40     printf("%d\n", ans);
41 }
42 
43 int main()
44 {
45     sc(t);
46     while(t--)
47     {
48         sc(n);sc(l);sc(r);
49         work();
50     }
51     sc(n);
52     return 0;
53 }