这篇博客只会写一些题解,基础内容和另外一些题,见:
- 容斥基础
- 反演基础
P4492 [HAOI2018] 苹果树
Hint:相当于求所有形态二叉树的路径和,考虑一条边 \((u,fa_u)\) 的贡献.
记子树 \(u\) 的大小为 \(sz_u\),把所有路径和拆成每条边会贡献到多少条路径里面,发现这就是 \(sz_u\times(n-sz_u)\). 我们考虑从小到大枚举每个标号,并且枚举子树大直接计算答案.
由于二叉树是一个节点一个节点生成的,相当于有标号. 考虑标号的影响,填到标号 \(i\) 时,前面标号任意,贡献为 \(i!\);子树中标号贡献 \(sz_i!\). 考虑子树生成的方案数,剩下的点选 \(sz_i-1\) 个,其他点全部填到子树外面,方案数为 \({(n-sz_i-1)!\over (i-2)!}\).
最终答案的式子就是:
考虑二叉树的生成方案有 \(n!\) 种,因为加入节点 \(i\) 时有 \(i\) 种位置,加入之后总位置又会增加 \(1\). 所以最终答案就是上面那个式子.
P1450 [HAOI2008] 硬币购物
Hint:背包预处理,枚举子集暴力容斥.
硬币数量的限制不好处理,容斥成不考虑限制的方案数减去所有不合法的方案数. 总方案数可以直接完全背包预处理,考虑钦定硬币种类的一个子集超出了限制,子集预先选 \(d_i+1\) 个硬币,方案数是预处理好的. 直接容斥即可.
P10681 [COTS 2024] 奇偶矩阵 Tablica
Hint:考虑一个题意转化:\(a\) 种颜色 \(1\) 个球,另外 \(b\) 种颜色 \(2\) 个球,\(c\) 个有序集合放一个球,\(d\) 个有序集合放两个球且不能有相同颜色的方案数.
上述转化相当于把 \(a\) 行的 \(1\) 和 \(b\) 行的 \(2\) 分配给 \(c,d\) 列. 首先 \(a,b,c,d\) 满足三个等式.
这是易于枚举的,下面考虑确定的 \(a,b,c,d\) 如何统计方案.
把 \(a+2b\) 个球排列,按顺序分配给 \(c + d\) 个集合,考虑容斥掉非法的情况:
- \(\{x,y\}\) 和 \(\{y,x\}\) 被重复统计.
- 出现 \(\{x,x\}\) 的集合.
前者的处理可以在最后答案除以 \(2^d\),后者考虑容斥,钦定 \(t\) 个集合放相同元素,于是剩下的 \(a+2(b-t)\) 个球排列,最终式子为:
P11030 『DABOI Round 1』Blessings Repeated
Hint:预处理出 \(T\) 每个区间被 \(S\) 包含的子序列数量,爆搜 \(T\) 的分拆统计答案.
\(k\) 很大,显然不能直接暴力做. 考虑最终的方案一定形如从 \(k\) 串中选择若干个,依次匹配 \(T\) 中的一段. 先预处理 \(f_{i,l,r}\) 表示前缀 \(i\) 中 \(T[l\cdots r]\) 的子序列方案数,有转移:
然后直接爆搜划分统计答案即可.
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int maxn = 5e3 + 10, maxm = 1e1 + 5, mo = 998244353;
const int inv[11] = {0, 1, 499122177, 166374059, 291154603, 856826403, 641926577, 376916469, 421456191, 712324701, 370705776};
ll n, m, k; char s[maxn], t[maxm];
ll f[maxn][maxm][maxm], ans;inline int add(const int &x, const int &y) {return x + y >= mo ? x + y - mo : (x + y < 0 ? x + y + mo : x + y);}
inline void upd(ll &x, const int &y) {return x = add(x, y), void(0);}inline ll C(int x) {ll res = 1;for(int i = 0; i < x; i++) (res *= (k - i) % mo) %= mo;return res * inv[x] % mo;
}
void dfs(int p, int cnt, ll res) {if(p > m) return upd(ans, res * C(cnt) % mo);for(int i = p; i <= m; i++) dfs(i + 1, cnt + 1, res * f[n][p][i] % mo);
}int main() {ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> k >> (s + 1) >> (t + 1); n = strlen(s + 1), m = strlen(t + 1);for(int i = 1; i <= n; i++) for(int l = 1; l <= m; l++) for(int r = l; r <= m; r++) {f[i][l][r] = f[i - 1][l][r];if(s[i] == t[r]) upd(f[i][l][r], (l == r ? 1 : f[i - 1][l][r - 1]));} dfs(1, 0, 1);cout << ans;return 0;
}
P9129 [USACO23FEB] Piling Papers G
Hint:考虑数位 DP 预处理出所有区间的答案.
首先差分,转换成求在 \(1\sim x\) 范围的答案. 考虑一个恰当的 DP 方程是 \(f_{l,r,i,j,0/1/2}\) 表示区间 \([l,r]\) 拼出的数字相比于 \(x\) 从低到高 \(i\) 到 \(j\) 位小于/大于/等于的方案数. 转移分讨在加在左边还是右边,以及与 \(x\) 这一位的大小关系即可.
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int maxn = 3e2 + 10, mo = 1e9 + 7;
int n, q, a[maxn], b[20], tot; ll A, B;
int ans[maxn][maxn], f[20][20][3];inline int add(const int &x, const int &y) {return x + y >= mo ? x + y - mo : (x + y < 0 ? x + y + mo : x + y);}
inline void upd(int &x, const int &y) {return x = add(x, y), void(0);}inline int cmp(const int &x, const int &y) {return x == y ? 2 : x > y;}
void calc(ll V, int op) {tot = 0;while(V) {b[++tot] = V % 10, V /= 10;} reverse(b + 1, b + tot + 1);for(int l = 1; l <= n; l++) {memset(f, 0, sizeof f);for(int r = l; r <= n; r++) {for(int i = 1; i <= tot; i++) for(int j = tot; j > i; j--) for(int k = 0; k < 3; k++) {if(a[r] == b[i]) upd(f[i][j][k], f[i + 1][j][k]);else upd(f[i][j][cmp(a[r], b[i])], f[i + 1][j][k]);if(k != 2) upd(f[i][j][k], f[i][j - 1][k]);else upd(f[i][j][cmp(a[r], b[j])], f[i][j - 1][k]);}for(int i = 1; i <= tot; i++) upd(f[i][i][cmp(a[r], b[i])], 2);for(int i = 1; i <= tot; i++) {upd(ans[l][r], op * f[i][tot][0]);upd(ans[l][r], op * f[i][tot][2]);if(i > 1) upd(ans[l][r], op * f[i][tot][1]);}}} return;
}int main() {ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n >> A >> B;for(int i = 1; i <= n; i++) cin >> a[i];calc(A - 1, -1), calc(B, 1);cin >> q;while(q--) {int l, r; cin >> l >> r;cout << ans[l][r] << "\n";}return 0;
}
P4448 [AHOI2018初中组] 球球的排列
Hint:观察到乘积为平方具有传递性,于是维护颜色,DP 状态区分颜色来进行转移.
我们把每一个点的颜色设为序列里面第一个乘积为平方的位置,为了方便 DP,把所有数先按颜色排序.
考虑填一个数的情况,我们可以往同色对插入一个异色来将其变为合法的,所以要讨论颜色之间的关系. 设 \(f_{i,j,k}\) 表示填完前 \(i\) 个数之后有 \(j\) 对与 \(i\) 颜色不同的相邻对,有 \(k\) 对与 \(i\) 同色的相邻对,记录同色的个数 \(cnt\). 转移分类讨论:
- \(i\) 与 \(i-1\) 异色,\(i\) 插入异色对.
- \(i\) 与 \(i-1\) 异色,\(i\) 插入同色对.
- \(i\) 与 \(i-1\) 同色,\(i\) 插入同色球旁边.
- \(i\) 与 \(i-1\) 同色,\(i\) 插入同色对.
- \(i\) 与 \(i-1\) 同色,\(i\) 插入异色对.
分别有转移:
注意边界;滚动数组.
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int maxn = 3e2 + 10, mo = 1e9 + 7;
int n, a[maxn], b[maxn];
int f[2][maxn][maxn];inline int add(const int &x, const int &y) {return x + y >= mo ? x + y - mo : x + y < 0 ? x + y + mo : x + y;}
inline void upd(int &x, const int &y) {return x = add(x, y), void(0);}
inline ll sqr(const ll &x) {return x * x;}int main() {ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i <= n; i++) {cin >> a[i]; b[i] = i;for(int j = 1; j < i; j++) if(sqr(sqrt(1ll * a[i] * a[j])) == 1ll * a[i] * a[j]) {b[i] = j; break;}} sort(b + 1, b + n + 1);f[0][0][0] = 1;for(int i = 1, cnt = 0; i <= n; i++) {int o = i & 1;memset(f[o], 0, sizeof f[o]);if(b[i] != b[i - 1]) {cnt = 0;for(int j = 0; j < i; j++) for(int j0 = 0; j0 <= j + 1; ++j0) {if(j0 <= j) upd(f[o][j][0], 1ll * f[o ^ 1][j0][j - j0] * (i - j) % mo);upd(f[o][j][0], 1ll * f[o ^ 1][j0][j - j0 + 1] * (j + 1) % mo);}}else {for(int j = 0; j < i; j++) for(int k = 0; k <= cnt; k++){if(k > 0) upd(f[o][j][k], 1ll * f[o ^ 1][j][k - 1] * (cnt * 2 - k + 1) % mo);upd(f[o][j][k], 1ll * f[o ^ 1][j + 1][k] * (j + 1) % mo);upd(f[o][j][k], 1ll * f[o ^ 1][j][k] * (i - cnt * 2 + k - j) % mo);}} cnt++;} cout << f[n & 1][0][0];return 0;
}