锐评：小学奥数测验
思路
环 + 循环同构，一眼知群论。
考虑类似 P4980 【模板】Pólya 定理，用 Burnside 引理处理。
令 \(G\) 为循环任意次构成的置换群，研究的 “点” 为染色过的环，根据 Burnside 引理知所求为 \(\frac{1}{n} \sum\limits_{i = 1}^n g(i)\)，其中 \(g(i)\) 表示置换为旋转 \(i\) 次时的不动点数量。
因为将长度为 \(n\) 的环旋转 \(i\) 次的置换共有 \(\gcd(i, n)\) 个循环，所以令 \(f(x)\) 表示置换中的循环个数为 \(x\) 时的不动点数量，则 \(g(x) = f(\gcd(x, n))\).
所以答案所求可以写成 \(\frac{1}{n} = \sum\limits_{i = 1}^n g(i) = \frac{1}{n} \sum\limits_{i = 1}^n f(\gcd(i, n)) = \frac{1}{n} \sum\limits_{d \mid n} f(d) \varphi(\frac{n}{d})\)，只需要考虑求出 \(f\) 即可。
不妨给每个循环从 \(0\) 开始标号。根据不动点的定义知同一循环内的点必须颜色相同。
方便起见令 \(x\) 代表循环的长度而非个数。现在求 \(f\) 可以转化成：
对于 \(\frac{n}{x}\) 个长度为 \(x\) 的循环，考虑将其中的 \(\frac{m}{x}\) 的循环全部染成黑色，并且不能有连续 \(k\) 个循环同时是黑色。求所有方案数。
令 \(S(n, m)\) 为：对于长度为 \(n\) 的环，将其中的 \(m\) 个点染成黑色，并且不能有超过 \(k\) 个连续的循环同时是黑色的方案总数。将循环缩成点，上面的问题实际上等价于求 \(S(\frac{n}{x}, \frac{m}{x})\).
因为题目钦定黑色个数，所以可以考虑把这些黑色点取出来，在剩下白点的 \(n - m\) 个空隙（白点成环）中合法地插入。
环上计数不好处理，考虑固定环的起始和结束结点，钦定首尾之间的黑色点个数，这样就可以转化成序列问题。
所以求 \(S(n, m)\) 等价于求 \(\sum\limits_{i = 0}^k (i + 1) R(n - m - 1, m - i)\)，其中 \(R(n, m)\) 表示：在 \(n\) 个点中将 \(m\) 个点染成黑色，要求没有超过连续 \(k\) 个点都是黑色的方案总数。
\(i + 1\) 是 \(i\) 个黑点划分到链首和链尾的方案总数。
所以问题转化成求 \(R(n, m)\).
这里 \(R(n, m)\) 又等价于在 \(n\) 个空盒中放入 \(m\) 个黑球，要求不存在一个盒中有超过 \(k\) 个黑球的方案总数。
这个可以容斥求，具体只需要钦定超过限制的盒子数量即可：
\(R(n, m) = \sum\limits_{i = 0}^{\min(\lfloor \frac{m}{k + 1} \rfloor, n)} (-1)^i {n \choose i} T(n, m - i(k + 1))\)，其中 \(T(n, m)\) 表示将 \(n\) 个相同的球放入 \(m\) 个不同的盒子（允许空盒）的方案总数。
\(T(n, m)\) 直接插板得到 \(T(n, m) = {n + m - 1 \choose n - 1}\).
这里容斥的复杂度是 \(O(\frac{m}{k})\). 求 \(S(n, m)\) 一共需要求 \(k\) 次，所以单次求 \(S(n, m)\) 的复杂度是 \(O(m)\).
观察答案的形式 \(\frac{1}{n} \sum\limits_{d \mid n} f(d) \varphi(\frac{n}{d})\)，发现总复杂度是 \(O(\sigma_1(n))\)，根据数论常识得复杂度为 \(O(n \log n)\).
注意到只有 \(i \mid n, i \mid m\) 的 \(i\) 才能保证 \(S(\frac{n}{i}, \frac{m}{i})\) 有值，所以只需要枚举 \(\gcd(n, m)\) 的因数，总复杂度为 \(O(\sigma_1(\gcd(n, m))\).
代码
#include <cstdio>
using namespace std;
#define min(x, y) (x <= y ? x : y)
const int maxn = 1e5 + 5;
const int mod = 998244353;
int n, m, k, coe;
int fac[maxn], invf[maxn];
int gcd(int a, int b) { return (!b ? a : gcd(b, a % b)); }
int phi(int x)
{
int res = x;
for (int i = 2; i * i <= x; i++)
{
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) res = res / x * (x - 1);
return res;
}
void init()
{
fac[0] = invf[0] = fac[1] = invf[1] = 1;
for (int i = 2; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mod, invf[i] = 1ll * invf[mod % i] * (mod - mod / i) % mod;
coe = invf[n];
for (int i = 1; i <= n; i++) invf[i] = 1ll * invf[i - 1] * invf[i] % mod;
}
int C(int n, int m) { return (n < m ? 0 : 1ll * fac[n] * invf[m] % mod * invf[n - m] % mod); }
int T(int n, int m) { return C(n + m - 1, n - 1); }
int R(int n, int m)
{
int res = 0;
for (int i = 0, nega = 1; i <= min(m / (k + 1), n); i++, nega = -nega)
{
res = (res + 1ll * nega * C(n, i) * T(n, m - i * (k + 1)) % mod) % mod;
res = (res + mod) % mod;
}
return res;
}
int S(int n, int m)
{
if (m <= k) return C(n, m);
int res = 0;
for (int i = 0; i <= k; i++) res = (res + 1ll * (i + 1) * R(n - m - 1, m - i) % mod) % mod;
return res;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
init();
if (n == m) return puts(k == m ? "1" : "0"), 0;
int res = 0, g = gcd(n, m);
for (int i = 1; i * i <= g; i++)
if (g % i == 0)
{
res = (res + 1ll * S(n / i, m / i) * phi(i) % mod) % mod;
if (g / i != i) res = (res + 1ll * S(n / (g / i), m / (g / i)) * phi(g / i) % mod) % mod;
}
res = 1ll * res * coe % mod;
printf("%d\n", res);
return 0;
}