striving & singing
https://www.luogu.com.cn/problem/P2564
一看题目显然可以双指针，那么先把坐标离散化，再记录每个坐标上的颜色，这样时间复杂度是$O(n\log n)$的，看起来可以，但是空间复杂度是$O(nk)$的，交上去直接 MLE 了。另一种更简单的方法是把珠子按照坐标排序，然后直接双指针即可，时间复杂度也是$O(n\log n)$，空间复杂度$O(n)$。
还有一种方法是先把所有颜色中坐标最小的加入堆中，然后每次取出堆中坐标最小的，把它的颜色对应的没有加入过堆的坐标最小的柱子加进去，这样复杂度是$O(n\log k)$的，更优。
#include<cstdio>
#include<utility>
#include<algorithm>
int n, k, cnt[61], ccnt, icnt, ans = 0x7fffffff;
std::pair<int, int> itm[1000100];
inline int min(int a, int b) { return a < b ? a : b; }
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= k; i++) {
int t; scanf("%d", &t);
for (int j = 1; j <= t; j++) {
int x; scanf("%d", &x);
itm[++icnt] = std::make_pair(x, i);
}
}
std::sort(itm + 1, itm + icnt + 1);
int cur = 1;
for (int i = 1; i <= n; i++) {
while (cur <= n && ccnt < k) {
if (!cnt[itm[cur].second]) ccnt++;
cnt[itm[cur].second]++;
cur++;
}
if (ccnt == k) ans = min(ans, itm[cur - 1].first - itm[i].first);
cnt[itm[i].second]--;
if (!cnt[itm[i].second]) ccnt--;
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P2331
一看$m\le 2$，可以直接想出一个状压 DP，设$dp[i][j][s]$表示前 i 行选了 j 个子矩阵，最后一行选的状态是 s 时的最大权值，其中状态 s 的第 k 位表示第 i 行的对应位置选没选。然后每个状态的决策有和前面的矩阵合并，和自己单独成为一个矩阵两种，分情况讨论即可。
但这样没法处理某一行中的两列属于不同的两个矩阵的情况(样例就是一个例子)，解决方法是再加一种状态，当 s = 4 时表示两个位置都选了，但属于不同的两个矩阵，然后继续分情况讨论即可。
注意分类讨论的状态转移细节，把一个 3 写成了 2 调了一个小时。
#include<cstdio>
#include<cstring>
int n, m, k, a[110][3], dp[110][11][5], ans;
inline int max(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]);
memset(dp, -0x3f, sizeof dp);
dp[0][0][0] = 0;
if (m == 1) {
for (int i = 1; i <= n; i++)
for (int j = 0; j <= k; j++) {
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]);
dp[i][j][1] = dp[i - 1][j][1] + a[i][1];
if (j) dp[i][j][1] = max(dp[i][j][1], max(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + a[i][1]);
}
ans = max(dp[n][k][0], dp[n][k][1]);
}
else if (m == 2) {
for (int i = 1; i <= n; i++)
for (int j = 0; j <= k; j++) {
for (int lst = 0; lst <= 4; lst++) {
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][lst]);
if (j) dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - 1][lst] + a[i][2]);
if (j) dp[i][j][2] = max(dp[i][j][2], dp[i - 1][j - 1][lst] + a[i][1]);
if (j) dp[i][j][3] = max(dp[i][j][3], dp[i - 1][j - 1][lst] + a[i][1] + a[i][2]);
if (j >= 2) dp[i][j][4] = max(dp[i][j][4], dp[i - 1][j - 2][lst] + a[i][1] + a[i][2]);
}
dp[i][j][1] = max(dp[i][j][1], max(dp[i - 1][j][1], dp[i - 1][j][4]) + a[i][2]);
dp[i][j][2] = max(dp[i][j][2], max(dp[i - 1][j][2], dp[i - 1][j][4]) + a[i][1]);
dp[i][j][3] = max(dp[i][j][3], dp[i - 1][j][3] + a[i][1] + a[i][2]);
dp[i][j][4] = max(dp[i][j][4], dp[i - 1][j][4] + a[i][1] + a[i][2]);
if (j) dp[i][j][4] = max(dp[i][j][4], max(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2]) + a[i][1] + a[i][2]);
}
for (int s = 0; s <= 4; s++) ans = max(ans, dp[n][k][s]);
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P3205
因为每次都是在序列的开头或结尾加数字，所以不难想到以区间作为阶段来 DP。设$dp[i][j][0/1]$表示区间$[i,j]$最后一次加入在了队头 / 队尾的方案数，初始化$dp[i][i][0]=dp[i][i][1]=1$，然后直接分类讨论即可。
一测样例发现输出的方案数是样例的两倍，其实是因为$dp[i][i][0]=dp[i][i][1]=1$导致只有一个人的序列方案数是 2，那么可以直接钦定一个人的序列只能从队头插入，即$dp[i][i][0]=1,dp[i][i][1]=0$。
#include<cstdio>
const int MOD = 19650827;
int n, h[1010], dp[1010][1010][2];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &h[i]), dp[i][i][0] = 1;
for (int l = 2; l <= n; l++)
for (int i = 1; i + l - 1 <= n; i++) {
int j = i + l - 1;
if (h[i] < h[i + 1]) dp[i][j][0] = (dp[i][j][0] + dp[i + 1][j][0]) % MOD;
if (h[i] < h[j]) dp[i][j][0] = (dp[i][j][0] + dp[i + 1][j][1]) % MOD;
if (h[j] > h[i]) dp[i][j][1] = (dp[i][j][1] + dp[i][j - 1][0]) % MOD;
if (h[j] > h[j - 1]) dp[i][j][1] = (dp[i][j][1] + dp[i][j - 1][1]) % MOD;
}
printf("%d\n", (dp[1][n][0] + dp[1][n][1]) % MOD);
return 0;
}https://www.luogu.com.cn/problem/P1272
设$dp[x][i]$表示节点 x 保留了 i 个节点，且保留了根节点时最少需要去掉的边数，那么有：
$$dp[x][i]=\begin{cases}deg[x]-[x\not =1]&i=1\\min_{j=0}^i{dp[x][i-j]+dp[v][j]-1}\end{cases}$$
其中$deg[x]$是 x 的度数，v 是节点 x 的子节点。-1 是因为在$dp[x][i-j]$中把$(x,v)$这条边删掉了，而要保留子节点就不能删这条边，所以删的边数 -1。
答案是$\min_{x=1}^n{dp[x][s]+[x\not=1]}$。
#include<cstdio>
#include<cstring>
int n, s, dp[155][155], ans = 0x3fffffff, deg[155];
struct edge { int to, next; };
struct graph {
int ecnt = 1, head[155];
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 min(int a, int b) { return a < b ? a : b; }
void dfs(int x, int lst) {
dp[x][1] = deg[x] - (x == 1 ? 0 : 1);
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);
for (int j = s; j >= 2; j--)
for (int k = 0; k <= j; k++) dp[x][j] = min(dp[x][j], dp[x][j - k] + dp[v][k] - 1);
}
ans = min(ans, dp[x][s] + (x == 1 ? 0 : 1));
}
int main() {
scanf("%d%d", &n, &s);
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
g.addedge(u, v); g.addedge(v, u);
deg[u]++; deg[v]++;
}
memset(dp, 0x3f, sizeof dp);
dfs(1, 0);
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P5628
这个是 USACO 的原题(luogu P3047)，以前做过那个原题但是现在又不太会了，所以再做一遍。为方便，下面讲的是原题的思路，本题在原题基础上稍加转化即可。
设$dp[x][i]$表示距离节点 x 距离不超过 i 的节点的权值和，那么可以先 dfs 一遍，求出距离节点 x 距离不超过 i 的 x 的子树内的节点的权值和，做法很显然，就不写了。然后可以换根+容斥，在第一遍 dfs 后，因为节点 1 是根节点所以节点 1 的 dp 值就是实际值，于是第二遍 dfs 时可以让$dp[v][i]$加上父节点的$dp[x][i-1]$，合并得到不是子树内的节点的权值和，而$dp[v][i-2]$多算了一遍所以还要减去。
#include<cstdio>
int n, k, size[30100];
long long dp[30100][210], ans;
struct edge { int to, next, w; };
struct graph {
int ecnt = 1, head[30100];
edge edges[60100];
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) {
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];
dp[x][0] += (long long)(n - size[v]) * size[v];
for (int j = 1; j <= k; j++) dp[x][j] += dp[v][j - 1];
}
for (int j = 1; j <= k; j++) dp[x][j] += dp[x][0];
}
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;
for (int j = k; j >= 1; j--) dp[v][j] += dp[x][j - 1] - (j >= 2 ? dp[v][j - 2] : 0);
dp[v][0] += (long long)(n - size[v]) * size[v];
dfs2(v, i);
}
}
inline long long max(long long a, long long b) { return a > b ? a : b; }
int main() {
scanf("%d%d", &n, &k);
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);
dfs2(1, 0);
for (int i = 1; i <= n; i++) ans = max(ans, dp[i][k]);
printf("%lld\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P5658
当时考场上想出了$O(n^2)$的暴力做法，但是树上的情况写挂了调不出来，于是只好写了个链的情况，拿了 35 分。要是树上的情况没写挂，拿到 50 分，那就可以省一了。
其实是一个线性 DP 强行搬到了树上。考虑链上的情况，设$dp[i]$表示以第 i 个位置结尾的合法括号序列个数，显然若$s[i]='('$或者$s[i]=')'$但没有匹配的左括号那么$dp[i]=0$，否则设匹配的左括号的位置为 lst，那么有$dp[i]=dp[lst-1]+1$。感觉挺对的，不过考场上没想出来，毕竟太菜了。
#include<cstdio>
#include<stack>
int n, f[500100];
long long dp[500100], ans;
char s[500100];
struct edge { int to, next; };
struct graph {
int ecnt, head[500100];
edge edges[500100];
inline void addedge(int u, int v) {
edges[++ecnt].to = v;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}g;
std::stack<int> stk;
void dfs1(int x) {
int t = 0;
if (s[x] == '(') stk.push(x);
else if (s[x] == ')' && !stk.empty()) {
dp[x] = dp[f[stk.top()]] + 1;
t = stk.top(); stk.pop();
}
for (int i = g.head[x]; i; i = g.edges[i].next) {
int &v = g.edges[i].to;
dfs1(v);
}
if (s[x] == '(') stk.pop();
else if (t) stk.push(t);
}
void dfs2(int x) {
for (int i = g.head[x]; i; i = g.edges[i].next) {
int &v = g.edges[i].to;
dp[v] += dp[x];
dfs2(v);
}
}
int main() {
scanf("%d", &n);
scanf("%s", s + 1);
for (int i = 2; i <= n; i++) {
scanf("%d", &f[i]);
g.addedge(f[i], i);
}
dfs1(1);
dfs2(1);
for (int i = 1; i <= n; i++) ans ^= i * dp[i];
printf("%lld\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P4170
因为涂的是一个区间所以想到区间 DP，设$dp[i][j]$表示$[i,j]$涂成目标状态需要的最少次数，那么有两种决策，一种是若$s[i]=s[j]$，那么可以由$dp[i+1][j-1]$转移来，另一种是通用的，直接枚举中间点，合并两个子区间。
#include<cstdio>
#include<cstring>
int n, dp[55][55];
char s[55];
inline int min(int a, int b) { return a < b ? a : b; }
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= n; i++) dp[i][i] = dp[i][i - 1] = 1;
for (int l = 2; l <= n; l++)
for (int i = 1; i + l - 1 <= n; i++) {
int j = i + l - 1;
if (s[i] == s[j]) dp[i][j] = min(dp[i][j], min(dp[i + 1][j], dp[i][j - 1]));
for (int k = i; k < j; k++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
printf("%d\n", dp[1][n]);
return 0;
}https://www.luogu.com.cn/problem/P3847
看完题面可以发现是一个区间 DP，但是转移感觉不太明白，但我决定先写一个试试，尽量不依靠题解。然后瞎编了两种转移方式，没想到交上去直接过了，挺好的。
代码中第一种转移对应加入/删除一个人，第二种转移对应改变一个人的颜色。
#include<cstdio>
#include<cstring>
int n, w[3010], dp[3010][3010];
inline int min(int a, int b) { return a < b ? a : b; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= n; i++) dp[i][i] = dp[i][i - 1] = 0;
for (int l = 2; l <= n; l++)
for (int i = 1; i + l - 1 <= n; i++) {
int j = i + l - 1;
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
if (w[i] == w[j]) dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
else dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + 1);
}
printf("%d\n", dp[1][n]);
return 0;
}https://www.luogu.com.cn/problem/P4395
设$dp[x][i]$表示节点 x 选了权值 i 时子树的最小权值和，那么有
$$dp[x][i]=i+\sum_v\min_{i\not =j}{dp[v][j]}$$
因为只有$i\not=j$这一个限制，所以集合${dp[v][j]}$中要么取最小值，要么取次小值，那么就可以只存最小值，次小值和取最小值时 j 的值。DP 时若子节点取最小值时的 j 和当前枚举到的权值相同，则需要取次小值。然后就把这个$O(n^2)$做法优化到了$O(n)$。
代码实现中，$sum[j]$存的是当前节点的权值取$j$时实际 DP 值(有些子节点取了次小值)和全部子节点取最小值时的差。之所以不直接存实际 DP 值，是因为这样做其他取最小值的点就不太好算了。总之代码实现也是挺有技巧的。
#include<cstdio>
#include<cstring>
int n, f[10100], g[10100], df[10100], sum[10100];
bool vis[10100];
struct edge { int to, next; };
struct graph {
int ecnt = 1, head[10100];
edge edges[20100];
inline void addedge(int u, int v) {
edges[++ecnt].to = v;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}gr;
inline void upd(int x, int v, int dv) {
if (v < f[x]) { g[x] = f[x]; f[x] = v; df[x] = dv; }
else if (v < g[x]) g[x] = v;
}
void dfs(int x, int lst) {
int s = 0, cur = 1;
for (int i = gr.head[x]; i; i = gr.edges[i].next) {
if ((i ^ lst) == 1) continue;
dfs(gr.edges[i].to, i);
}
for (int i = gr.head[x]; i; i = gr.edges[i].next) {
if ((i ^ lst) == 1) continue;
int &v = gr.edges[i].to;
s += f[v];
sum[df[v]] += g[v] - f[v]; vis[df[v]] = true;
}
while (vis[cur]) cur++; upd(x, s + cur, cur);
cur++; while (vis[cur]) cur++; upd(x, s + cur, cur);
for (int i = gr.head[x]; i; i = gr.edges[i].next) {
if ((i ^ lst) == 1) continue;
int &v = gr.edges[i].to;
if (!vis[df[v]]) continue;
upd(x, s + sum[df[v]] + df[v], df[v]);
sum[df[v]] = 0; vis[df[v]] = false;
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
gr.addedge(u, v); gr.addedge(v, u);
}
memset(f, 0x3f, sizeof f);
memset(g, 0x3f, sizeof g);
dfs(1, 0);
printf("%d\n", f[1]);
return 0;
}https://www.luogu.com.cn/problem/P6521
恰好 d 个位置不同，相当于恰好 4 - d 个位置相同。可以容斥一下，设$f[i]$表示恰好 i 个位置相同的个数，$g[i]$表示枚举哪 i 个位置相同，然后计算得出的个数(也被称为钦定 i 个位置相同的个数)，那么有：
$$f[i]=g[i]-\sum_{j=i+1}^4\binom{j}{i}f[j]$$
实际上就是枚举有多少个满足大于 i 个位置相同，设为 j ，然后每个对在$g[i]$中被计算了$\binom{j}{i}$次，直接减去即可。
另一种做法是二项式反演。同样设$f[i]$表示恰好，$g[i]$表示钦定，那么有：
$$g[i]=\sum_{j=i}^4\binom{j}{i}f[j]$$
直接套反演公式，得
$$f[i]=\sum_{j=i}^4(-1)^{j-i}\binom{j}{i}g[j]$$
同样可以得出正确答案。
二项式反演也叫广义容斥，至于为什么叫广义容斥我也不懂，感觉它只是用了一下容斥原理。有三种形式：
$$f(i)=\sum_{j=0}^i(-1)^j\binom{i}{j}g(j)\Leftrightarrow g(i)=\sum_{j=0}^i(-1)^j\binom{i}{j}f(j)$$
这个好像没啥用。
$$g(i)=\sum_{j=a}^i\binom{i}{j}f(j)\Leftrightarrow f(i)=\sum_{j=a}^i(-1)^{i-j}\binom{i}{j}g(j)$$
令$g(i)$表示钦定选最多 i 个的方案数，$f(i)$表示选恰好 i 个的方案数，那么就可以利用它实现两者之间的转化。
$$g(i)=\sum_{j=i}^n\binom{j}{i}f(j)\Leftrightarrow f(i)=\sum_{j=i}^n(-1)^{j-i}\binom{j}{i}g(j)$$
令$g(i)$表示钦定选最少 i 个的方案数，$f(i)$表示选恰好 i 个的方案数，那么也可以利用它实现两者之间的转化。
#include<cstdio>
#include<cstring>
#include<map>
#include<string>
#include<iostream>
int n, d, binom[5][5], ans, f[5], g[5];
std::map<std::string, int> cnt;
inline int bit(int x) {
int ans = 0;
for (; x; x = (x - 1) & x) ans++;
return ans;
}
int main() {
scanf("%d%d", &n, &d);
d = 4 - d;
binom[0][0] = 1;
for (int i = 1; i <= 4; i++)
for (int j = 0; j <= 4; j++) binom[i][j] = binom[i - 1][j] + binom[i - 1][j - 1];
for (int i = 1; i <= n; i++) {
memset(f, 0, sizeof f); memset(g, 0, sizeof g);
std::string str;
std::cin >> str;
for (int s = 0; s <= 15; s++) {
std::string str1; str1.resize(4);
for (int j = 0; j < 4; j++) {
if (s & (1 << j)) str1[j] = str[j];
else str1[j] = '$';
}
if (cnt.count(str1)) g[bit(s)] += cnt[str1];
cnt[str1]++;
}
for (int i = 4; i >= d; i--) {
f[i] = g[i];
for (int j = i + 1; j <= 4; j++) f[i] -= binom[j][i] * f[j];
}
ans += f[d];
}
printf("%d\n", ans);
return 0;
}子集反演：
$$g(S)=\sum_{T\subseteq S}f(T)\Leftrightarrow f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T)$$
$$g(S)=\sum_{T\supseteq S}f(T)\Leftrightarrow f(S)=\sum_{T\supseteq S}(-1)^{|T|-|S|}g(T)$$
证明可以考虑下面两个式子：
$$\sum_{T\subseteq S}(-1)^{|T|}=\sum_{|T|=0}^{|S|}(-1)^{|T|}\binom{|S|}{|T|}=(1-1)^{|S|}=[S=\varnothing]$$
$$\sum_{T\subseteq S}(-1)^{|S|-|T|}=\sum_{|T|=0}^{|S|}(-1)^{|S|-|T|}\binom{|S|}{|T|}=(1-1)^{|S|}=[S=\varnothing]$$
于是得到
$$\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T)\\=\sum_{U\subseteq S}f(U)\sum_{U\subseteq T\subseteq S}(-1)^{|S|-|T|}\\=\sum_{U\subseteq S}f(U)\sum_{T\subseteq S-U}(-1)^{|S-U|-|T|}\\=\sum_{U\subseteq S}f(U)[S=U]\\=f(S)$$
$$\sum_{T\supseteq S}(-1)^{|T|-|S|}g(T)\\=\sum_{U\supseteq S}f(U)\sum_{U\supseteq T\supseteq S}(-1)^{|T|-|S|}\\=\sum_{U\supseteq S}f(U)\sum_{U-S\supseteq T}(-1)^{|T|}\\=\sum_{U\supseteq S}f(U)[S=U]\\=f(S)$$
当$f(S)$的值只与$|S|$有关时，通过子集反演的两个公式分别可以导出二项式反演的两个形式。
https://www.luogu.com.cn/problem/P4859
若有$x$对满足$a>b$，那么有$x-(n-x)=k$，解得$x=\dfrac{n+k}{2}$，所以当$n+k\equiv 1\pmod 2$时方案数为 0 ，否则可以转化为有$\dfrac{n+k}{2}$对满足$a>b$。
设$f(i)$表示有恰好 i 对满足条件的方案数，$g(i)$表示钦定 i 对满足条件的计算值，$dp[i][j]$表示 a 数组的前 i 个位置配对了 j 个满足条件的对时配对方案的数量，那么有：
$$dp[i][j]=dp[i-1][j]+(cnt(i)-(j-1))dp[i-1][j-1]$$
$$g(i)=\sum_{j=i}^n\binom{j}{i}f(j)\\=(n-i)!\cdot dp[n][i]$$
由二项式反演得
$$f(i)=\sum_{j=i}^n(-1)^{j-i}\binom{j}{i}g(j)$$
根据公式计算即可。
#include<cstdio>
#include<algorithm>
const int MOD = 1e9 + 9;
int n, k, a[2010], b[2010], dp[2010][2010], f[2010], g[2010], fac[2010], binom[2010][2010], ans;
int main() {
scanf("%d%d", &n, &k);
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = (long long)fac[i - 1] * i % MOD;
binom[0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= i; j++) {
binom[i][j] = binom[i - 1][j];
if (j) binom[i][j] = (binom[i][j] + binom[i - 1][j - 1]) % MOD;
}
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
std::sort(a + 1, a + n + 1);
std::sort(b + 1, b + n + 1);
int cur = 1;
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
while (cur <= n && b[cur] < a[i]) cur++;
for (int j = 0; j <= i; j++) {
dp[i][j] = dp[i - 1][j];
if (j) dp[i][j] = (dp[i][j] + (long long)(cur - 1 - (j - 1)) * dp[i - 1][j - 1] % MOD) % MOD;
}
}
for (int i = 0; i <= n; i++) g[i] = (long long)dp[n][i] * fac[n - i] % MOD;
if ((n + k) % 2) printf("0\n");
else for (int j = (n + k) / 2, op = 1; j <= n; j++, op *= -1) ans = (ans + (long long)op * binom[j][(n + k) / 2] * g[j] % MOD + MOD) % MOD;
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P6142
和赛道修建那题基本一样的，注意特判当前节点是 1 时的情况即可。
#include<cstdio>
#include<set>
int n;
bool ok;
struct edge { int to, next; };
struct graph {
int ecnt = 1, 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;
inline int max(int a, int b) { return a > b ? a : b; }
int dfs(int x, int lst, int mid) {
if (!ok) return 0;
int ans = 0, cnt = 0;
std::multiset<int> s;
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
int &v = g.edges[i].to;
s.insert(dfs(v, i, mid) + 1);
}
if ((x == 1 && (s.size() & 1)) || (x != 1 && !(s.size() & 1))) s.insert(0);
while (!s.empty() && ok) {
std::multiset<int>::iterator i = s.begin(), p = s.lower_bound(mid - *i);
if (i == p) p++;
if (x == 1) {
if (p == s.end()) ok = false;
else s.erase(p);
}
else {
if (p == s.end() && cnt) ok = false;
else if (p == s.end() && !cnt) ans = *i, cnt = 1;
else if (p != s.end()) s.erase(p);
}
s.erase(i);
}
return ans;
}
inline bool check(int mid) {
ok = true;
dfs(1, 0, mid);
return ok;
}
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);
}
int l = 1, r = n;
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/P5505
限制是每个同学都要分到特产，那么可以设$g(i)$表示钦定 i 个同学没有分到，$f(i)$表示恰好 i 个同学没有分到的方案数，那么有：
$$g(i)=\binom{n}{i}\prod_{j=1}^m\binom{a_j+n-i-1}{n-i-1}\\=\sum_{j=i}^n\binom{j}{i}f(j)$$
其中$\binom{n}{i}$是枚举哪 i 个同学没有分到，$\binom{a_j+n-i-1}{n-i-1}$的意思是把$a_j$个球分到$n-i$个盒子里，可以有空盒的方案数，根据乘法原理乘起来。
反演一下得到
$$f(i)=\sum_{j=i}^n(-1)^{j-i}\binom{j}{i}g(j)$$
代入 i = 0
$$f(0)=\sum_{j=0}^n(-1)^jg(j)$$
根据公式计算即可。
#include<cstdio>
const int MOD = 1e9 + 7;
int n, m, a[1010], binom[2010][2010], g[1010], ans;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
for (int i = 0; i <= 2000; i++) binom[i][0] = 1;
for (int i = 1; i <= 2000; i++)
for (int j = 1; j <= i; j++) binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
for (int i = 0; i <= n; i++) {
g[i] = binom[n][i];
for (int j = 1; j <= m; j++) g[i] = (long long)g[i] * binom[a[j] + n - i - 1][n - i - 1] % MOD;
}
for (int j = 0, op = 1; j <= n; j++, op *= -1) ans = (ans + (op * g[j] + MOD) % MOD) % MOD;
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P3158
设$f(t,x,y)$表示t个球恰好占用x行y列的方案数，$g(t,x,y)$表示t个球钦定占用x行y列的方案数，那么有：
$$g(t,x,y)=\binom{xy}{t}\=\sum_{i=1}^x\binom{x}{i}\sum_{j=1}^y\binom{y}{j}f(t,i,j)$$
二项式反演在高维情况下也成立：
$$f(t,x,y)=\sum_{i=1}^x(-1)^{x-i}\binom{x}{i}\sum_{j=1}^y(-1)^{y-j}\binom{y}{j}g(t,i,j)$$
那么就可以$O(n^5)$预处理出$f$。设$dp[t][x][y]$表示前 t 种颜色的球恰好占用了 x 行 y 列的方案数，那么有：
$$dp[t][x][y]=\sum_{dx=1}^x\sum_{dy=1}^y\binom{x}{dx}\binom{y}{dy}f[a[t]][dx][dy]\cdot dp[t-1][x-dx][y-dy]$$
再来一波$O(n^5)$ DP 即可。其中两个组合数的意思是枚举当前颜色占用了哪几行哪几列。
最后的答案就是：
$$\sum_{x=1}^n\sum_{y=1}^m\binom{n}{x}\binom{m}{y}dp[c][x][y]$$
其中 x,y 表示枚举所有棋子共占用了几行几列，两个组合数同样表示枚举所有棋子占用了哪几行哪几列。
另外，在证明二项式反演在二维情况下成立时要设一个中间量 h(具体见 luogu 题解)，而在递推时同时处理出 h 可以使预处理复杂度降一维。时间太紧了以后再仔细研究。
#include<cstdio>
const int MOD = 1e9 + 9;
int n, m, c, a[15], dp[11][35][35], f[1010][35][35], binom[910][910], ans;
bool vis[1010];
inline int max(int a, int b) { return a > b ? a : b; }
inline int pwr_1(int k) { return k % 2 ? -1 : 1; }
int main() {
scanf("%d%d%d", &n, &m, &c);
for (int i = 1; i <= c; i++) scanf("%d", &a[i]);
for (int i = 0; i <= n * m; i++) binom[i][0] = 1;
for (int i = 1; i <= n * m; i++)
for (int j = 1; j <= i; j++) binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
for (int t = 1; t <= c; t++) {
if (vis[a[t]]) continue;
vis[a[t]] = true;
for (int x = 1; x <= n && x <= a[t]; x++)
for (int y = 1; y <= m && y <= a[t]; y++)
for (int i = 1, opx = pwr_1(x - i); i <= x; i++, opx *= -1)
for (int j = 1, opy = pwr_1(y - j); j <= y; j++, opy *= -1)
f[a[t]][x][y] = (f[a[t]][x][y] + ((long long)opx * binom[x][i] * opy * binom[y][j] % MOD * binom[i * j][a[t]] % MOD + MOD) % MOD) % MOD;
}
dp[0][0][0] = 1;
for (int t = 1; t <= c; t++)
for (int x = 1; x <= n; x++)
for (int y = 1; y <= m; y++)
for (int dx = 1; dx <= x; dx++)
for (int dy = 1; dy <= y; dy++)
dp[t][x][y] = (dp[t][x][y] + (long long)dp[t - 1][x - dx][y - dy] * binom[x][dx] % MOD * binom[y][dy] % MOD * f[a[t]][dx][dy] % MOD) % MOD;
for (int x = 1; x <= n; x++)
for (int y = 1; y <= m; y++) ans = (ans + (long long)dp[c][x][y] * binom[n][x] % MOD * binom[m][y] % MOD) % MOD;
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P6478
给出一棵点数$n=2m$的树和两个点数为$n$的点集，对于$k\in[0,m]$，求将两个点集的点分别两两配对，有恰好$k$对满足一个是另一个节点的祖先的方案数。
设$f(i)$表示恰好 k 对的方案数，$g(i)$表示钦定 k 对的方案数，那么 f 可以由 g 通过二项式反演得到。若能求出选出 k 对的方案数，那么显然 g 可以由这个方案数乘上一个阶乘得到。
考虑树形 DP，设$dp[x][j]$表示以 x 为根的子树中选出 j 对的方案数，那么这就是一个树形背包，有：
$$dp[x][j]=\sum_{k=1}^jdp[x][j-k]\cdot dp[v][k]$$
这样算出来的是不选择当前节点的方案数，还要加上选择当前节点的方案数，也就是
$$dp[x][j]+=dp[x][j-1]\cdot (cnt-(j-1))$$
其中 cnt 表示子树中与当前节点不在同一点集的节点数。
朴素树形背包的复杂度是$O(n^3)$的，可以加个上下界优化，即限制枚举变量的上下界，把复杂度优化到$O(n^2)$。可以参考这篇文章：https://ouuan.github.io/post/%E6%A0%91%E4%B8%8A%E8%83%8C%E5%8C%85%E7%9A%84%E4%B8%8A%E4%B8%8B%E7%95%8C%E4%BC%98%E5%8C%96/
至于为什么这样可以优化我也不太懂，总之先背下来再说。
DP 完后，$g(i)=dp[1]i!$，然后直接套上二项式反演即可。
#include<cstdio>
const int MOD = 998244353;
int n, dp[5010][5010], f[2510], g[2510], cnt[5010][2], size[5010], fac[2510], binom[2510][2510];
char s[5010];
struct edge { int to, next; };
struct graph {
int ecnt = 1, head[5010];
edge edges[10010];
inline void addedge(int u, int v) {
edges[++ecnt].to = v;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}gr;
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
void dfs(int x, int lst) {
size[x] = 1;
dp[x][0] = 1;
for (int i = gr.head[x]; i; i = gr.edges[i].next) {
if ((i ^ lst) == 1) continue;
int &v = gr.edges[i].to;
dfs(v, i);
for (int j = min(size[x] + size[v], n / 2); j >= 1; j--)
for (int k = max(j - size[x], 1); k <= size[v] && k <= j; k++)
dp[x][j] = (dp[x][j] + (long long)dp[x][j - k] * dp[v][k] % MOD) % MOD;
size[x] += size[v];
cnt[x][0] += cnt[v][0]; cnt[x][1] += cnt[v][1];
}
for (int j = min(size[x], n / 2); j > 0; j--)
dp[x][j] = (dp[x][j] + (long long)dp[x][j - 1] * (cnt[x][(s[x] - '0') ^ 1] - (j - 1)) % MOD) % MOD;
cnt[x][s[x] - '0']++;
}
int main() {
scanf("%d", &n);
scanf("%s", s + 1);
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
gr.addedge(u, v); gr.addedge(v, u);
}
dfs(1, 0);
fac[0] = 1;
for (int i = 1; i <= n / 2; i++) fac[i] = (long long)fac[i - 1] * i % MOD;
for (int i = 0; i <= n / 2; i++) binom[i][0] = 1;
for (int i = 1; i <= n / 2; i++)
for (int j = 1; j <= i; j++) binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
for (int i = 0; i <= n / 2; i++) g[i] = (long long)dp[1][i] * fac[n / 2 - i] % MOD;
for (int i = 0; i <= n / 2; i++)
for (int j = i, op = 1; j <= n / 2; j++, op *= -1) f[i] = (f[i] + (op * (long long)binom[j][i] * g[j] % MOD + MOD)) % MOD;
for (int i = 0; i <= n / 2; i++) printf("%d\n", f[i]);
return 0;
}https://www.luogu.com.cn/problem/P3702
可以用减法公式，即答案等于任意数的方案数减去不用质数的方案数。然后就是一个常见的 DP，设$dp[i][j]$表示前 i 个数的和$\mod p$等于 j 的方案数，那么有：
$$dp[i][j]=\sum_{k=0}^{p-1}dp[i-1][(j-k)\bmod p]\cdot cnt(k)$$
令 k 等于 j - k，也就是从枚举 k 变为枚举 j - k，得到：
$$dp[i][j]=\sum_{k=0}^{p-1}dp[i-1][k]\cdot cnt((j-k)\bmod p)$$
其中$cnt(x)$表示$[1,m]$中$\mod p$等于 x 的数的个数，可以通过分类讨论$O(1)$算出。
设$c[k][j]=cnt((j-k)\bmod p)$，那么有:
$$dp[i][j]=\sum_{k=0}^{p-1}dp[i-1][k]\cdot c[k][j]$$
这就是矩阵乘法的形式，因此可以通过矩阵快速幂优化 DP，复杂度$O(p^3\log n)$。
注意不要写错模数。
#include<cstdio>
#include<cstring>
const int MOD = 20170408;
int n, m, p, ans, prime[2000100], pcnt, cntp[110];
bool isprime[20000100];
struct matrix {
int r, c, a[101][101];
int* operator [] (const int &idx) { return &a[idx][0]; }
matrix(int rv = 0, int cv = 0): r(rv), c(cv) { memset(a, 0, sizeof a); }
matrix operator * (matrix &b) {
matrix ans(r, b.c);
for (int i = 0; i < ans.r; i++)
for (int j = 0; j < ans.c; j++)
for (int k = 0; k < c; k++) ans[i][j] = (ans[i][j] + (long long)a[i][k] * b[k][j] % MOD) % MOD;
return ans;
}
inline void build() { for (int i = 0; i < r; i++) a[i][i] = 1; }
inline void clear() { memset(a, 0, sizeof a); }
}dp, trs;
inline int cnt(int x) {
if (x == 0) return m / p;
else if (x < m) return (m - x) / p + 1;
else if (x == m) return 1;
else return 0;
}
inline matrix pwr(matrix x, int k) {
matrix ans(x.r, x.c); ans.build();
for (; k; x = x * x, k >>= 1)
if (k & 1) ans = ans * x;
return ans;
}
int main() {
scanf("%d%d%d", &n, &m, &p);
dp.r = p, dp.c = 1; trs.r = trs.c = p;
dp[0][0] = 1;
for (int i = 0; i < p; i++)
for (int j = 0; j < p; j++) trs[i][j] = cnt((j - i + p) % p) % MOD;
dp = pwr(trs, n) * dp;
ans = dp[0][0];
for (int i = 2; i <= m; i++) isprime[i] = true;
for (int i = 2; i <= m; i++) {
if (isprime[i]) prime[++pcnt] = i, cntp[i % p]++;
for (int j = 1; j <= pcnt && i * prime[j] <= m; j++) {
isprime[i * prime[j]] = false;
if (!(i % prime[j])) break;
}
}
dp.clear(); trs.clear();
dp[0][0] = 1;
for (int i = 0; i < p; i++)
for (int j = 0; j < p; j++) trs[i][j] = (cnt((j - i + p) % p) - cntp[(j - i + p) % p] + MOD) % MOD;
dp = pwr(trs, n) * dp;
ans = (ans - dp[0][0] + MOD) % MOD;
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P6477
有两种我知道的思路，一种是 duyi 神仙的题解里的，考虑$f(l,r)$可以理解为在区间$[l,r]$中选出一个数字的方案数，而$f(l,r)^2$可以理解为在$[l,r]$中选出两个数字且可以重复的方案数，那么可以枚举这两个数字然后计算贡献，令某个数字对区间有贡献当且仅当它是区间中第一个出现的这一种数字，那么可以通过预处理$pre[i]$表示第 i 个数字的上一个相同数字的位置，然后可以通过它计算有贡献的区间个数。
考虑优化，可以只枚举两个数字中的一个，然后答案(应该)就是：
$$\sum_{j=1}^n(n-j+1)\left(2\sum_{i=pre[j]+1}^j(i-\max(pre[i],pre[j]))-(j-pre[j])\right)$$
要维护$\sum_{i=1}^j\max(pre[i],pre[j])$，可以考虑用$pre[j]\cdot j$加上大于$pre[j]$的那些$pre[i]$，再把多算的$pre[j]$减去即可，可以开两个权值树状数组，分别维护个数和和，总复杂度$O(n\log n)$。不过我写完调不出来了，样例都过不去。
另一种做法是扫描线。扫描线的思想就是对于区间统计的题目只统计其中一个区间端点，然后考虑端点变化时对答案的影响。对于本题可以枚举右端点 r ，然后考虑求出$\sum_{l=1}^nf(l,r)^2$。令第$i$个位置表示$f(i,r)$的信息，那么统计答案时就是直接算平方和，右端点向右移时就是把区间$[pre[r]+1,r]$加一，这个东西可以直接用线段树维护，根据初中数学有如下公式：
$$\sum(a+v)^2=\sum a^2+2v\sum a+\sum v^2$$
因此维护区间和和区间平方和以及加法标记即可。
注意不要爆long long。
#include<cstdio>
#include<algorithm>
const int MOD = 1e9 + 7;
int n, a[1000100], vl[1000100], lst[1000100], pre[1000100], ans;
struct segtreenode { int addtag, sum, sum2; };
struct segtree {
segtreenode nds[4000100];
inline int ls(int x) { return x << 1; }
inline int rs(int x) { return x << 1 | 1; }
inline void pushup(int x) {
nds[x].sum = (nds[ls(x)].sum + nds[rs(x)].sum) % MOD;
nds[x].sum2 = (nds[ls(x)].sum2 + nds[rs(x)].sum2) % MOD;
}
inline void pushdown(int x, int l, int r) {
if (!nds[x].addtag) return;
int mid = l + (r - l >> 1), &v = nds[x].addtag;
nds[ls(x)].sum2 = (nds[ls(x)].sum2 + ((long long)2 * v * nds[ls(x)].sum % MOD + (long long)v * v % MOD * (mid - l + 1) % MOD) % MOD) % MOD;
nds[ls(x)].sum = (nds[ls(x)].sum + (long long)v * (mid - l + 1) % MOD) % MOD;
nds[ls(x)].addtag = (nds[ls(x)].addtag + v) % MOD;
nds[rs(x)].sum2 = (nds[rs(x)].sum2 + ((long long)2 * v * nds[rs(x)].sum % MOD + (long long)v * v % MOD * (r - mid) % MOD) % MOD) % MOD;
nds[rs(x)].sum = (nds[rs(x)].sum + (long long)v * (r - mid) % MOD) % MOD;
nds[rs(x)].addtag = (nds[rs(x)].addtag + v) % MOD;
v = 0;
}
void add(int x, int l, int r, int ql, int qr, int v) {
if (ql <= l && r <= qr) {
nds[x].sum2 = (nds[x].sum2 + (long long)2 * v * nds[x].sum % MOD + (long long)v * v % MOD * (r - l + 1) % MOD) % MOD;
nds[x].sum = (nds[x].sum + (long long)v * (r - l + 1) % MOD) % MOD;
nds[x].addtag = (nds[x].addtag + v) % MOD;
return;
}
pushdown(x, l, r);
int mid = l + (r - l >> 1);
if (ql <= mid) add(ls(x), l, mid, ql, qr, v);
if (mid + 1 <= qr) add(rs(x), mid + 1, r, ql, qr, v);
pushup(x);
}
int query(int x, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return nds[x].sum2;
pushdown(x, l, r);
int mid = l + (r - l >> 1), ans = 0;
if (ql <= mid) ans = query(ls(x), l, mid, ql, qr);
if (mid + 1 <= qr) ans = (ans + query(rs(x), mid + 1, r, ql, qr)) % MOD;
return ans;
}
}seg;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), vl[i] = a[i];
std::sort(vl + 1, vl + n + 1);
int vn = std::unique(vl + 1, vl + n + 1) - vl - 1;
for (int i = 1; i <= n; i++) a[i] = std::lower_bound(vl + 1, vl + vn + 1, a[i]) - vl;
for (int i = 1; i <= n; i++) pre[i] = lst[a[i]], lst[a[i]] = i;
for (int i = 1; i <= n; i++) {
seg.add(1, 1, n, pre[i] + 1, i, 1);
ans = (ans + seg.query(1, 1, n, 1, n)) % MOD;
}
printf("%d\n", ans);
return 0;
}随便选一个集合拔掉，相当于随便选一个集合留下来，即任意一个子序列。那么问题就是每次操作可以区间加一，求最多 k 次操作后最长不下降子序列的长度。
显然对一个区间$[l,r]$进行区间加一操作，可能会使答案增大，也可能减小。增大是因为操作后有可能能接上$[1,l-1]$中的某个序列从而更新答案，减小是因为操作后有可能和$[r+1,n]$中的某个序列断开。那么显然可以贪心，每次直接将操作右端点设为$n$，这样答案就一定不会减小了。
于是可以 DP，设$dp[i][j]$表示前 i 个位置，第 i 个位置被增加了 j 次的最长不下降子序列长度，那么有：
$$dp[i][j]=\max_{k=1}^{i-1}\max_{l=0}^jdp[k][l]+1\ (h[k]+l\le h[i]+j)$$
可以用二维树状数组优化一下。把 i 滚动掉，第一维存 j ，第二维存$h[i]+j$，那么显然要求的就是二维前缀最大值，用二维树状数组维护即可，复杂度$O(nk\log(nk))$。
#include<cstdio>
int n, k, a[10100], ans;
inline int max(int a, int b) { return a > b ? a : b; }
struct ft {
int n, m, ft[510][6010];
inline int lowbit(int x) { return x & -x; }
inline void assign(int x, int y, int v) {
for (int i = x + 1; i <= n; i += lowbit(i))
for (int j = y; j <= m; j += lowbit(j)) ft[i][j] = max(ft[i][j], v);
}
inline int query(int x, int y) {
int ans = 0;
for (int i = x + 1; i >= 1; i -= lowbit(i))
for (int j = y; j >= 1; j -= lowbit(j)) ans = max(ans, ft[i][j]);
return ans;
}
}ft;
int main() {
scanf("%d%d", &n, &k);
ft.n = k + 1;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), ft.m = max(ft.m, a[i] + k);
for (int i = 1; i <= n; i++)
for (int j = k; j >= 0; j--) {
int v = ft.query(j, a[i] + j) + 1;
ans = max(ans, v);
ft.assign(j, a[i] + j, v);
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P4158
之前在 cf 上见过做法类似的题，当时还以为也就绿题或蓝题难度，没想到在 luogu 是紫的(好水)。
每行是独立的，所有可以对每行分别考虑。设$f[i][j][k]$表示第 i 行前 j 个位置刷了 k 次最多能刷对几个位置，然后这就是一个背包，预处理两种颜色的前缀和(用来算区间里有几个位置是这种颜色，从而算出刷某个区间为某个颜色能刷对几个位置)，然后直接$O(nm^2t)$ DP 即可。
但 t 的范围比较大，这样会 TLE。显然 n 个位置最多只会刷 n 次，所以可以把 k 的枚举上界从 t 改为 m ，复杂度优化到$O(nm^3)$，可行。
求出 f 之后，设$g[i][j]$表示前 i 行共刷了 j 次的答案，还是背包，直接 DP 即可。
#include<cstdio>
#include<cstring>
int n, m, t, a[55][55], cnt[55][55][2], f[55][55][2510], g[55][2510];
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d%d%d", &n, &m, &t);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%1d", &a[i][j]), cnt[i][j][a[i][j]]++;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) cnt[i][j][0] += cnt[i][j - 1][0], cnt[i][j][1] += cnt[i][j - 1][1];
memset(f, -0x3f, sizeof f);
for (int i = 1; i <= n; i++) {
f[i][0][0] = 0;
for (int j = 1; j <= m; j++)
for (int k = 0; k <= m; k++) {
f[i][j][k] = f[i][j - 1][k];
for (int l = 0; l < j; l++)
if (k) f[i][j][k] = max(f[i][j][k], f[i][l][k - 1] + max(cnt[i][j][0] - cnt[i][l][0], cnt[i][j][1] - cnt[i][l][1]));
}
}
memset(g, -0x3f, sizeof g);
g[0][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= t; j++)
for (int k = 0; k <= j; k++) g[i][j] = max(g[i][j], g[i - 1][j - k] + f[i][m][k]);
printf("%d\n", g[n][t]);
return 0;
}https://www.luogu.com.cn/problem/P4161
将每个数向它对应的数连有向边，那么图上会出现若干个简单环，而变回原序列所需的次数显然就是环的大小的最小公倍数。问题转化为若干和为 n 的数的可能的 lcm 的个数。考虑把 lcm 质因数分解为$\prod_{i=1}^mp_i^{k_i}$，则这个 lcm 能被凑出来当且仅当$\sum_{i=1}^np_i^{k_i}\le n$。因此可以线性筛预处理 n 以内的所有质数，然后设$dp[j]$表示质数幂和等于 j 的方案数，这就是一个背包问题，直接 DP 即可。
#include<cstdio>
int n, prime[1010], pcnt;
long long dp[1010], ans;
bool isprime[1010];
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i++) isprime[i] = true;
for (int i = 2; i <= n; i++) {
if (isprime[i]) prime[++pcnt] = i;
for (int j = 1; j <= pcnt && i * prime[j] <= n; j++) {
isprime[i * prime[j]] = false;
if (!(i % prime[j])) break;
}
}
dp[0] = 1;
for (int i = 1; i <= pcnt; i++)
for (int j = n; j >= 1; j--)
for (int pk = prime[i]; pk <= j; pk *= prime[i]) dp[j] += dp[j - pk];
for (int i = 0; i <= n; i++) ans += dp[i];
printf("%lld\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P5752
显然只要使$\sum_{i=1}^n(x_i-\overline x)^2$最小，观察一下$\overline x$的公式$\overline x=\dfrac{\sum_{i=1}^nx_i}{n}$，发现上面的和式就是所有格子的和，所以$\overline x$可以直接算出来，然后直接五维 DP，设$dp[i][x1][y1][x2][y2]$表示分割了 i 次，当前没分割的矩形左上角和右下角坐标分别为$(x1,y1),(x2,y2)$时$\sum_{j=1}^i(x_j-\overline x)^2$的最小值，转移只要枚举在哪分割即可。
#include<cstdio>
#include<cstring>
#include<cmath>
int n, a[9][9], suma[9][9];
double dp[15][9][9][9][9], avg;
inline int sum(int x1, int y1, int x2, int y2) { return suma[x2][y2] - suma[x1 - 1][y2] - suma[x2][y1 - 1] + suma[x1 - 1][y1 - 1]; }
inline double min(double a, double b) { return a < b ? a : b; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= 8; i++)
for (int j = 1; j <= 8; j++) scanf("%d", &a[i][j]), suma[i][j] = a[i][j] + suma[i - 1][j] + suma[i][j - 1] - suma[i - 1][j - 1], avg += a[i][j];
avg /= n;
memset(dp, 0x42, sizeof dp);
for (int i = 1; i <= n; i++)
for (int x1 = 1; x1 <= 8; x1++)
for (int y1 = 1; y1 <= 8; y1++)
for (int x2 = x1; x2 <= 8; x2++)
for (int y2 = y1; y2 <= 8; y2++) {
if (i == 1) dp[i][x1][y1][x2][y2] = (sum(x1, y1, x2, y2) - avg) * (sum(x1, y1, x2, y2) - avg);
else {
dp[i][x1][y1][x2][y2] = 1e9;
for (int x = x1; x < x2; x++)
dp[i][x1][y1][x2][y2] = min(dp[i][x1][y1][x2][y2], min(dp[i - 1][x1][y1][x][y2] + (sum(x + 1, y1, x2, y2) - avg) * (sum(x + 1, y1, x2, y2) - avg),
dp[i - 1][x + 1][y1][x2][y2] + (sum(x1, y1, x, y2) - avg) * (sum(x1, y1, x, y2) - avg)));
for (int y = y1; y < y2; y++)
dp[i][x1][y1][x2][y2] = min(dp[i][x1][y1][x2][y2], min(dp[i - 1][x1][y1][x2][y] + (sum(x1, y + 1, x2, y2) - avg) * (sum(x1, y + 1, x2, y2) - avg),
dp[i - 1][x1][y + 1][x2][y2] + (sum(x1, y1, x2, y) - avg) * (sum(x1, y1, x2, y) - avg)));
}
}
printf("%.3lf\n", sqrt(dp[n][1][1][8][8] / n));
return 0;
}