$C.$ 给你一个整数 $N \le 10^{11}$，问有多少对 $A \le B \le C$ 满足 $ABC \le N$

思路：$AAA \le ABC \le N$，得到 $A \le N$，用 $N$ 的最大范围估计， $A \le 5000$，枚举 $A$ 的取值，那么 $BB \le BC \le \frac{N}{A}$，得到 $B \le \sqrt{\frac{N}{A}}$，枚举 $A = 1, 2, …, 5000$，估计一下 $\sum_{A=1}^{5000}\sqrt{\frac{N}{A}} = \sqrt{N} \times \sum_{A=1}^{5000}\sqrt{\frac{1}{A}} < 5000 \times (1 + \frac{1}{\sqrt{2}} + … + \frac{1}{\sqrt{5000}}) < 5000 \times 2 = 10^4$，时间复杂度来自枚举 $A$ 和 $B$，大概是 $5 \times 10^3 \times 10^4 = 5 \times 10^7$，可以接受

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1 << 30;
const int mod = 1e9 + 7;
# define ALL(A) A.begin(),A.end()

void solve() {
    ll n;
    cin >> n;
    ll ans = 0;
    for (ll a = 1; a <= 5000LL; a ++)
        for (ll b = a; b * b <= n / a; b ++)
            ans += max(0LL, n / a / b - b + 1);
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    T = 1;
    // cin >> T;
    while (T --)
        solve();
    return 0;
}

$D.$ 给你 $n$ 个公司，第 $i$ 个公司有 $a_i$ 个人，给定整数 $k$，你可以选择 $k$ 个不同公司，每个公司选一个人，完成一个项目，问最多能完成多少个项目

思路：转化为这样的问题：选择 $k$ 个组，组内可以有重复的元素，组间不可以重复，问组的最大容量是多少。使用二分，假设组的容量是 $x$，枚举每个公司的人数，如果 $a_i \ge x$，就从中取 $x$ 个人，构成一组，否则，记录所有 $a_i < x$ 的 $a_i$ 的总和 $s$，一旦 $s \ge x$，就取出 $x$ 个人构成一组，最后检查能否构成 $k$ 组即可

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1 << 30;
const int mod = 1e9 + 7;
const ll INF = 2e18;
# define ALL(A) A.begin(),A.end()

void solve() {
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> a(n, 0);
    for (int i = 0; i < n; i ++)
        cin >> a[i];
    ll l = 0, r = INF;
    while (l < r) {
        ll mid = l + r + 1 >> 1;
        // thred 总的轮数
        auto check = [&](ll thred) -> bool {
            ll tot = 0, s = 0;
            for (auto& x : a) {
                if (x >= thred) {
                    tot ++;
                    continue;
                }
                s += x;
                if (s >= thred) {
                    tot ++;
                    s -= thred;
                }
            }
            return tot >= k;
        };
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    cout << l << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    T = 1;
    // cin >> T;
    while (T --)
        solve();
    return 0;
}

$E.$ 给你一个字符串 $S$，由字母 $K, E, Y$ 组成，且 $|S| \le 30$，每次操作可以交换相邻的两个字符，给你一个整数 $K$，问至多进行 $K$ 次操作，能得到多少种不同的字符串

思路：字符串全排列的数量为 $\frac{3^{30}}{{cnt_{K} \cdot} cnt_E \cdot cnt_Y}$，其中 $cnt_x$ 代表字符 $x$ 出现的次数，次数都小于 $30$，全排列的复杂度 $> \frac{3^{30}}{30\cdot30\cdot30}$，显然是不可接受的。对于字符串 $S$，最多有交换 $C_{|S|}^2$ 种不同的交换方式，$k$ 的有效值最大是 $C_{|S|}^2$。考虑用 $DP$ 计数，用 $dp[i][j][k][t]$ 表示使用 $i$ 个 K，$j$ 个 E，$k$ 个 Y，交换次数为 $t$ 的方案个数，初始时 $dp[0][0][0][0] = 1$，考虑新增加一个字符时，状态怎么转移，不妨假设新增加的字符是 K，我们已经排好了前 $i - 1 + j + k$ 个字符，包括 $i - 1$ 个 K，$j$ 个 E，$k$ 个 Y，将把 K 放到第 $i + j + k$ 个位置，用一个位置数组，记录每个 K 在原字符串中的位置，可以从中获取要增加的第 $i$ 个 K 的位置，由于 K 之后的 E 和 Y 字符，如果放到 K 前面的话，会导致 K 往后移动，我们需要计算出，有多少个 E 和 Y 排到了 K 的前面，可以用二分和计数来解决，得到 K 移动后的新位置 $P_{now}$，增加字符 K 需要操作的次数为 $num = P_{now} - (i + j + k)$，得到转移方程

• $dp[i][j][k][t] = dp[i][j][k][t] + dp[i - 1][j][k][t - num]$

同理可以增加 E 和 Y，并进行状态转移

复杂度 $O(n^3 \cdot n^2 \cdot log(n)) = O(n^5 \cdot log(n))$

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1 << 30;
const int mod = 1e9 + 7;
const ll INF = 2e18;
# define ALL(A) A.begin(),A.end()

// dp[i][j][k][t] 表示排好了 i 个 "K"，j 个 "E", k 个 "Y"，交换 t 次的方案数
ll dp[35][35][35][910];

void solve() {
    string s;
    int K;
    cin >> s >> K;
    // 最多有 C_n^2 种交换方式
    int n = s.size();
    K = min(K, n * (n - 1) / 2);
    vector<vector<int>> pos(3);
    for (int i = 1; i <= n; i ++) {
        char c = s[i - 1];
        if (c == 'K')
            pos[0].push_back(i);
        else if (c == 'E')
            pos[1].push_back(i);
        else
            pos[2].push_back(i);
    }
    int a = pos[0].size();
    int b = pos[1].size();
    int c = pos[2].size();
    dp[0][0][0][0] = 1;
    // 30 * 30 * 30 * 900
    for (int i = 0; i <= a; i ++)
        for (int j = 0; j <= b; j ++)
            for (int k = 0; k <= c; k ++)
                for (int t = 0; t <= K; t ++) {
                    // 当前放 'K'
                    if (i >= 1) {
                        int p = pos[0][i - 1];
                        int j1 = lower_bound(ALL(pos[1]), p) - pos[1].begin();
                        int j2 = lower_bound(ALL(pos[2]), p) - pos[2].begin();
                        int nowP = p + max(0, j - j1) + max(0, k - j2);
                        int num = nowP - (i + j + k);
                        if (t >= num)
                            dp[i][j][k][t] += dp[i - 1][j][k][t - num];
                    }
                    // 当前放 'E'
                    if (j >= 1) {
                        int p = pos[1][j - 1];
                        int j0 = lower_bound(ALL(pos[0]), p) - pos[0].begin();
                        int j2 = lower_bound(ALL(pos[2]), p) - pos[2].begin();
                        int nowP = p + max(0, i - j0) + max(0, k - j2);
                        int num = nowP - (i + j + k);
                        if (t >= num)
                            dp[i][j][k][t] += dp[i][j - 1][k][t - num];
                    }
                    // 当前放 'Y'
                    if (k >= 1) {
                        int p = pos[2][k - 1];
                        int j0 = lower_bound(ALL(pos[0]), p) - pos[0].begin();
                        int j1 = lower_bound(ALL(pos[1]), p) - pos[1].begin();
                        int nowP = p + max(0, i - j0) + max(0, j - j1);
                        int num = nowP - (i + j + k);
                        if (t >= num)
                            dp[i][j][k][t] += dp[i][j][k - 1][t - num];
                    }
                }
    ll ans = 0;
    for (int t = 0; t <= K; t ++)
        ans += dp[a][b][c][t];
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    T = 1;
    // cin >> T;
    while (T --)
        solve();
    return 0;
}

$F.$ 给你一个 $n \times m$ 的矩阵，$n, m \le 30$，每个位置有一个数 $a_{i,j}$，要求你从 $(1, 1)$ 走到 $(n, m)$，每次只能向右或者向下走，给你一个整数 $K$，问所有路径中，前 $K$ 大值的和，最小是多少

思路：对于第 $K$ 大值问题，可以考虑枚举这个值是多少，假设我们枚举的第 $K$ 大值是 $x$，用 $dp[i][j][k]$ 表示走到 $(i, j)$，且选了 $k$ 个 $\ge x$ 的值时，$\ge x$ 的部分，和的最小值，假设 $a_{i,j} = y$，所有可能的情况如下：

• 当 $y > x$ 时，这个数一定要加上，因为这个数会影响 $x$ 是不是第 $K$ 大的
• 当 $y < x$ 时，这个数不需要加上，因为 $y$ 比第 $K$ 大值 $x$ 小，不会影响前 $K$ 大和
• 当 $y = x$ 时，这个数可选可不选，因为当 $x$ 位于第 $K$ 大位置时，插入 $y$ 不会影响第 $K$ 大值是 $x$，可以把 $y$ 放到 $\ge x$ 的部分占位置，也可以把 $y$ 放到 $\le x$ 的部分，让它对结果不产生影响

综上，状态转移为：

• 如果 $y \ge x$，$dp[i][j][k] = min(dp[i - 1][j][k - 1], dp[i][j - 1][k - 1]) + y$
• 如果 $y \le x$，$dp[i][j][k] = min(dp[i - 1][j][k], dp[i][j - 1][k])$

时间复杂度为 $n^2 \times n^2 \times (n + m) = O(n^5)$，其中 $n = 30$，$30^5 \approx 2\times 10^7 $

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1 << 30;
const int mod = 1e9 + 7;
const ll INF = 2e18;
# define ALL(A) A.begin(),A.end()

void solve() {
    int n, m, K;
    cin >> n >> m >> K;
    vector<vector<int>> a(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            cin >> a[i][j];
    ll ans = INF;
    // 枚举所选数的最小值是多少
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++) {
            // (1, 1) 和 (n, m) 是必选的
            int num = a[i][j];
            vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(m + 1, vector<ll>(K + 1, INF)));
            dp[0][1][0] = dp[1][0][0] = 0;
            for (int o1 = 1; o1 <= n; o1 ++)
                for (int o2 = 1; o2 <= m; o2 ++) {
                    // 可选
                    if (a[o1][o2] >= num) {
                        // 大于等于 num 的个数
                        for (int k = 1; k <= K; k ++) {
                            if (dp[o1 - 1][o2][k - 1] != INF)
                                dp[o1][o2][k] = min(dp[o1][o2][k], dp[o1 - 1][o2][k - 1] + a[o1][o2]);
                            if (dp[o1][o2 - 1][k - 1] != INF)
                                dp[o1][o2][k] = min(dp[o1][o2][k], dp[o1][o2 - 1][k - 1] + a[o1][o2]);
                        }
                    }
                    // 可不选
                    if (a[o1][o2] <= num) {
                        // 大于等于 num 的个数
                        for (int k = 0; k <= K; k ++) {
                            if (dp[o1 - 1][o2][k] != INF)
                                dp[o1][o2][k] = min(dp[o1][o2][k], dp[o1 - 1][o2][k]);
                            if (dp[o1][o2 - 1][k] != INF)
                                dp[o1][o2][k] = min(dp[o1][o2][k], dp[o1][o2 - 1][k]);
                        }
                    }
                }
            ans = min(ans, dp[n][m][K]);
        }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    T = 1;
    // cin >> T;
    while (T --)
        solve();
    return 0;
}

$G.$ 给你两个数 $N \le 10^{12}$，$K \le min(10^6, N)$，求 $C_N^K$ 的约数个数（对 $998244353$ 取模）

思路：关键在于 $K$ 的范围，$K \le 10^6$，$C_N^K = \frac{\prod_{i=N-K+1}^{N}i}{\prod_{i=1}^Ki}$，可以看到分子和分母，区间的长度都是 $K \le 10^6$，根据算术基本定理和组合数学，一个数 $x = p_1^{k_1} p_2^{k_2} … p_m^{k_m}$ 的约数个数为 $\prod_{i=1}^{m}(k_i+1)$，只需关心 $C_N^K$ 分解质因数后，质因数的次方 $k_i$。使用埃式筛，可以用 $O(n \log(n) \log(n))$ 的复杂度，用 $1$ ~ $n$ 内质数去筛一个区间 $[L, R]$，把区间 $[L, R]$ 范围内的数存到下标在 $[1, R - L + 1]$ 的数组 $now$ 中，在埃式筛的第二个循环中，用 $n$ 范围内的质数去筛，对于 $C_N^K$ 的分母，直接取 $n=10^6$，可以把区间内所有的质因数筛出来，而对于分子，我们也取 $n=10^6$，可以筛出所有 $\le 10^6$ 的因子，筛完这部分后，还有一部分 $> 10^6$ 的质因子，对于这部分质因子，我们使用 $now$ 数组，对于所有 $now[i] \neq 1$ 的位置，表示对应的数是 $> 10^6$ 的质数，并且次方为 $1$，也统计到答案中即可。

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1 << 30;
const int mod = 998244353;
const ll INF = 2e18;
const int N = 1000010;
# define ALL(A) A.begin(),A.end()

void solve() {
    ll n, k;
    cin >> n >> k;
    vector<ll> cnt(N, 0);
    vector<ll> now(k + 1, 0);
    for (int i = 1; i <= k; i ++)
        now[i] = i;
    for (int i = 2; i <= N; i ++) {
        for (int j = i; j <= k; j += i) {
            while (now[j] % i == 0) {
                now[j] /= i;
                cnt[i] --;
            }
        }
    }
    // 把数字 [n - k + 1, n] 放到下标 [1, k]
    for (int i = 1; i <= k; i ++)
        now[i] = n - k + i;
    for (int i = 2; i <= N; i ++) {
        // 找到大于等于 n - k + 1 的第一个 i
        ll start = (n - k + 1 + i - 1) / i * i;
        for (ll j = start; j <= n; j += i)
            while (now[j - (n - k)] % i == 0){
                now[j - (n - k)] /= i;
                cnt[i] ++;
            }
    }
    ll ans = 1;
    for (int i = 1; i <= N; i ++)
        ans = ans * (cnt[i] + 1) % mod;
    for (int i = 1; i <= k; i ++)
        if (now[i] != 1)
            ans = ans * 2 % mod;
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    T = 1;
    // cin >> T;
    while (T --)
        solve();
    return 0;
}