striving & singing
从今天起开始停课，每天 7 个小时用来睡觉，1 个小时用来吃饭、活动和其他零碎事情，剩下 16 个小时全部用来卷。
https://www.luogu.com.cn/problem/P1005
不同行之间互不影响，那么可以设$dp[x][i][j]$表示第 x 行取了前 i 个数和后 j 个数时这一行的最大分数，那么有：
$$dp[x][i][j]=\max(dp[x][i-1][j]+2^{m-(j-i+1)}a[x][i-1],dp[x][i][j+1]+2^{m-(j-i+1)}a[x][j+1])$$
然后还得写高精。注意高精的写法，在比较大小时比较两数的位数，因为压了位所以不能直接比较数组的长度，需要长度 -1 乘 8 再加上末位的位数。另外加法乘法的写法最好记下来，现场口胡老是写错细节。
#include<cstdio>
#include<cstring>
int n, m, a[85][85];
inline int max(int a, int b) { return a > b ? a : b; }
inline int bit(int x) {
int ans = 0;
for (; x; x /= 10) ans++;
return ans;
}
struct integer {
int a[7], n;
integer(int x = 0) {
memset(a, 0, sizeof a);
if (!x) { n = 1; return; }
for (int i = 1; x; x /= (int)1e8, i++) a[i] = x % (int)1e8, n = i;
}
inline int& operator [] (const int &idx) { return a[idx]; }
inline bool operator < (integer b) const {
if (((n - 1) * 8 + bit(a[n])) ^ ((b.n - 1) * 8 + bit(b[n]))) return ((n - 1) * 8 + bit(a[n])) < ((b.n - 1) * 8 + bit(b[n]));
for (int i = n; i >= 1; i--)
if (a[i] ^ b[i]) return a[i] < b[i];
return false;
}
inline integer operator + (integer b) {
integer ans;
for (int i = 1; i <= max(n, b.n); i++) {
ans[i + 1] += (ans[i] + a[i] + b[i]) / (int)1e8;
ans[i] = (ans[i] + a[i] + b[i]) % (int)1e8;
}
ans.n = max(n, b.n);
while (ans[ans.n + 1]) ans.n++;
return ans;
}
inline integer operator * (integer b) {
integer ans;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= b.n; j++) {
ans[i + j] += (ans[i + j - 1] + (long long)a[i] * b[j]) / (int)1e8;
ans[i + j - 1] = (ans[i + j - 1] + (long long)a[i] * b[j] % (int)1e8) % (int)1e8;
}
ans.n = n + b.n - 1;
while (ans[ans.n + 1]) ans.n++;
return ans;
}
inline void print() {
bool fst = true;
if (!n) printf("0");
for (int i = n; i >= 1; i--) {
if (fst) printf("%d", a[i]), fst = false;
else printf("%08d", a[i]);
}
printf("\n");
}
}int2(2), dp[85][85][85], ans;
inline integer pwr(integer x, int k) {
integer ans(1);
for (; k; x = x * x, k >>= 1)
if (k & 1) ans = ans * x;
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
for (int x = 1; x <= n; x++)
for (int l = m - 1; l >= 0; l--)
for (int i = 1; i + l - 1 <= m; i++) {
int j = i + l - 1, t = m - l;
integer s;
if (i > 1) {
s = dp[x][i - 1][j] + *(new integer(a[x][i - 1])) * pwr(int2, t);
if (dp[x][i][j] < s) dp[x][i][j] = s;
}
if (j < m) {
s = dp[x][i][j + 1] + *(new integer(a[x][j + 1])) * pwr(int2, t);
if (dp[x][i][j] < s) dp[x][i][j] = s;
}
}
for (int x = 1; x <= n; x++) {
integer s;
for (int i = 1; i <= m; i++)
if (s < dp[x][i][i - 1]) s = dp[x][i][i - 1];
ans = ans + s;
}
ans.print();
return 0;
}https://www.luogu.com.cn/problem/P1858
背包九讲里讲得挺透彻的。一般求 DP 的前 k 优解，可以多开一维表示这个状态的第 k 优解，然后考虑这个状态由哪些状态转移来，由于多开的这一维对应存的值大小是递增的，所以可以用类似归并排序的方法合并那些数组，复杂度会乘上一个 k 。
#include<cstdio>
int k, m, n, dp[2][5010][55], v[210], w[210], ans;
int main() {
scanf("%d%d%d", &k, &m, &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);
for (int j = m; j >= 0; j--)
for (int p = 1; p <= k; p++) dp[1][j][p] = -0x3fffffff;
dp[1][0][1] = 0;
int cur = 0;
for (int i = 1; i <= n; i++, cur ^= 1) {
for (int j = m; j >= 0; j--) {
int cur1 = 1, cur2 = 1;
for (int p = 1; p <= k; p++) {
if (j >= v[i]) {
if (dp[cur ^ 1][j][cur1] > dp[cur ^ 1][j - v[i]][cur2] + w[i]) dp[cur][j][p] = dp[cur ^ 1][j][cur1], cur1++;
else dp[cur][j][p] = dp[cur ^ 1][j - v[i]][cur2] + w[i], cur2++;
}
else dp[cur][j][p] = dp[cur ^ 1][j][p];
}
}
}
for (int i = 1; i <= k; i++) ans += dp[cur ^ 1][m][i];
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P1174
https://www.luogu.com.cn/problem/P1108
求最长下降子序列长度和方案数。设$f[i]$表示以 i 结尾的最长下降子序列长度，$g[i]$表示最长下降子序列的方案数。
仍然使用$O(n^2)$的朴素 DP 做法，对于每个 i ，枚举 i 前面的位置 j，若$a[j]>a[i]$则可以转移。两种方案相同的条件是构成相同，而不是位置相同，所以还需要去重。
考虑 i 前面的某个位置 j ，如果$a[j]=a[i]$，那么如果$f[j]<f[i]$，显然 j 不如 i 优，对 i 后面的位置都没有贡献，所以可以直接把 j 位置清空；如果$f[j]=f[i]$，那么以 j 结尾和以 i 结尾的最长下降子序列的构成一定相同，所以也要把 j 位置清空；而$f[j]>f[i]$这种情况不存在。综上所述，当 i 前面有位置 j 使得$a[j]=a[i]$时，可以直接把 j 位置清空，这样就满足了去重的要求。
#include<cstdio>
int n, a[5010], f[5010], g[5010], ans1, ans2;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) {
f[i] = g[i] = 1;
for (int j = 1; j < i; j++) {
if (a[j] > a[i]) {
if (f[j] + 1 > f[i]) {
f[i] = f[j] + 1;
g[i] = g[j];
}
else if (f[j] + 1 == f[i]) g[i] += g[j];
}
else if (a[j] == a[i]) f[j] = g[j] = 0;
}
}
for (int i = 1; i <= n; i++) {
if (f[i] > ans1) { ans1 = f[i], ans2 = g[i]; }
else if (f[i] == ans1) { ans2 += g[i]; }
}
printf("%d %d\n", ans1, ans2);
return 0;
}https://www.luogu.com.cn/problem/P4342
显然是一个区间 DP，要求的是最大值，但因为乘法负负得正，所以最大值也可能由两个负数最小值相乘转移得出。因此可以设$f[i][j]$表示区间$[i,j]$合并出的最大值，$g[i][j]$表示最小值，然后分各种情况讨论即可。
注意 f 和 g 分别要初始化为$-\inf$和$\inf$。
#include<cstdio>
#include<vector>
#include<cstring>
int n, a[110], f[110][110], g[110][110], ans = -0x3fffffff;
char op[110];
std::vector<int> ans2;
inline char readchar() {
char c = getchar();
while (c == ' ' || c == '\n' || c == '\r') c = getchar();
return c;
}
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) op[i] = readchar(), scanf("%d", &a[i]), op[n + i] = op[i], a[n + i] = a[i];
memset(f, -0x3f, sizeof f); memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n + n; i++) f[i][i] = g[i][i] = a[i];
for (int l = 1; l <= n; l++)
for (int i = 1; i + l - 1 <= n + n; i++) {
int j = i + l - 1;
for (int k = i; k < j; k++) {
if (op[k + 1] == 't') {
f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j]);
g[i][j] = min(g[i][j], g[i][k] + g[k + 1][j]);
}
else if (op[k + 1] == 'x') {
f[i][j] = max(f[i][j], f[i][k] * f[k + 1][j]);
f[i][j] = max(f[i][j], g[i][k] * g[k + 1][j]);
g[i][j] = min(g[i][j], g[i][k] * g[k + 1][j]);
g[i][j] = min(g[i][j], f[i][k] * g[k + 1][j]);
g[i][j] = min(g[i][j], g[i][k] * f[k + 1][j]);
}
}
}
for (int i = 1; i - 1 < n; i++) ans = max(ans, f[i][i + n - 1]);
for (int i = 1; i - 1 < n; i++)
if (f[i][i + n - 1] == ans) ans2.push_back(i);
printf("%d\n", ans);
for (std::vector<int>::iterator p = ans2.begin(); p != ans2.end(); p++) printf("%d ", *p);
return 0;
}https://www.luogu.com.cn/problem/P2014
树上背包入门题。很久以前做过了，结果做完又忘了，所以再做一遍。设$dp[x][i]$表示以 x 为根的子树选了 i 个节点时的最大权值和，那么有：
$$dp[x][j]=\max_{k=1}^{j-1}(dp[x][j],dp[x][j-k]+dp[v][k])$$
这个方程似乎并没有体现出必须选择父节点的条件，但实际上 k 的枚举范围最大到$j-1$，就意味着当前状态无法由选了 0 个节点的状态转移来，从而满足了条件。
#include<cstdio>
int n, m, dp[310][310];
struct edge { int to, next; };
struct graph {
int ecnt, head[310];
edge edges[310];
inline void addedge(int u, int v) {
edges[++ecnt].to = v;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}g;
inline int max(int a, int b) { return a > b ? a : b; }
void dfs(int x) {
for (int i = g.head[x]; i; i = g.edges[i].next) {
int &v = g.edges[i].to;
dfs(v);
for (int j = m; j >= 1; j--)
for (int k = 1; k < j; k++) dp[x][j] = max(dp[x][j], dp[x][j - k] + dp[v][k]);
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
int fa; scanf("%d%d", &fa, &dp[i][1]);
g.addedge(fa, i);
}
m++;
dfs(0);
printf("%d\n", dp[0][m]);
return 0;
}https://www.luogu.com.cn/problem/P1437
一个砖能被敲掉的前提是它上面和右上的砖都被敲掉。所以每列被敲掉的砖一定是一个前缀。那么可以从右往左 DP ，设$dp[j][i][k]$表示处理完了后 j 列，第 j 列敲了上面 i 块砖，一共敲了 k 块砖时的最大分值。
$$dp[j][i][k]=\min_{l=i-1}^{n-j}(dp[j+1][l][k-i]+\sum_{p=1}^ia[i][j])$$
总复杂度$O(n^4)$。可以再加个前缀和优化，把$O(n)$的转移优化为$O(1)$，复杂度降到$O(n^3)$。
其实本质就是按照拓扑序 DP。所以其实从上往下 DP，每次枚举当前行敲了哪个前缀也是可以的。
#include<cstdio>
#include<cstring>
int n, m, a[55][55], f[55][55][1510], g[55][55][1510], ans;
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n - i + 1; j++) scanf("%d", &a[i][j]);
memset(f, -0x3f, sizeof f);
f[n + 1][0][0] = g[n + 1][0][0] = 0;
for (int j = n; j >= 1; j--) {
int sum = 0;
for (int i = 0; i <= n - j + 1; i++) {
sum += a[i][j];
for (int k = i * (i + 1) / 2; k <= m; k++)
f[j][i][k] = g[j + 1][max(i - 1, 0)][k - i] + sum;
ans = max(ans, f[j][i][m]);
}
for (int i = n - j + 1; i >= 0; i--)
for (int k = i * (i + 1) / 2; k <= m; k++) g[j][i][k] = max(g[j][i + 1][k], f[j][i][k]);
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P2704
状压 DP，设$dp[i][s1][s2]$表示 DP 到了第 i 行，第 i 行的状态为 s1，第 i - 1 行的状态为 s2 时，最多能放几个。如果就这样暴力 DP ，复杂度$O(8^nn)$，不太行。可以预处理满足相邻的 1 距离大于等于 2 的所有状态，然后发现这样符合条件的状态最多只有 60 个，于是复杂度就优化到了$O(60^3n)$。
$$dp[i][s1][s2]=\min_{valid(s3)}(dp[i-1][s2][s3]+bit(s3))$$
#include<cstdio>
#include<cstring>
int n, m, stt[110], scnt, dp[110][65][65], ans, a[110];
inline char read() {
char c = getchar();
while (c == ' ' || c == '\n' || c == '\r') c = getchar();
return c;
}
inline bool judge(int s) {
int lst = -1;
bool ok = true;
for (int i = 0; i < m && ok; i++) {
if (lst != -1 && (s & (1 << i)) && i - lst <= 2) ok = false;
else if (s & (1 << i)) lst = i;
}
return ok;
}
inline int bit(int s) {
int ans = 0;
for (; s; s = (s - 1) & s) ans++;
return ans;
}
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (read() == 'H') a[i] = (a[i] << 1) | 1;
else a[i] = a[i] << 1;
}
for (int s = 0; s < (1 << m); s++) if (judge(s)) stt[++scnt] = s;
memset(dp, -0x3f, sizeof dp);
for (int j = 1; j <= scnt; j++) {
if (stt[j] & a[1]) continue;
for (int k = 1; k <= scnt; k++) {
if (stt[j] & stt[k]) continue;
dp[1][j][k] = bit(stt[j]);
}
}
for (int i = 2; i <= n; i++)
for (int j = 1; j <= scnt; j++) {
if (stt[j] & a[i]) continue;
int s = stt[j];
for (int k = 1; k <= scnt; k++) {
if ((s & stt[k]) || (stt[k] & a[i - 1])) continue;
for (int l = 1; l <= scnt; l++) {
if ((s & stt[l]) || (stt[k] & stt[l]) || (stt[l] & a[i - 2])) continue;
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][k][l] + bit(s));
}
}
}
for (int i = 1; i <= scnt; i++) {
if (stt[i] & a[n]) continue;
for (int j = 1; j <= scnt; j++)
if (!(stt[i] & stt[j]) && !(stt[j] & a[n - 1])) ans = max(ans, dp[n][i][j]);
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P3052
和之前那个机器人小 Q 类似，也是将物品划分为若干组，使得组数最小，不同的是这题对顺序没有要求，且要求全选。做法类似，让状态的 0/1 表示这个物品有没有被划分到某一组，设$f[s]$表示对应状态的最小分组数，$g[s]$表示在$f[s]$最小的前提下最后一组的最小已占用空间。然后分成可以合并到前一组和不能合并两种情况讨论即可，连分类讨论的标准都是类似的。
#include<cstdio>
#include<cstring>
int n, w, v[20], f[270100], g[270100];
inline int min(int a, int b) { return a < b ? a : b; }
int main() {
scanf("%d%d", &n, &w);
for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
memset(f, 0x3f, sizeof f); memset(g, 0x3f, sizeof g);
f[0] = 0;
for (int s = 1; s < (1 << n); s++) {
for (int i = 1; i <= n; i++) {
if (s & (1 << (i - 1))) {
if (g[s ^ (1 << (i - 1))] + v[i] <= w && f[s] >= f[s ^ (1 << (i - 1))]) {
f[s] = f[s ^ (1 << (i - 1))];
g[s] = min(g[s], g[s ^ (1 << (i - 1))] + v[i]);
}
if (g[s ^ (1 << (i - 1))] + v[i] > w && f[s] >= f[s ^ (1 << (i - 1))] + 1) {
f[s] = f[s ^ (1 << (i - 1))] + 1;
g[s] = min(g[s], v[i]);
}
}
}
}
printf("%d\n", f[(1 << n) - 1]);
return 0;
}https://www.luogu.com.cn/problem/P2051
这题我看了题解，因为想不出来怎么划分阶段和设计状态。
由题意得每行每列最多只能放两个棋，那么每行每列放的棋的数量只有 0, 1, 2 三种情况。可以以行为阶段进行 DP，设$dp[i][j][k]$表示前 i 行中有 j 列放了 1 个棋，k 列放了 2 个棋，剩下$m-j-k$列没有放棋。然后分情况讨论即可。
$$dp[i][j][k]=dp[i-1][j][k]\\+(j+1)dp[i-1][j+1][k-1]+(m-j-k+1)dp[i-1][j-1][k]\\+\binom{j+2}{2}dp[i-1][j+2][k-2]+\binom{m-j-k+2}{2}dp[i-1][j-2][k]\\+(m-j-k+1)j\cdot dp[i-1][j][k-1]$$
#include<cstdio>
const int MOD = 9999973;
int n, m, dp[110][110][110], ans;
int main() {
scanf("%d%d", &n, &m);
dp[0][0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
for (int k = 0; k <= m - j; k++) {
dp[i][j][k] = dp[i - 1][j][k];
if (k) dp[i][j][k] = (dp[i][j][k] + (long long)(j + 1) * dp[i - 1][j + 1][k - 1] % MOD) % MOD;
if (j) dp[i][j][k] = (dp[i][j][k] + (long long)(m - j - k + 1) * dp[i - 1][j - 1][k] % MOD) % MOD;
if (k > 1) dp[i][j][k] = (dp[i][j][k] + (long long)(j + 2) * (j + 1) / 2 * dp[i - 1][j + 2][k - 2] % MOD) % MOD;
if (j > 1) dp[i][j][k] = (dp[i][j][k] + (long long)(m - j - k + 2) * (m - j - k + 1) / 2 * dp[i - 1][j - 2][k] % MOD) % MOD;
if (k) dp[i][j][k] = (dp[i][j][k] + (long long)(m - j - k + 1) * j % MOD * dp[i - 1][j][k - 1] % MOD) % MOD;
}
for (int j = 0; j <= m; j++)
for (int k = 0; k <= m - j; k++) ans = (ans + dp[n][j][k]) % MOD;
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P2512
这题我看了题解，因为没见过这种模型，弱化版(luogu P1031)也没做过。
设$x_i$表示第 i 个人给第 i - 1 个人传了几个唐，那么答案就是$\sum_{i=1}^n|x_i|$。题目要求最后每个人的唐数都变成$\overline a$，那么有：
$$a_i+x_{i+1}-x_i=\overline a(i\in[1,n])$$
$$x_{i+1}=\overline a-a_i+x_i$$
$$x_i=\overline a-a_{i-1}+x_{i-1}(i\in[1,n])$$
用$x_1$表示出其他的$x_i$，那么有：
$$x_i=\begin{cases}x_1&i=1\\x_{i-1}+\overline a-a_{i-1}&i\in[2,n]\end{cases}$$
$$x_i=\begin{cases}x_1&i=1\\x_1+\sum_{j=1}^{i-1}(\overline a-a_j)&i\in[2,n]\end{cases}$$
设
$$c_i=\begin{cases}0&i=1\\\sum_{j=1}^{i-1}(a_j-\overline a)&i\in[2,n]\end{cases}$$
所以
$$x_i=\begin{cases}x_1&i=1\\x_1-c_i&i\in[2,n]\end{cases}$$
于是答案为
$$\sum_{i=1}^n|x_i|=\sum_{i=1}^n|x_1-c_i|$$
这里还用到一个结论：设 a 是一个长度为 n 的序列，则令$\sum_{i=1}^n|x-a_i|$最小的 x 是这个序列的中位数。证明略
所以可以计算一下 c 数组，然后找到 c 的中位数，然后统计答案即可。
注意要开long long。
#include<cstdio>
#include<algorithm>
int n;
long long a[1000100], avg, c[1000100], mid, ans;
inline long long abs(long long x) { return x > 0 ? x : -x; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), avg += a[i];
avg /= n;
for (int i = 1; i <= n; i++) a[i] -= avg, c[i] = c[i - 1] + a[i - 1];
std::nth_element(c + 1, c + n / 2 + 1, c + n + 1);
mid = c[n / 2 + 1];
if (n % 2) {
std::nth_element(c + 1, c + n / 2, c + n + 1);
mid = (mid + c[n / 2]) / 2;
}
for (int i = 1; i <= n; i++) ans += abs(mid - c[i]);
printf("%lld\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P6538
看到这个题，我不禁想到了二分图最大权匹配，但是复杂度显然不行。可以把袋子排一遍序，那么做法就变得显然了，从小到大考虑每个袋子，显然贪心地装它能装的价值最大的物品即可。
所以有时候给数据排个序或许能让问题变得简单。至少能方便思考。
注意用multiset，而不是set。
#include<cstdio>
#include<algorithm>
#include<set>
#include<functional>
int n, k, c[300100];
long long ans;
struct item {
int m, v;
}itm[300100];
std::multiset<int, std::greater<int> > s;
inline bool cmp(item &a, item &b) { return a.m < b.m; }
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d%d", &itm[i].m, &itm[i].v);
for (int i = 1; i <= k; i++) scanf("%d", &c[i]);
std::sort(itm + 1, itm + n + 1, cmp);
std::sort(c + 1, c + k + 1);
int cur = 1;
for (int i = 1; i <= k; i++) {
while (cur <= n && itm[cur].m <= c[i]) s.insert(itm[cur].v), cur++;
if (!s.empty()) {
ans += *s.begin();
s.erase(s.begin());
}
}
printf("%lld\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P6508
显然是二分，问题在于 check 函数怎么写。我想了个 DP，但是复杂度爆炸，一看题解发现原来自己写 DP 写傻了，直接枚举小包买了几个，算出要花多少钱，取最小值即可。
#include<cstdio>
int n, m, a[110], b[110], sm[110], pm[110], sv[110], pv[110], suma;
inline int min(int a, int b) { return a < b ? a : b; }
bool check(int mid) {
int reqm = 0;
for (int i = 1; i <= n; i++) {
int ireq = a[i] * mid - b[i], ireqm = 0x3fffffff;
for (int j = 0; sm[i] * j <= ireq; j++) {
int k = (ireq - sm[i] * j) / sv[i] + ((ireq - sm[i] * j) % sv[i] ? 1 : 0);
ireqm = min(ireqm, j * pm[i] + k * pv[i]);
}
ireqm = min(ireqm, (ireq / sm[i] + (ireq % sm[i] ? 1 : 0)) * pm[i]);
if (ireqm ^ 0x3fffffff) reqm += ireqm;
}
return reqm <= m;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d%d%d%d%d%d", &a[i], &b[i], &sm[i], &pm[i], &sv[i], &pv[i]), suma += a[i];
int l = 0, r = suma + m;
while (l < r) {
int mid = l + (r - l >> 1);
if (check(mid)) l = mid + 1;
else r = mid;
}
printf("%d\n", l - 1);
return 0;
}https://www.luogu.com.cn/problem/P5017
显然可以看出一个复杂度关于 t 的 DP 做法，设$dp[i]$表示车在第 i 时刻出发时的最小等待时间和，那么有：
$$dp[i]=\min_{j=0}^{i-m}(dp[j]+i\cdot cnt(j,i)-sum(j,i))$$
其中 j 是枚举上一次出发的时刻，$cnt(j,i)$表示满足$j\le t_k\le i$的人数，$sum(j,i)$表示满足$j\le t_k\le i$的人的$t_k$之和。总复杂度$O(t^2)$，不行。
当$j\le i-2m$时，可以在$[j+m,i-m]$之间再出发一次，这样答案显然会比再$i-2m$之前出发更优，所以可以优化一下：
$$dp[i]=\min_{j=i-2m+1}^{i-m}(dp[j]+i\cdot cnt(j,i)-sum(j,i))$$
这样复杂度就优化到了$O(tm)$，有可能能过，但感觉还是不太行。
当$(i-m,i)$中间一个人都没有时，显然在$i-m$时刻发车比在 i 时刻发车更优，所以没有人时，$dp[i]=dp[i-m]$。
显然有人的状态只有$O(nm)$个，那么复杂度优化到了$O(nm^2+t)$，行。
#include<cstdio>
#include<cstring>
int n, m, cnt[4001000], sum[4001000], maxt, dp[4001000], ans = 0x7fffffff;
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
cnt[x]++; sum[x] += x;
maxt = max(maxt, x);
}
for (int i = 1; i < maxt + m; i++) cnt[i] += cnt[i - 1], sum[i] += sum[i - 1];
memset(dp, 0x3f, sizeof dp);
dp[0] = 0;
for (int i = 1; i < maxt + m; i++) {
if (i >= m && !(cnt[i] - cnt[i - m])) { dp[i] = dp[i - m]; continue; }
dp[i] = i * cnt[i] - sum[i];
for (int j = max(0, i - m - m + 1); j <= i - m; j++) dp[i] = min(dp[i], dp[j] + i * (cnt[i] - cnt[j]) - (sum[i] - sum[j]));
}
for (int i = maxt; i < maxt + m; i++) ans = min(ans, dp[i]);
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P5663
给出一个点，每次询问某个点到这个点是否存在一条长度为 l 的路径，路径可以是简单或不简单的。
因为可以是不简单路径，所以只要一个点有到其他点的边，就可以先从这个点从到另一个点，再走回来，这样路径长度 +2 ，起点不变。所以可以直接跑一遍 bfs，求出给出的起点到其他所有点的长度分别为奇数和偶数的最短路，如果和 l 的奇偶性相同的最短路的长度小于等于 l ,就存在一条长度为 l 的路径。
这题我看了题解，原因是对这类题的模型不够了解，并且对题目的分析也不够，没想到可以走到其他点再走回来。
#include<cstdio>
#include<cstring>
#include<queue>
#include<utility>
int n, m, t, dis[100100][2];
bool vis[100100][2];
struct edge { int to, next; };
struct graph {
int ecnt, head[100100];
edge edges[200100];
inline void addedge(int u, int v) {
edges[++ecnt].to = v;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}g;
std::queue<std::pair<int, int> > q;
void bfs() {
memset(dis, 0x3f, sizeof dis);
dis[1][0] = 0;
q.push(std::make_pair(1, 0));
while (!q.empty()) {
std::pair<int, int> f = q.front();
q.pop();
if (vis[f.first][f.second & 1]) continue;
vis[f.first][f.second & 1] = true;
for (int i = g.head[f.first]; i; i = g.edges[i].next) {
int &v = g.edges[i].to;
if (dis[v][(f.second & 1) ^ 1] > dis[f.first][f.second & 1] + 1) {
dis[v][(f.second & 1) ^ 1] = dis[f.first][f.second & 1] + 1;
q.push(std::make_pair(v, dis[f.first][f.second & 1] + 1));
}
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &t);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
g.addedge(u, v); g.addedge(v, u);
}
bfs();
for (int i = 1; i <= t; i++) {
int a, l; scanf("%d%d", &a, &l);
if (dis[a][l & 1] <= l) printf("Yes\n");
else printf("No\n");
}
return 0;
}https://www.luogu.com.cn/problem/P3959
n 很小，那肯定是状压 DP 。考虑状态 s 表示对应节点有没有加入生成树，但这样难以划分状态，也不知道深度是多少。可以再加一维，$dp[d][s]$表示加入状态为 s ，生成树中深度最大的点的深度为 i 时的最小花费，那么有：
$$dp[d][s]=\min_{(s1\in s)\land(s\in ex[s1])}(dp[d-1][s1]+(d-1)cost[s1][s])$$
其中$cost[s1][s]$表示在状态 s1 基础上一步(即加入的边有一端在原集合中)加入一些点变成 s 所需的最小花费，$ex[s]$表示把所有一步能加入的点都加入 s 后得到的集合。这个方程看起来不是很对，因为它把枚举的所有点都加到深度最大的点下面去了，但实际上它已经枚举了所有的方案，所以一定枚举到了最优解，而只需要保证能枚举到最优解就够了，不需要管其他不优的决策。其实这样的等价转换在之前那道 USACO 的状压题中也有体现。
要计算$cost$，可以把它分开考虑，考虑状态 s 一步加入某个点所需的最小花费，这个显然很好算，算出来后枚举两个状态，把所有只在其中一个集合中存在的元素的值加上即可。
总复杂度$O(n^23^n)$。
注意特判只有一个点的情况。
#include<cstdio>
#include<cstring>
int n, m, dp[15][4100], ex[4100], dis[4100][15], cost[4100][4100], g[15][15], ans = 0x3fffffff;
inline int min(int a, int b) { return a < b ? a : b; }
int main() {
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
g[u][v] = g[v][u] = min(g[u][v], w);
}
memset(dis, 0x3f, sizeof dis);
for (int s = 1; s < (1 << n); s++)
for (int x = 1; x <= n; x++)
if (s & (1 << (x - 1))) {
ex[s] |= (1 << (x - 1));
for (int v = 1; v <= n; v++)
if (g[x][v] ^ 0x3f3f3f3f) ex[s] |= (1 << (v - 1)), dis[s][v] = min(dis[s][v], g[x][v]);
}
for (int s = 1; s < (1 << n); s++)
for (int s1 = s; s1; s1 = (s1 - 1) & s)
for (int x = 1; x <= n; x++)
if ((s & (1 << (x - 1))) && !(s1 & (1 << (x - 1)))) cost[s1][s] += dis[s1][x];
for (int root = 1; root <= n; root++) {
memset(dp, 0x3f, sizeof dp);
dp[1][1 << (root - 1)] = 0;
for (int d = 2; d <= n; d++) {
for (int s = 0; s < (1 << n); s++)
for (int s1 = s; s1; s1 = (s1 - 1) & s)
if ((ex[s1] & s) == s) dp[d][s] = min(dp[d][s], dp[d - 1][s1] + (d - 1) * cost[s1][s]);
ans = min(ans, dp[d][(1 << n) - 1]);
}
}
if (n > 1) printf("%d\n", ans);
else printf("0\n");
return 0;
}https://www.luogu.com.cn/problem/P2831
n 这么小，肯定也是状压 DP，设状态 s 表示对应的猪有没有被消灭，$dp[s]$表示达到对应状态最少要发射几次。可以预处理$eft[i][j]$表示发射一条经过点 i 和点 j 的抛物线时能消灭的猪的集合。然后对于每个状态枚举单独消灭某个猪和同时消灭一些猪两种决策，后者可以枚举抛物线经过的两个点。这样总复杂度是$O(2^nn^2)$的，感觉不太行。
交换消灭的顺序，对答案是没有影响的。所以，对于当前状态中的某个点，既然它迟早要被消灭，那现在就消灭它好了。所以可以固定状态的一个点(比如我写的是编号最小的点)，然后枚举另一个点即可，总复杂度优化到了$O(2^nn)$，行。
这题我看了题解，设计出状态后没想出来怎么预处理和写方程，对模型的了解还不够，总之不够熟练。我觉得可能可以这样思考：既然要消灭若干猪，那可以枚举其中的两个，因为三点确定抛物线，所以枚举两个足以推出其他的。从小的部分入手。
#include<cstdio>
#include<cstring>
const double eps = 1e-6;
int t, n, m, dp[270100], lowbitx[270100], eft[20][20];
double x[20], y[20];
inline double abs(double x) { return x > -eps ? x : -x; }
inline int min(int a, int b) { return a < b ? a : b; }
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%lf %lf", &x[i], &y[i]);
for (int s = 1; s < (1 << n); s++) {
int t = s, x = 1;
while (!(t & 1)) t >>= 1, x++;
lowbitx[s] = x;
}
memset(eft, 0, sizeof eft);
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) {
if (abs(x[i] - x[j]) < eps) continue;
double a = (y[i] * x[j] - y[j] * x[i]) / (x[i] * x[i] * x[j] - x[j] * x[j] * x[i]), b = y[i] / x[i] - a * x[i];
if (a > 0) continue;
for (int k = 1; k <= n; k++)
if (abs(a * x[k] * x[k] + b * x[k] - y[k]) < eps) eft[i][j] = eft[j][i] = (eft[i][j] | (1 << (k - 1)));
}
memset(dp, 0x3f, sizeof dp);
dp[0] = 0;
for (int s = 1; s < (1 << n); s++) {
for (int i = 1; i <= n; i++) {
dp[s] = min(dp[s], dp[s ^ (1 << (i - 1))] + 1);
dp[s] = min(dp[s], dp[s ^ (eft[i][lowbitx[s]] & s)] + 1);
}
}
printf("%d\n", dp[(1 << n) - 1]);
}
return 0;
}https://www.luogu.com.cn/problem/P1131
可以考虑把过程倒过来，从所有叶子节点出发，同时汇聚到根节点，那么对于每个点，叶子节点的电流一定是同时到达它的，于是做法显而易见：记某个点 x 的所有叶子节点到达它的最早时间是$t[x]$，对于每个节点求子节点的 t 的最大值 maxt，maxt 减去每个子节点的 t 就是这个子节点对答案的贡献。
这题我看了题解，没有想到倒过来做。正难则反，有时候把过程倒过来想说不定就变简单了。
#include<cstdio>
int n, s;
long long t[500100], ans;
struct edge { int to, next, w; };
struct graph {
int ecnt = 1, head[500100];
edge edges[1000100];
inline void addedge(int u, int v, int w) {
edges[++ecnt].to = v;
edges[ecnt].w = w;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}g;
inline int max(int a, int b) { return a > b ? a : b; }
void dfs(int x, int lst) {
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
int &v = g.edges[i].to;
dfs(v, i);
t[x] = max(t[x], t[v] + g.edges[i].w);
}
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
ans += t[x] - t[g.edges[i].to] - g.edges[i].w;
}
}
int main() {
scanf("%d%d", &n, &s);
for (int i = 1; i < n; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
g.addedge(u, v, w); g.addedge(v, u, w);
}
dfs(s, 0);
printf("%lld\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P5997
又是一个最小划分组数问题，这次不同组的容量是不同的。优先选择容量更大的包更优，所以可以先把包排序，然后和前面两题一样 DP 即可。
注意判断一些边界条件，不要一时图快就赶紧交了。
这题我看了题解，没想到贪心选大包，对状压 DP 的认识也不够深，实际上，这样做能够枚举所有的方案，所以是对的。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
int n, m, v[30], c[110], f[17001000], g[17001000];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
for (int i = 1; i <= m; i++) scanf("%d", &c[i]);
std::sort(c + 1, c + m + 1, std::greater<int>());
memset(f, 0x3f, sizeof f); memset(g, 0x3f, sizeof g);
f[0] = 0;
for (int s = 1; s < (1 << n); s++)
for (int i = 1; i <= n; i++)
if (s & (1 << (i - 1))) {
int s1 = s ^ (1 << (i - 1));
if (f[s1] > n) continue;
if (g[s1] + v[i] <= c[f[s1]]) {
if (f[s] > f[s1]) f[s] = f[s1], g[s] = g[s1] + v[i];
else if (f[s] == f[s1] && g[s1] + v[i] < g[s]) g[s] = g[s1] + v[i];
}
else {
if (v[i] > c[f[s1] + 1]) continue;
if (f[s] > f[s1] + 1) f[s] = f[s1] + 1, g[s] = v[i];
else if (f[s] == f[s1] + 1 && v[i] < g[s]) g[s] = v[i];
}
}
if (f[(1 << n) - 1] ^ 0x3f3f3f3f) printf("%d\n", f[(1 << n) - 1]);
else printf("NIE\n");
return 0;
}https://www.luogu.com.cn/problem/P1966
$$\sum_{i=1}^n(a_i-b_i)^2=\sum_{i=1}^n(a_i^2+b_i^2)-2\sum_{i=1}^na_ib_i$$
不管怎么交换，其中的$\sum(a_i^2+b_i^2)$的值都不会变化，那么问题就转化为了$\sum a_ib_i$最大。
由排序不等式得，当序列 a 与序列 b 中大小排名相同的数放在同一位置时，$\sum a_ib_i$最大。所以可以先把两个序列离散化一下，然后要求的就是把排列 b 变成排列 a 的最小交换次数，可以将 a 中的数字按照位置重新编号，将 b 按照相同的规则重新改写，然后求 b 的逆序对个数即可。
这题我看了题解，看题解前用贪心的邻项交换法整了个奇怪的式子，可以用来排序并求出最小距离和，但不能求出最小交换次数。没想到可以求逆序对个数。总之分析题目时最好先推一下题目中直接出现的式子，而不要用一些与题目没有显然关联的方法分析，另外看到最小交换次数就要反应过来一般是逆序对个数。
#include<cstdio>
#include<algorithm>
const int MOD = 1e8 - 3;
int n, a[100100], b[100100], c[100100], d[100100], ans;
struct ft {
int ft[100100];
inline int lowbit(int x) { return x & -x; }
inline void add(int x, int v) { for (x = n - x + 1; x <= n; x += lowbit(x)) ft[x] += v; }
inline int query(int x) {
int ans = 0;
for (x = n - x + 1; x >= 1; x -= lowbit(x)) ans += ft[x];
return ans;
}
}ft;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), c[i] = a[i];
for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
std::sort(c + 1, c + n + 1);
int an = std::unique(c + 1, c + n + 1) - c - 1;
for (int i = 1; i <= n; i++) a[i] = std::lower_bound(c + 1, c + an + 1, a[i]) - c;
for (int i = 1; i <= n; i++) c[i] = b[i];
std::sort(c + 1, c + n + 1);
int bn = std::unique(c + 1, c + n + 1) - c - 1;
for (int i = 1; i <= n; i++) b[i] = std::lower_bound(c + 1, c + bn + 1, b[i]) - c;
for (int i = 1; i <= n; i++) d[a[i]] = i;
for (int i = 1; i <= n; i++) b[i] = d[b[i]];
for (int i = 1; i <= n; i++) {
ans = (ans + ft.query(b[i])) % MOD;
ft.add(b[i], 1);
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P2312
一看这数据范围好像要写高精，但是感觉复杂度不太行，一看题解，原来是哈希。枚举所有可能的解，然后计算验证，因为系数太大所以可以模一个数(我膜的是 19260817)，如果在模这个数意义下计算出多项式是 0 那么就假装它是解。这样做大概率是对的，可以多模几个数提高正确率，不过常数也会增加，我写了两个模数就 TLE 了。
计算多项式可以用秦九韶算法。
另外，还可以取小质数为模数，然后如果一个数不是解，那么这个数加模数的倍数也不是解，从而降低常数。听说还可以用中国剩余定理优化，但是好像没有题解这样写。
这题我看了题解，因为没想到可以用哈希做，总之不会做时可以想一些奇怪的乱搞做法，比如哈希。
#include<cstdio>
const int MOD = 19260817;
int n, m, a[110], ans1, ans2[1000100];
inline void read(int x) {
register char ch = getchar();
register int flag = 1;
while (ch == ' ' || ch == '\n' || ch == '\r') ch = getchar();
if (ch == '-') flag = -1, ch = getchar();
while ('0' <= ch && ch <= '9') {
a[x] = ((long long)a[x] * 10 + (ch & 15) * flag + MOD) % MOD;
ch = getchar();
}
}
inline bool check(int x) {
int ans = a[n];
for (int i = n; i >= 1; i--) ans = ((long long)ans * x + a[i - 1]) % MOD;
return !ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++) read(i);
for (int x = 1; x <= m; x++)
if (check(x)) ans2[++ans1] = x;
printf("%d\n", ans1);
for (int i = 1; i <= ans1; i++) printf("%d\n", ans2[i]);
return 0;
}https://www.luogu.com.cn/problem/P5888
受到限制的节点最多只有 1e5 个，那么可以把所有不被限制且不是第一个点的点合并在一起，记为 0 号节点。设$dp[i][j]$表示传了 i 次球最后传到了 j 的方案数，直接 DP 即可。
这样暴力 DP 复杂度是$O(mk^2)$的，因为需要$O(k)$转移。正难则反，可以预处理所有节点的方案数之和$\sum_{j=0}^{vn}dp[i-1][j]$，其中 vn 是有限制的点的个数，然后用这个和减去当前点能到达的点的方案数即可，因为只有$O(k)$条边，所以复杂度降为了$O(m(k+k))$即$O(mk)$。
注意边是单向边。
这题我看了题解，因为不会优化转移。
#include<cstdio>
#include<algorithm>
const int MOD = 998244353;
int n, k, m, vl[100100], vcnt, dp[210][100100], sum[210];
struct uedge { int u, v; }edges[50100];
struct edge { int to, next; };
struct graph {
int ecnt, head[100100];
edge edges[200100];
inline void addedge(int u, int v) {
edges[++ecnt].to = v;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}g;
int main() {
scanf("%d%d%d", &n, &k, &m);
vl[++vcnt] = 1;
for (int i = 1; i <= m; i++) scanf("%d%d", &edges[i].u, &edges[i].v), vl[++vcnt] = edges[i].u, vl[++vcnt] = edges[i].v;
std::sort(vl + 1, vl + vcnt + 1);
int vn = std::unique(vl + 1, vl + vcnt + 1) - vl - 1;
for (int i = 1; i <= m; i++) {
edges[i].u = std::lower_bound(vl + 1, vl + vn + 1, edges[i].u) - vl;
edges[i].v = std::lower_bound(vl + 1, vl + vn + 1, edges[i].v) - vl;
g.addedge(edges[i].u, edges[i].v);
}
dp[0][1] = 1; sum[0] = 1;
for (int j = 1; j <= k; j++) {
if (n - vn > 0) dp[j][0] = (long long)dp[j - 1][0] * (n - vn - 1) % MOD;
for (int i = 1; i <= vn; i++) dp[j][0] = (dp[j][0] + (long long)dp[j - 1][i] * (n - vn) % MOD) % MOD;
sum[j] = dp[j][0];
for (int x = 1; x <= vn; x++) {
dp[j][x] = (sum[j - 1] - dp[j - 1][x] + MOD) % MOD;
for (int i = g.head[x]; i; i = g.edges[i].next)
if (x ^ g.edges[i].to) dp[j][x] = (dp[j][x] - dp[j - 1][g.edges[i].to] + MOD) % MOD;
sum[j] = (sum[j] + dp[j][x]) % MOD;
}
}
printf("%d\n", dp[k][1]);
return 0;
}https://www.luogu.com.cn/problem/P1136
显然交换两个相同的字符是没用的，交换两个不同的字符，等价于把一个从 j 变为 z ，另一个从 z 变为 j。于是可以设$dp[i][j][k][0/1]$表示前 i 个字符中有 j 个从 z 变为了 j，有 k 个从 j 变为了 z，第 i 位变为了 j / z 的最大 jz 个数，那么有：
$$dp[i][j][k][0]=\max(dp[i-1][j][k][0],dp[i-1][j][k][1])\ \ \ (s[i]=j)$$
$$dp[i][j][k][1]=\max(dp[i-1][j][k-1][0]+1,dp[i-1][j][k-1][1])\ \ \ (s[i]=j)$$
$$dp[i][j][k][0]=\max(dp[i-1][j-1][k][0],dp[i-1][j-1][k][1])\ \ \ (s[i]=z)$$
$$dp[i][j][k][1]=\max(dp[i-1][j][k][0]+1,dp[i-1][j][k][1])\ \ \ (s[i]=z)$$
然后记得初始化为$-\inf$，$dp[0][0][0][1]=0$。对于最优化问题的 DP，一般都要初始化为$\inf$或$-\inf$，然后一些合法的初始状态初始化为 0 或者其他什么东西，这样才能保证状态由合法的状态转移而来。总之初始化也是 DP 设计中重要的一环。
#include<cstdio>
#include<cstring>
int n, m, dp[510][110][110][2], ans;
char s[510];
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d%d", &n, &m);
scanf("%s", s + 1);
memset(dp, -0x3f, sizeof dp);
dp[0][0][0][1] = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
for (int k = 0; k <= m; k++) {
if (s[i] == 'j') {
dp[i][j][k][0] = max(dp[i - 1][j][k][0], dp[i - 1][j][k][1]);
if (k) dp[i][j][k][1] = max(dp[i - 1][j][k - 1][0] + 1, dp[i - 1][j][k - 1][1]);
}
else if (s[i] == 'z') {
if (j) dp[i][j][k][0] = max(dp[i - 1][j - 1][k][0], dp[i - 1][j - 1][k][1]);
dp[i][j][k][1] = max(dp[i - 1][j][k][0] + 1, dp[i - 1][j][k][1]);
}
}
for (int i = 0; i <= m; i++) ans = max(ans, max(dp[n][i][i][0], dp[n][i][i][1]));
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P2448
有两种位置，一种是被交换过的，另一种是没交换过的。有两种对答案的贡献，一种是被交换过的数之间的，另一种是被交换过和没被交换过的数之间的。
先离散化一下，然后第一种贡献可以直接求逆序对得出，对于第二种贡献可以把没被交换的数的连续段看作一个整体，因为它们在值域上是连续的所以这一段中所有数对答案的贡献都是相同的，那么这段的贡献就是段中最小的数(其他数也一样)的逆序对数乘段长。把这一整段看作一个整体，求逆序对即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
int n, p[200100], vl[200100], vcnt, a[100100], b[100100], vn;
long long ans;
struct ft {
int ft[200100];
inline int lowbit(int x) { return x & -x; }
inline void add(int x, int v) { for (x = vn - x + 1; x <= vn; x += lowbit(x)) ft[x] += v; }
inline int query(int x) {
int ans = 0;
for (x = vn - x + 1; x >= 1; x -= lowbit(x)) ans += ft[x];
return ans;
}
inline void clear() { memset(ft, 0, sizeof(int) * (vn + 1)); }
}ft;
inline void swap(int &a, int &b) { int t = a; a = b; b = t; }
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]), vl[++vcnt] = a[i], vl[++vcnt] = b[i];
std::sort(vl + 1, vl + vcnt + 1);
vn = std::unique(vl + 1, vl + vcnt + 1) - vl - 1;
for (int i = 1; i <= n; i++) a[i] = std::lower_bound(vl + 1, vl + vn + 1, a[i]) - vl, b[i] = std::lower_bound(vl + 1, vl + vn + 1, b[i]) - vl;
for (int i = 1; i <= vn; i++) p[i] = i;
for (int i = 1; i <= n; i++) swap(p[a[i]], p[b[i]]);
for (int i = 1; i <= vn; i++) {
ans += ft.query(p[i]);
ft.add(p[i], 1);
if (i < vn) ans += ft.query(i + 1) * (vl[i + 1] - 1 - vl[i]);
}
ft.clear();
for (int i = 1; i <= vn; i++) {
ans += ft.query(p[i]);
ft.add(i, vl[i + 1] - 1 - vl[i]);
}
printf("%lld\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P1514
可以用反证法证明，若存在所有沙漠城市都建造设施的方案，则湖泊地带的任意城市能够输送的沙漠城市的集合一定是一个区间。并且由题意得地图是一个 DAG ，那么显然可以直接 DP，设$dp[i][j]$表示处于位置$(i,j)$的点能够输送的沙漠城市的区间，按照拓扑序把自身能直接到达的节点的区间合并即可。若两个区间的并集不是一个区间，则不存在可行的方案。
若存在可行的方案，那么还要求覆盖所有位置的最小区间数，直接暴力 DP 即可；若不存在可行方案，直接暴力标记统计答案即可。
然而只得了 90 分，调试发现我的 dfs 被毒瘤数据卡爆栈了。不管了。
#include<cstdio>
#include<cstring>
#include<algorithm>
const int dir[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
int n, m, h[510][510], dp2[510];
bool vis[510][510], vis2[510];
struct section {
int l, r;
section(int lv = 0, int rv = 0): l(lv), r(rv) {}
inline void build() { l = m; r = 0; }
}dp[510][510], all, sec[510];
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
inline section merge(const section &a, const section &b) {
if (!((a.l == m && !a.r) || (b.l == m && !b.r)) && (a.r + 1 < b.l || b.r + 1 < a.l)) return section(n, 0);
return section(min(a.l, b.l), max(a.r, b.r));
}
inline void dfs(int x, int y) {
if (vis[x][y]) return;
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int xg = x + dir[i][0], yg = y + dir[i][1];
if (xg >= 1 && xg <= n && yg >= 1 && yg <= m && h[xg][yg] < h[x][y]) {
dfs(xg, yg);
dp[x][y] = merge(dp[x][y], dp[xg][yg]);
}
}
}
inline bool cmp(const section &a, const section &b) { return a.r < b.r; }
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%d", &h[i][j]), dp[i][j].build();
for (int j = 1; j <= m; j++) dp[n][j] = section(j, j);
for (int j = 1; j <= m; j++) dfs(1, j);
all.build();
for (int j = 1; j <= m; j++) all = merge(all, dp[1][j]);
if (all.l == 1 && all.r == m) {
for (int j = 1; j <= m; j++) sec[j] = dp[1][j];
std::sort(sec + 1, sec + m + 1, cmp);
memset(dp2, 0x3f, sizeof dp2);
dp2[0] = 0;
for (int cur = 1, i = 1; i <= m; i++) {
while (cur <= m && sec[cur].r < i) cur++;
while (sec[cur].r == i) {
for (int j = sec[cur].l - 1; j < i; j++) dp2[i] = min(dp2[i], dp2[j] + 1);
cur++;
}
}
printf("1\n%d\n", dp2[m]);
}
else {
for (int i = 1; i <= m; i++)
for (int j = dp[1][i].l; j <= dp[1][i].r; j++) vis2[j] = true;
int ans = 0;
for (int i = 1; i <= m; i++)
if (!vis2[i]) ans++;
printf("0\n%d\n", ans);
}
return 0;
}https://www.luogu.com.cn/problem/P1627
把大于 b 的数看作 1 ，等于 b 的数看作 0，小于 b 的数看作 -1，那么问题就转化为了求包含某个位置的区间和为 0 的区间个数。把区间和拆为两个前缀和的差，那么对于所有在 b 右边的位置，求在 b 左边有多少和位置的前缀和与它相同即可，可以开个计数数组$O(n)$实现。
#include<cstdio>
const int K = 100010;
int n, b, a[100100], cnt[200100], x, ans;
int main() {
scanf("%d%d", &n, &b);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if (a[i] > b) a[i] = 1;
else if (a[i] == b) a[i] = 0, x = i;
else a[i] = -1;
a[i] += a[i - 1];
}
cnt[K] = 1;
for (int i = 1; i <= n; i++) {
if (i >= x) ans += cnt[a[i] + K];
else cnt[a[i] + K]++;
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P1472
设$dp[i][j]$表示有 i 个节点，深度小于等于 j 的无标号完满二叉树的个数，那么有：
$$dp[i][j]=\sum_{k=1}^idp[k][j-1]\cdot dp[i-k-1][j-1]$$
常见的思路是设$dp[i][j]$表示有 i 个节点，深度等于 j 的个数，但这样转移方程很麻烦，不如上面好写。
与之前做的"分手是祝愿"那题对应，在那题中把状态差分了一下方程才写出了方程，而本题把状态前缀和了一下使方程更加简洁。
#include<cstdio>
const int MOD = 9901;
int n, k, dp[210][110];
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= k; i++) dp[1][i] = 1;
for (int i = 1; i <= n; i++)
for (int j = 2; j <= k; j++)
for (int k = 1; k < i; k++)
dp[i][j] = (dp[i][j] + dp[k][j - 1] * dp[i - k - 1][j - 1]) % MOD;
printf("%d\n", (dp[n][k] - dp[n][k - 1] + MOD) % MOD);
return 0;
}https://www.luogu.com.cn/problem/P2577
首先有一个贪心的结论：让吃饭时间长的人先打饭一定更优。
可以用邻项交换法证明。设某个人打饭时间为$a_i$，吃饭时间为$b_i$，紧接着排在他后面的人的打饭时间为$a_j$，吃饭时间为$b_j$。令$b_i<b_j$。则总时间为$t_1=\max(a_i+b_i,a_i+a_j+b_j)=a_i+a_j+b_j$。交换两个人的次序，则总时间为$t_2=\max(a_j+a_i+b_i,a_j+b_j)$。
若$t_2=a_j+a_i+b_i$，那么有$b_i<b_j$得$t_1>t_2$；若$t_2=a_j+b_j$，那么$t_1>t_2$。综上所述，当$b_i<b_j$时，交换它们的次序一定能使答案更优。所以让吃饭时间长的人先打饭一定更优。先排下序，然后接下来考虑 DP。
设$dp[i][j]$表示前 i 个人一号窗口的打饭时间为 j 时的最小吃饭时间，有：
$$dp[i][j]=\min(\max(dp[i-1][j-a[i]],j+b[i]),\max(dp[i-1][j],sum[i]-j+b[i]))$$
其中$sum[i]$表示前$i$个人的打饭时间之和。
#include<cstdio>
#include<cstring>
#include<algorithm>
int n, dp[210][40100], sum[210], ans = 0x3fffffff;
struct person {
int a, b;
}p[210];
inline bool cmp(person &a, person &b) { return a.b > b.b; }
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].a, &p[i].b);
std::sort(p + 1, p + n + 1, cmp);
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + p[i].a;
memset(dp, 0x3f, sizeof dp);
dp[0][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= sum[i]; j++) {
if (j >= p[i].a) dp[i][j] = min(dp[i][j], max(dp[i - 1][j - p[i].a], j + p[i].b));
dp[i][j] = min(dp[i][j], max(dp[i - 1][j], sum[i] - j + p[i].b));
}
for (int j = 0; j <= sum[n]; j++) ans = min(ans, dp[n][j]);
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P1809
先排序。不难想到一种决策：让最快的和最慢的一起渡河，然后最快的再回来，用时是$t_1+t_i$。除此之外还有另一种决策：让最快的和次快的一起渡河，最快的回来，让最慢的和次慢的一起渡河，次快的回来，用时是$t_1+2t_2+t_i$。这两个用时不能在得到确切的数之前明确大小关系，那么取最小值就行了。
于是设$dp[i]$表示前 i 个人的最短用时，那么有：
$$dp[i]=\min(dp[i-1]+t_1+t_i,dp[i-2]+t_1+2t_2+t_i)$$
#include<cstdio>
#include<algorithm>
int n, t[100100];
long long dp[100100];
inline long long min(long long a, long long b) { return a < b ? a : b; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &t[i]);
std::sort(t + 1, t + n + 1);
dp[1] = t[1]; dp[2] = t[2];
for (int i = 3; i <= n; i++) dp[i] = min(dp[i - 1] + t[1] + t[i], dp[i - 2] + t[1] + t[2] * 2 + t[i]);
printf("%lld\n", dp[n]);
return 0;
}https://www.luogu.com.cn/problem/P5588
对于每种颜色，求它有多少个端点。端点的意思是这个点只有一个子树中存在和它颜色相同的点。可以用以前用过的一个技巧，记录每种颜色当前访问过的节点数，然后若访问子树后与访问子树前的计数的差值大于 0 ，则说明这个子树中有颜色相同的点。
需要注意的是，若一个节点没发现有存在相同颜色的点的子树，这个点仍可能是端点，因为它的未访问的兄弟节点可能和它颜色相同。若一个节点发现只有一个子树中存在颜色相同的点，这个点也不一定是端点，也因为它的未访问的兄弟节点可能和它颜色相同。因此在判断时要多加一些限制，设目前发现的存在相同颜色节点的子树数量为 ed，若 ed = 1，且(当前节点不是第一个被访问的这种颜色的节点，或当前节点是最后一个被访问的这种颜色的节点)，那么就认为它是端点；若 ed = 0，且当前节点是第一个被访问的这种颜色的节点，那么也认为它是端点。
求出端点数后，若没有端点则任意路径都是合法的，答案为$\dfrac{n(n-1)}{2}$；若只有一个端点说明只有一个这种颜色的点，答案为子树 size 两两相乘的和；若有两个端点，根据乘法原理，答案是两个节点对应子树的 size 之积；若有三个及以上端点，答案为 0。
#include<cstdio>
int n, c[1000100], cnt[1000100], eptcnt[1000100], size[1000100], epsize[1000100], tot[1000100];
long long ans1[1000100], ans2[1000100];
struct edge { int to, next; };
struct graph {
int ecnt = 1, head[1000100];
edge edges[2000100];
inline void addedge(int u, int v) {
edges[++ecnt].to = v;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}g;
void dfs(int x, int lst) {
size[x] = 1;
int ed = (cnt[c[x]] ? 1 : 0), son = 0;
bool top = (cnt[c[x]] ? false : true);
cnt[c[x]]++;
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
int &v = g.edges[i].to, lst = cnt[c[x]];
dfs(v, i);
ans1[c[x]] += (long long)size[x] * size[v];
size[x] += size[v];
if (cnt[c[x]] - lst) ed++, son = v;
}
ans1[c[x]] += (long long)(n - size[x]) * size[x];
if ((ed == 1 && (ed == (top ? 0 : 1) || cnt[c[x]] == tot[c[x]])) || (top && !ed)) {
if (!eptcnt[c[x]]) { epsize[c[x]] = (top && ed ? n - size[son] : size[x]); }
else if (eptcnt[c[x]] == 1) ans2[c[x]] = (long long)epsize[c[x]] * (top && ed ? n - size[son] : size[x]);
eptcnt[c[x]]++;
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &c[i]), tot[c[i]]++;
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
g.addedge(u, v); g.addedge(v, u);
}
dfs(1, 0);
for (int i = 1; i <= n; i++) {
if (!cnt[i]) printf("%lld\n", (long long)n * (n - 1) / 2);
else if (cnt[i] == 1) printf("%lld\n", ans1[i]);
else if (eptcnt[i] == 2) printf("%lld\n", ans2[i]);
else printf("0\n");
}
return 0;
}https://www.luogu.com.cn/problem/P1528
二分填多少嘴，然后 dfs + 剪枝判断是否可行。显然优先填嘴小的会使答案更优，所以先把嘴排一遍序，然后 dfs 时依次枚举每个嘴吃哪个蛋糕。有如下优化：
#include<cstdio>
#include<algorithm>
int n, a[55], m, b[1100], maxa, suma, sumb[1100];
bool ans;
inline int max(int a, int b) { return a > b ? a : b; }
void dfs(int x, int st) {
if (ans) return;
if (!x) { ans = true; return; }
if (suma < sumb[x]) return;
for (int i = st; i <= n; i++) {
if (a[i] < b[x]) continue;
a[i] -= b[x]; suma -= b[x];
if (a[i] < b[1]) suma -= a[i];
if (b[x - 1] == b[x]) dfs(x - 1, i);
else dfs(x - 1, 1);
if (a[i] < b[1]) suma += a[i];
a[i] += b[x]; suma += b[x];
}
}
inline bool check(int mid) {
ans = false;
dfs(mid, 1);
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), maxa = max(maxa, a[i]), suma += a[i];
scanf("%d", &m);
for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
std::sort(b + 1, b + m + 1);
for (int i = 1; i <= m + 1; i++) sumb[i] = sumb[i - 1] + b[i];
for (; sumb[m] > suma; m--);
int l = 0, r = m + 1;
while (l < r) {
int mid = l + (r - l >> 1);
if (check(mid)) l = mid + 1;
else r = mid;
}
printf("%d\n", l - 1);
return 0;
}https://www.luogu.com.cn/problem/P4370
当 n 固定不变时，$\binom{n}{m}$是一个关于 m 的凸函数。若 n 为偶数，则$m=\dfrac{n}{2}$时$\binom{n}{m}$有最大值；若 n 为奇数，则$m=\left\lfloor\dfrac{n}{2}\right\rfloor$和$\left\lfloor\dfrac{n}{2}\right\rfloor+1$时$\binom{n}{m}$有最大值。所以直接对于$i\in[1,n]$，在大根堆中插入$\binom{i}{i/2}$即可。每次取出堆中最大值，然后加入它对应的那一侧的下一个组合数。
要比较组合数，直接算太大了，模意义下又没法比较，可以用之前 zhx 出的那个二分题中相同的技巧，在比较时将不等式两侧取对数，那么直接预处理 log 阶乘的前缀和，比较时直接算对数比较即可。
#include<cstdio>
#include<queue>
#include<cmath>
int MOD = 1e9 + 7;
int n, k, fac[1000100], invfac[1000100], ans;
double logfac[1000100];
struct binom {
int a, b;
binom(int av = 0, int bv = 0): a(av), b(bv) {}
inline bool operator < (const binom &y) const { return logfac[a] - logfac[b] - logfac[a - b] < logfac[y.a] - logfac[y.b] - logfac[y.a - y.b]; }
inline int value() { return (long long)fac[a] * invfac[b] % MOD * invfac[a - b] % MOD; }
};
std::priority_queue<binom> q;
void exgcd(int a, int b, int &x, int &y) {
if (!b) { x = 1; y = 0; return; }
exgcd(b, a % b, y, x);
y -= a / b * x;
}
inline int inv(int a) { int x, y; exgcd(a, MOD, x, y); return (x % MOD + MOD) % MOD; }
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) logfac[i] = logfac[i - 1] + log(i);
fac[0] = invfac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = (long long)fac[i - 1] * i % MOD;
invfac[n] = inv(fac[n]);
for (int i = n - 1; i >= 0; i--) invfac[i] = (long long)invfac[i + 1] * (i + 1) % MOD;
for (int i = 0; i <= n; i++) q.push(binom(i, i / 2));
for (int i = 1; i <= k; i++) {
binom t = q.top();
q.pop();
ans = (ans + t.value()) % MOD;
if (t.b - 1 >= 0 && t.b <= (double)t.a / 2) q.push(binom(t.a, t.b - 1));
if (t.b + 1 <= t.a && t.b >= t.a / 2) q.push(binom(t.a, t.b + 1));
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P2064
设第 i 天的乘上的数为$k_i$，则总路程为$a+ak_1+ak_1k_2+...+(ak_1k_2...k_n)$。用秦九韶算法中的方法，把式子化为$a(1+k_1(1+k_2(...)))$，然后发现总路程一定是 a 的倍数，所以枚举 s 的所有因数，除以 a 后 dfs 搜索，依次枚举$k_1$到$k_n$。若当前数$\in[2,9]$，说明已经递归到了最后一层，将 ans 取最小值返回即可。
#include<cstdio>
int s, ans = 0x3fffffff;
inline int min(int a, int b) { return a < b ? a : b; }
void dfs(int x, int cnt) {
if (cnt >= ans) return;
x--;
if (2 <= x && x <= 9) { ans = min(ans, cnt + 1); return; }
if (x < 2) return;
for (int i = 2; i <= 9; i++) if (!(x % i)) dfs(x / i, cnt + 1);
}
int main() {
scanf("%d", &s);
for (int i = 1; i * i <= s; i++) {
if (s % i) continue;
dfs(i, 1);
dfs(s / i, 1);
}
if (ans ^ 0x3fffffff) printf("%d\n", ans);
else printf("-1\n");
return 0;
}https://www.luogu.com.cn/problem/P5322
将每个城堡看作一个组，击败的玩家的集合看作物品，那么问题就转化为了 01 分组背包问题，可以$O(nms)$解决。
为了方便可以把同一个城堡的不同玩家兵力排序，然后击败的玩家集合就是一个前缀。
#include<cstdio>
#include<cstring>
#include<algorithm>
int s, n, m, a[110][110], dp[110][20100], ans;
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d%d%d", &s, &n, &m);
for (int i = 1; i <= s; i++)
for (int j = 1; j <= n; j++) scanf("%d", &a[j][i]);
for (int i = 1; i <= n; i++) std::sort(&a[i][0] + 1, &a[i][0] + s + 1);
memset(dp, -0x3f, sizeof dp);
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
dp[i][j] = dp[i - 1][j];
for (int k = 1; k <= s; k++)
if (j >= a[i][k] * 2 + 1) dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i][k] * 2 - 1] + k * i);
}
}
for (int i = 0; i <= m; i++) ans = max(ans, dp[n][i]);
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P3801
设矩形的长为 w，高为 h，被覆盖的行的数量为 ansr，被覆盖的列的数量为 ansc，显然答案就是$ansr\cdot w+ansc\cdot h-2\cdot ansr\cdot ansc$。那么分别维护行和列被覆盖的情况，修改时相当于单点异或 1，使用树状数组直接维护即可。
#include<cstdio>
int n, m, q;
struct ft {
int ft[100100], n, a[100100];
inline int lowbit(int x) { return x & -x; }
inline void add(int x, int v) { for (; x <= n; x += lowbit(x)) ft[x] += v; }
inline void sxor1(int x) {
if (a[x]) add(x, -1);
else add(x, 1);
a[x] ^= 1;
}
inline int query(int x) {
int ans = 0;
for (; x >= 1; x -= lowbit(x)) ans += ft[x];
return ans;
}
inline int query(int l, int r) { return query(r) - query(l - 1); }
}row, clm;
int main() {
scanf("%d%d%d", &n, &m, &q);
row.n = n; clm.n = m;
for (int i = 1; i <= q; i++) {
int opt; scanf("%d", &opt);
if (opt == 1) {
int x, y; scanf("%d%d", &x, &y);
row.sxor1(x); clm.sxor1(y);
}
else if (opt == 2) {
int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int ansr = row.query(x1, x2), ansc = clm.query(y1, y2);
printf("%lld\n", (long long)ansr * (y2 - y1 + 1) + (long long)ansc * (x2 - x1 + 1) - (long long)ansr * ansc * 2);
}
}
return 0;
}https://www.luogu.com.cn/problem/P2216
使用单调队列套单调队列，内层维护每行当前区间的最值，外层维护所有行的区间的最值，复杂度$O(nm)$。
#include<cstdio>
#include<queue>
#include<utility>
int n, m, k, a[1010][1010], ans = 0x3fffffff;
std::deque<std::pair<int, int> > qrmin[1010], qcmin, qrmax[1010], qcmax;
inline int min(int a, int b) { return a < b ? a : b; }
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
for (int j = 1; j <= m; j++) {
qcmin.clear(); qcmax.clear();
for (int i = 1; i <= n; i++) {
while (!qrmin[i].empty() && qrmin[i].front().first < j - k + 1) qrmin[i].pop_front();
while (!qrmin[i].empty() && qrmin[i].back().second >= a[i][j]) qrmin[i].pop_back();
qrmin[i].push_back(std::make_pair(j, a[i][j]));
while (!qcmin.empty() && qcmin.front().first < i - k + 1) qcmin.pop_front();
while (!qcmin.empty() && qcmin.back().second >= qrmin[i].front().second) qcmin.pop_back();
qcmin.push_back(std::make_pair(i, qrmin[i].front().second));
while (!qrmax[i].empty() && qrmax[i].front().first < j - k + 1) qrmax[i].pop_front();
while (!qrmax[i].empty() && qrmax[i].back().second <= a[i][j]) qrmax[i].pop_back();
qrmax[i].push_back(std::make_pair(j, a[i][j]));
while (!qcmax.empty() && qcmax.front().first < i - k + 1) qcmax.pop_front();
while (!qcmax.empty() && qcmax.back().second <= qrmax[i].front().second) qcmax.pop_back();
qcmax.push_back(std::make_pair(i, qrmax[i].front().second));
if (i >= k && j >= k) ans = min(ans, qcmax.front().second - qcmin.front().second);
}
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P6298
容斥，设$g[i]$表示 gcd 是 i 的倍数的齿轮组个数，$f[i]$表示 gcd 是 i 的齿轮组个数，则有：
$$g[i]=\binom{\sum_{j=1}^n[i|a_j]}{k}$$
$$f[i]=g[i]-\sum_{(i|j)\land(i\not=j)}f[j]=\binom{\sum_{j=1}^n[i|a_j]}{k}-\sum_{(i|j)\land(i\not=j)}f[j]$$
于是倒着枚举 i ，枚举 i 的倍数计算即可，由于调和级数的增长是$O(\ln n)$的，所以复杂度$O(n+m\ln m)$。
#include<cstdio>
const int MOD = 1e9 + 7;
int n, m, k, f[1000100], fac[1000100], invfac[1000100], cnt[1000100];
void exgcd(int a, int b, int &x, int &y) {
if (!b) { x = 1; y = 0; return; }
exgcd(b, a % b, y, x);
y -= a / b * x;
}
inline int inv(int a) { int x, y; exgcd(a, MOD, x, y); return (x % MOD + MOD) % MOD; }
inline int binom(int n, int m) {
if (n < m) return 0;
return (long long)fac[n] * invfac[m] % MOD * invfac[n - m] % MOD;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
cnt[x]++;
}
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = (long long)fac[i - 1] * i % MOD;
invfac[n] = inv(fac[n]);
for (int i = n - 1; i >= 0; i--) invfac[i] = (long long)invfac[i + 1] * (i + 1) % MOD;
for (int i = m; i >= 1; i--) {
int sumf = 0, valid = cnt[i];
for (int j = i + i; j <= m; j += i) {
valid += cnt[j];
sumf = (sumf + f[j]) % MOD;
}
f[i] = (binom(valid, k) - sumf + MOD) % MOD;
}
for (int i = 1; i <= m; i++) printf("%d ", f[i]);
return 0;
}https://www.luogu.com.cn/problem/P3478
换根 DP 入门题，没啥好写的。
#include<cstdio>
int n, depth[1000100], ans, size[1000100];
long long dp[1000100], maxdp;
struct edge { int to, next; };
struct graph {
int ecnt = 1, head[1000100];
edge edges[2000100];
inline void addedge(int u, int v) {
edges[++ecnt].to = v;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}g;
void dfs1(int x, int lst) {
depth[x] = depth[g.edges[lst ^ 1].to] + 1;
size[x] = 1;
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
int &v = g.edges[i].to;
dfs1(v, i);
size[x] += size[v];
}
}
void dfs2(int x, int lst) {
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
int &v = g.edges[i].to;
dp[v] = dp[x] + (n - size[v]) - size[v];
dfs2(v, i);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
g.addedge(u, v); g.addedge(v, u);
}
dfs1(1, 0);
for (int i = 1; i <= n; i++) dp[1] += depth[i];
dfs2(1, 0);
for (int i = 1; i <= n; i++)
if (maxdp < dp[i]) {
maxdp = dp[i];
ans = i;
}
printf("%d\n", ans);
return 0;
}