2020 CCPC Wannafly Winter Camp Day1 C. 染色图
定义一张无向图 G=⟨V,E⟩ 是 k 可染色的当且仅当存在函数 f:V↦{1,2,⋯,k} 满足对于 G 中的任何一条边 (u,v)，都有 f(u)≠f(v)。
定义函数 g(n,k) 的值为所有包含 n 个点的无自环、无重边的 k 可染色无向图中的边数最大值。举例来说，g(3,1)=0,g(3,2)=2,g(3,3)=3。
现在给出三个整数 n,l,r，你需要求解：\((\sum_{i=l}^rg(n,i))mod998244354\)
输入格式：
第一行输入一个整数 \(T(1≤T≤10^3)\)，表示数据组数。
对于每组数据，输入三个整数 \(n,l,r(1≤l≤r≤n≤10^9)\)。
输出格式
对于每组数据，输出一行一个整数表示答案。
输入样例：
5
3 1 1
3 2 2
5 2 4
10 3 9
1000 123 789
输出样例：
0
2
23
280
332539617
时间限制: 1000 ms
内存限制: 256 MB
代码长度限制: 16 KB
分析
n个点，m种颜色，可以分成\(m\)堆，每堆的颜色都是相同的，这样就会有\(n\%m\)堆有\(n/m+1\)个点，\(m-n\%m\)堆有\(n/m\)个点，堆与堆之间的点都是要两两连线的，而对于堆中的点，是不能有连线的，所以就是一个大的完全图减去m个小的完全图。将公式推出来之后，根据数据范围可知不可暴力，可以对每个\(n/m\)的取值，求出对应的\([l,r]\)，然后进行计算。
\[{n \choose 2} - n\%m\times{\lceil{n\over m}\rceil \choose 2}-(m-n\%m)\times {\lfloor{n\over m}\rfloor \choose 2}
\]
\]
\[\Downarrow
\]
\]
\[{n \choose 2} - \lfloor {n\over m}\rfloor \times n + \lfloor {n \over m} \rfloor * (\lfloor {n\over m}\rfloor + 1)*m / 2
\]
\]
枚举\(\lfloor {n\over m} \rfloor\)的值，求出对应的[l,r]
const int mod = 998244353;
int T;
ll n,l,r;
int main()
{
cin >> T;
while(T--){
cin >> n >> l >> r;
ll res = (r - l + 1) * (n * (n-1) / 2 % mod)%mod;
for(int i = l;i <= r;i = d+1){
ll tmp = n / i;
ll d = n / i ? min(n / tmp, r) : r; //求出商为tmp的r
ll num = d - i + 1; //区间长度
res = (res - num * tmp % mod * n % mod + tmp * (tmp + 1) / 2 % mod * num % mod * (d + i) / 2 + mod) % mod;
}
cout << res << endl;
}
return 0;
}