P10144
如果一个区间 \([L,R]\) 满足条件，则 \(\max(a_i,h-a_i)\) 在 \([L,R]\) 上单谷。
观察到能让 \(\max(a_i,h-a_i)\) 和 \(\max(a_{i+1}, h - a_{i+1})\) 变号的 \(h\) 分割点只有 \(\mathcal{O}(n)\) 个，于是可以用一种类似于扫描线的方法记录每一个符号变动，顺便维护 \(p_i\) 表示从 \(i\) 开始最长的符合要求的区间的右端点。
\(\mathcal{O}(n\log n)\)。
不用调一次过让我很爽。这就是写之前先想清楚自己在写什么的好处。
Update：过不去另外一个版本。这就是 std::set 给我的自信。
P8292
给定 \(n\) 个 \(200\) 位二进制数 \(s_i\)。保证 [相关条件]。
有 \(q\) 次询问，每次给出一个子集 \(S\)，求有多少个 \(\{s_1,s_2,\cdots,s_n\}\) 的子集满足它的 OR 和是 \(S\) 的超集。
注意到一个数至多有一个 \(>\sqrt{V}\) 的质因子。
所有 \(\le \sqrt{V}=44\) 的质因子，共有 \(14\) 个。
对于 \(>44\) 的因子，记录 \(f_{i,S}\) 表示因子 \(i\)，选出若干个数满足或和为 \(S\) 的方案数。
对于每组询问，做 \(\sqrt{V}\) 次 FWT 即可。诶呀过不去
预处理前缀一坨和后缀一坨，然后就只用做 \(\sum c_i\) 次了。
* 题解的容斥我见过，但是没有想出来。反思一下。关于位运算 \(\operatorname{OR}\) 起来有一个典容斥是钦定一些位 \(\operatorname{OR}\) 后为 \(0\)。
P2178
对 \(S\) 建立后缀数组，求出 \(h\) 数组。
有 \(\operatorname{LCP\ lemma}\)，所以我们根据 \(h\) 的大小从大到小加进去。
类似 P10173 做一下，就做完了。
最后需要 \(mx_i\gets\max(mx_i,mx_{i+1}),sum_i\gets sum_i+sum_{i+1}\)。
CF1906K *
分治 FWT。有趣。
怎么说呢。就是，[题目相关解法]。
很难解释。这个是 \(\mathcal{O}(V\log^2 V)\) 的。
P2767
设 \(f_{n,m}\) 为共有 \(n\) 个节点，根度数为 \(m\) 的方案数。
设 \(g_{n}=\sum f_{n,m}\)
则 \(f_{n, m} =\sum{f_{n-k,m-1} g_k}\)
其实不是这样的。不过可以瞎搞搞。
P6453 / SP3734
\(f(a, k)\) 为在序列 \(a\) 中填 \(k\) 个相同数的答案。
设 \(p\) 为区间最小值的位置，则很容易分治。
然后做一个暴力卷积，再算一算组合数就行了。
\(n^3\)。
P8352
设 \(f_{u,1/0}\) 表示选 \(u\) 或不选 \(u\) 的最大独立集。
转移为 \(f_{u,0}=\sum{\max(f_{v,0}, f_{v,1})}\)，\(f_{u,1}=v_u + \sum f_{v,0}\)。
暴力做是直接把 \(f_{u,0/1}\) 压进状态去 dp。这样是 \(\mathcal{O}(n^4k^4)\) 的。不是很行。
观察到 \(f_{u,1}-f_{u,0}\le k\)，且当 \(f_{u,1}<f_{u,0}\) 的时候 \(f_{u,1}\) 其实是无用的。
那么把状态换成 \((f_{u,1}, f_{u,1}-f_{u,0})\) 和 \(f_{u,0}\)（\(f_{u,0}>f_{u,1}\)） 即可。
这样是 \(\mathcal{O}(n^2k^4)\) 的。
P3412
计算出在 \(u\)，从 \(u\to f_u\) 的期望移动步数。
设 \(g_u\) 为 \(u\to f_u\) 的期望步数，\(h_u\) 为 \(f_u\to u\) 的期望步数。
则 \(g_u = \operatorname{deg}(u)\times(\sum_{u=f_v} (g_{v}+1) + 1)\times \frac{1}{\operatorname{deg}(u)}\)
\(h_u=\operatorname{deg}(f_u)\times (\sum (g_v/h_v+1) + 1)\times \frac{1}{\operatorname{deg}(f_u)}\)
可以两次 dfs 计算。
然后直接对于每条边计算贡献就行了。
感觉比高斯消元 / 树上高斯消元高到不知道哪里去了。
P5387
考虑 \(|V|=1\) 的情况。
\(x\) 的后继状态 \(y\) 满足 \(y<x\) 且 \(x\oplus y\le x\)。
思考一下这代表什么。
设 \(x\) 的后缀状态集合为 \(S(x)\)。
则 \(S(x)=S(x-\operatorname{highbit}(x))\cup[\operatorname{highbit}(x), x)\)。
看起来很不错，可惜的是 \(\operatorname{SG}\) 函数并不能简单合并。
归纳法好像可以证明当 \(\operatorname{highbit}(x)=\operatorname{highbit}(y),x<y\) 的时候，\(\operatorname{SG}(x)<\operatorname{SG}(y)\)。
倍增求出所有的 SG，然后 FWT\(^k\) 即可。
int SG[1 << 10];
int main() {
SG[0] = 0;
_rep(i,1,1023) {
set<int> s;
_rep(j,0,i - 1) if((i ^ j) <= i) {
s.insert(SG[j]);
}
for(int j = 0; ; ++j) {
if(s.count(j)) continue;
SG[i] = j; break;
}
}
_rep(i,0,1023) printf("%d\n", SG[i]);
return 0;
}
打一个表，然后可以发现一些更加简单的结论。
\(\operatorname{SG}(i)=i-\operatorname{highbit}(i)+1\)
P5071
考虑普通莫队。是 \(\mathcal{O}(w(V)n\sqrt{n}+n\operatorname{factor}(V))\) 的。可能过不去。
根号分治一下，可以去掉 \(w(V)\)。
P6049 / CF995F(弱化版)
首先一个直白的想法是，设 \(f_{u, k}\) 表示在以 \(u\) 为根的子树内用了 \(k\) 种颜色，其中 \(u\) 是第 \(k\) 种。
这样很难算，如果把「恰好用了 \(k\) 种颜色」这个限制去除，就会很好 dp。
问题是，这样会算重，最后容斥一下就行了。
这个其实就是二项式反演。
- 假如把「\(u\) 是第 \(k\) 种」这个条件扔掉，就是板子。但是这样无法转移。
- 于是钦定 \(u\) 是第 \(k\) 种，就可以方便的转移。
- 把 \(u\) 去掉后可以当做二项式反演来看待。
In Addition：
-
有标号有根树计数
设 \(f_{i}\) 表示 \(i\) 个点的森林数量，\(g_{i}\) 表示 \(i\) 个点的树的数量。
则有 \(g_i=\sum{g_{i-j}f_j\binom{i - 1}{j - 1}}\) （枚举编号最大的那个点的连通块）。 -
无标号有根树计数
类似。见下
CF888F
[题目相关解法]。
注意钦定第一个和最后一个是不一样的。测死我了/px
CF1781F
考虑计数 \(n\) 次操作后的总和法方案数概率之和。
如果第 \(n-1\) 次操作不是合法括号串，第 \(n\) 次操作必定无法弥补。
于是考虑设 \(f_{i, j}\) 为操作 \(i\) 次，外面需要 \(j\) 个 () 来修正的概率之和。
转移可以直接 \(\mathcal{O}(n)\) 暴力转移，总复杂度 \(\mathcal{O}(n^3)\)。
实现有点困难。（？）
设 \(f[i][0/1][0/1/2/3][j]\) 表示 \(x(x)x\) 或 \(x)x(x\) 处理完第几个 \(x\) 了。
枚举这一个 \(x\) 用了几次操作转移。
UOJ 310 / CF1906K(加强版)
拉一个 FWT 板子下来，观察一下。
发现数组里只有两个值：\(3\) 和 \(-1\)。
我们可以先通过 FWT 的线性性拉出所有值的和，解一个鸡兔同笼方程组即可。
高级 \(\mathcal{O}(V\log V)\)。
CF1043F
答案并不会超过 \(w(V)\)。
枚举答案，然后 \(\gcd\) 容斥一下可以求出方案数，进而计算可行性。
CF724F
对于 无根不同构树计数 钦定根为重心。
设 \(f_{u, i, j}\) 表示 \(u\) 个点，根塞了 \(i\) 个子树，最大子树大小为 \(j\) 的方案数。
然后是一个比较 trivial 的东西。
UVA10829
\(U+V+U\)。
类似优秀的拆分的套路，枚举（\(|U|\)）然后枚举关键点。
求一下两个关键点之间的 \(\operatorname{LCP}\) 可以 \(\mathcal{O}(1)\) 计算答案。
CF1060F
考虑给每条边一个 \([0, 1]\) 的随机变量钦定它被删除的顺序。
设 \(F_u(x)\) 为当 \(u\to\) 根路径上最大值为 \(x\) 时子树的贡献（\(\times (1/2)^k\) ）的期望。
则有
\(F_u(x)=\prod_v (xF_v(x)+\frac{1}{2}\int_x^1F_v(t)\mathrm{d}t)\)
维护多项式，直接暴力计算就可以了。
答案 \(=\sum_{p} (1/2)^{cnt(p)}\times \frac{1}{(n-1)!}\)，其实就是 \(F_{root}(0)\)。
（\(P(A)=E(I_A)=E((1/2)^{cnt(p)})\)）。
这个看起来很厉害，以后我不知道会不会遇到类似的题。
三维偏序 - 二项式反演做法
设 \(f_i\) 为至少有 \(i\) 维偏序的 \((a, b)\) 的对数，\(g_i\) 表示正好有 \(i\) 维偏序的对数。
有 \(g_3=f_3=-f_3+\binom{3}{2}f_2-\binom{3}{1}f_1+\binom{3}{0}f_0\)
于是我们只需要知道 \(f_2,f_1,f_0\) 即可，这是 \(\mathcal{O}(n\log n)\)。
另解是对于 \((a,b,c)\) 和 \((a',b',c')\)，对答案的贡献要么是 \(3\)，要么是 \(1\)。
类似 UOJ310 一样解方程即可。
CF1295F
结论：在 \(n\) 种元素中选出 \(m\) 个的方案数是 \(\binom{n + m - 1}{m}\)。
证明 #1：可以理解为把 \(m\) 个小球塞到 \(n\) 个盒子里的方案数，插板法即可。
证明 #2：[1]01010011 \(1-n,0-m\)。[相关证明]。
将值域分成 \(\mathcal{O}(n)\) 段。
设 \(f_{i, j}\) 表示第 \(i\) 个数在第 \(j\) 段的方案数，转移为
\(f_{i,j}=\sum_{i'<i} \binom{\operatorname{len}[j] + (i-i')-1}{i-i'}\sum_{j'>j} f[i'][j']\)。
前缀和优化转移可以做到 \(\mathcal{O}(n^3)\)。
\(\binom{a+1}{b+1}=\frac{a!(a+1)}{b!(b+1)(a-b)!}=\binom{a}{b}\frac{a+1}{b+1}\)
P3643
\(\binom{a+1}{b}=\frac{(a+1)!}{b!(a+1-b))(a-b)!}=\binom{a}{b}\frac{a+1}{a+1-b}\)
设 \(f_{i, j}\) 表示第 \(i\) 个数在第 \(j\) 段的方案数，转移为
\(f_{i,j}=\sum_{i'<i} (\sum_{j=0}^{cnt - 1}\binom{len}{j + 1}\binom{cnt-1}{j})\sum_{j'>j} f[i'][j']\)。
（\(cnt\) 为能选的点的个数）
观察这个式子。
\( \begin{aligned} &\ \ \ \ \sum_{j=0}^{cnt - 1}\binom{len}{j + 1}\binom{cnt-1}{j}\\ &=\sum_{j=0}^{cnt - 1}\binom{len}{len - 1 - j}\binom{cnt-1}{j}\\ &= \binom{len + cnt - 1}{len - 1} \end{aligned} \)
CF1765G
如果直接做是 \(n\) 次操作，观察限制是 \(\frac{3}{4}n\) 左右，
所以只需要稍微优化一下就可以了。
随机化，一次性问两个值。当 \(s_2=s_i\) 且询问了 \(P\) 的时候可以得到 \(s_{i-1}\)，否则当询问了 \(Q\) 的时候也可以得到 \(s_{i-1}\)。
ARC151E
-
\(\operatorname{LCS}(s, t)\neq \varnothing\) 取 \(\operatorname{LCS}(s, t)\) 即可。
-
否则直接跑一个多源汇最短路即可，字符串相邻的字符连边，边权 \(2\)。
CF1943D2
容斥，钦定有 \(k\) 个点是 “坏” 的（\(a_{i-1} + a_{i+1} < a_i\))。
注意到，假如 \(i\) 是坏的，则与 \(i\) 相邻的点都不可能是坏的。
设 \(f_{i, j, k}\) 表示 \(a_i\) 取 \(j\)，\(1\sim i-1\) 共有 \(k\) 个坏点。
（实际上只需要记录 \(k\) 的奇偶性就行了）
转移为
- 钦定 \(i-1\) 是坏的，\(f_{i, j, k}=\sum (L-l-j) f_{i-2,l,k \oplus 1}\)。
- 不管，\(f_{i, j, k} = \sum f_{i-1,l,k}\)。
ABC242Ex
\(E(ans)=\sum_{i\ge 1} P(ans\ge i)\)
\(P(ans\ge i)\) 表示，\(i-1\) 次操作后存在一个点没有被染色的概率。
于是容斥。期望不好容斥，但是概率还是好算滴。
int ans = 0;
_rep(i,1,(1 << n) - 1) {
int cnt = 0;
_rep(j,1,m) {
bool flag = true;
_rep(k,0,n - 1) if(((i >> k) & 1) && l[j] <= k && k <= r[j]) flag = false;
if(flag) ++cnt;
}
int prob = 1ll * cnt * fpm(m, p - 2) % p;
if(__builtin_popcount(i) & 1) ans = (ans + fpm(1 + p - prob, p - 2)) % p;
else ans = (ans - fpm(1 + p - prob, p - 2) + p) % p;
debug("i = %d, cnt = %d, ans = %d\n", i, cnt, ans);
}
outln(ans);
暴力验证程序。
CF1799G
被脑测了。一开始不会做没有 \(t_i\) 限制的。
没有 \(t_i\) 限制时，答案为 \(\frac{n!}{\prod c_i!}\)。
有 \(t_i\) 限制的时候可以容斥。
设 \(f_{i, j}\) 表示前 \(i\) 组，有 \(j\) 个人违反了规则，指向了自己的组的方案数。
\(g_{i, j}\) 表示第 \(i\) 组，有 \(j\) 个人违反了规则，指向了自己的组的方案数。
（方案数指 \(\frac{1}{\prod c_i!}\)。）
\(g\) 的转移：
（枚举人 \(k\)，省略第一维即第几组）
\(g_{j}=\sum_{i=0}^{c_k} g'_{j-i}\times \binom{tot-(j-i)}{i}\times (c_k-i)!^{-1}\)
转移 \(\mathcal{O}(n^2)\)。
\(f\) 的转移就是一个背包。这个也是 \(n^2\)。
没调，直接一次过样例！爽爽爽！
AT_tdpc_string
计数 \(\sum{a_i}=n,|a|=m\) 的个数可以简单 dp。
这个和 盒子小球 类模型没有关系。
\(\mathcal{O}(n^2)\)。
ABC214G
对于环可以容斥，设 \(f_{i, j, k}\) 表示前 \(i\) 个数选了 \(j\) 个，其中 \(i-i+1\) 的边状态是 \(k\) 的方案数。
然后这个是很好 dp 的。
预处理可以拆边然后转化成一个组合数问题。
P9989
上帝造题七分钟 III。
ABC267G
设 \(f_{i, j}\) 表示前 \(i\) 个数，共有 \(j\) 个 < 关系的方案数。
则分情况讨论：
-
Case 1. 不增加新的
<。- 放在开头
- 放在某一个相同 \(a\) 的后面
- 放在一个
<的中间
-
Case 2. 增加新的 '<'
- 除 Case 1 以外的所有情况
直接 dp 即可。
P9454
题目实际上是这个意思。
- 去掉 \(1\) 号节点是若干棵树
- 随机 dfs，求 \(\forall i, \operatorname{E}(\operatorname{dfn}_i)\)。
在同一棵树内，（钦定一个根），考虑 \(v\) 对 \(u\) 的 dfn 序贡献。
- \(v\) 为 \(u\) 的祖先，贡献为 \(1\)。
- \(v\) 在 \(u\) 的子树内，贡献为 \(0\)。
- 其他情况，贡献为 \(\frac{1}{2}\)，考虑方式是，在 \(\operatorname{LCA}\) 上，相互都是等价的，各有 \(\frac{1}{2}\) 的概率在前面。
总之，同一棵树内 \(u\) 的贡献总和是 \(\sum_{rt} \frac{tot+cnt(anc)-cnt(sub)}{2}\)
这个可以使用换根 dp 求。
接下来考虑子树之间的贡献。
子树 \(v\) 对子树 \(u\) 的贡献是 \(siz_v\times \frac{siz_v}{siz_v+siz_u}\)
把所有相同大小的子树放在一起处理就行了。
本题难点：读题。
一次过！nice。
P5303
AT_arc101_c
答案为 \(\sum_{S\subset \mathbb{E}} f(S)(-1)^{|S|}\)，其中 \(f(S)\) 的含义为 \(S\) 集合内的边都不被染色的方案数。
\(f(S)=\sum{\frac{x!}{2^{x/2}\times (x/2)!}}\)，\(x\) 为一个连通块之内点的个数。
设 \(f_{u, i, j}\) 代表 \(u\) 子树内，与 \(u\) 相连的连通块大小为 \(i\)，一共选出了 \(j\) 个没被干掉的边的 \(\sum g(x)\)。
实际上，我们只关心 \(j\) 的奇偶性，因此只需要保存 \(0/1\)。
转移可以很简单地 \(\mathcal{O}(siz_usiz_v)\) 地转移，这样总复杂度是 \(\mathcal{O}(n^2)\)。
CF997D
首先发现，两棵树是独立的。
考虑设 \(f_{u, k}\) 表示在节点 \(u\)，走 \(k\) 步后回到节点 \(u\) 的方案数。
好难啊，改一下状态定义。
设 \(f_{u, k}\) 表示在节点 \(u\)，走 \(k\) 步不经过 \(u\) 的父亲的方案数，\(g_{u, k}\) 表示从 \(u\) 的父亲开始，不经过 \(u\) 的方案数，\(h_{u, k}\) 表示没有任何限制的方案数（都要回到 \(u\)）。
\(f_{u, k}=\sum_{v}\sum_{y} f_{u, y}\times f_{v, k - y - 1}\)。
\(g_{u, k}=\sum_{v\in g[fa], v\neq u}\sum_{y}g_{u, y}\times (g/f)_{v, k-y-1}\)。
然后你发现，对于所有相同的 \(fa\) 和 \(y\)，我们可以快速计算系数之和。
然后就可以非常好的做了。
CF382E
考虑设 \(f_{a, b, c, d}\) 表示用 \(a\) 个有标号的点组组成了大小为 \(b\) 的森林，其中最大匹配为 \(c\)，\(d\) 表示有没有子树的根是可以取的。
\(b\in [1, 2], d\in [0,1]\)。
设 \(g_{a, b, c}\) 表示用 \(a\) 个有标号的点组成的有根树，最大匹配为 \(b\)，根能不能取为 \(c\) 的方案数。
然后可以用 \(g\) 去转移 \(f\)。
In Addition:
无标号无根树计数。
转化为一个类似完全背包，但是不是完全背包的问题。（在一类里选 \(k\) 个的系数是不一样的）
只能转化为多重背包，然后平方 \(\log\) 或者 平方 \(\times\) 度数平方。
CF917D
Matrix-Tree 和拉格朗日插值
在树上的边边权为 \(x\)，不在树上的边边权为 \(1\)，跑一遍 Matrix-Tree，
最后算出来的多项式中，\(x^k\) 项的系数就是 \(k\) 的答案。
但是直接跑是 \(\mathcal{O}(n^5)\) 的，不可接受。注意到答案必然是一个 \(n\) 次多项式，那么代 \(n\) 个值进去插值就行了。
容斥
实际上是二项式反演。钦定 \(k\) 条边和原树一样。
那么剩下的方案数是 \(\prod a_i\times n^{k - 2}\)。（结论）
- 组合意义
\(\prod a_i\) 可以理解为在每个连通块内选一个点的总方案数。 - 代数推导
设 \(f_{u, k, 0}\) 表示不考虑 \(u\) 所在的连通块，\(\prod a_i\)，\(f_{u, k, 1}\) 表示暂时的 \(\prod a_i\)。转移是类似的，但是没有组合意义清晰。
P10175
考虑把 \(a_i + |S|\) 拆成 \(\lfloor\frac{|S|}{U}\rfloor\times U + |S|\bmod U + a_i\)。
根据乘法分配律，前面部分不可能选超过 \(k\) 项。
设 \(f_{u, i, k}\) 表示在 \(u\) 子树中选了 \(i\) 项，其中分配律展开后有 \(k\) 个 \(U\) 相乘的方案数。
CF1707D
题目要求：对于所有 \(1\le i\le k\)，满足 \(S_i\neq S_{i - 1}\)。
容斥，对于所有 \(T\subseteq \{1,2,\cdots, k\}\) 求 \(f(T)\) 表示
- \(T\) 内的满足 \(S_i=S_{i - 1}\)。
- 其他的任意。
我们对于 \(|T|\) 分大小讨论，有：\(\sum_{i}\sum_{|T|=i} f(T)\)。
假如已经确定了 \(|T|\)，那么所有 \(f(T)\) 之和就是将 \(S\) 分成 \(k - |T|\) 段，使得每段内都相等的方案数。
注意，假如 \(S = [1,1,1], n - |T|=2\)，则 \([[1, 1], [1]]\) 和 \([1, [1, 1]]\) 应该被视为不同的分段方式，因为这些分段方式所对应的 \(T\) 是不一样的。
一组分段方式对应一个 \(T\)，计数 \(T\) 就是计数分段方式。
设 \(g_{x}\) 表示选出 \(x\) 个 \(S\) 的方案数。我们把这 \(x\) 个 \(S\) 视为每一段的代表。
则 \(g_x\times \binom{n-1}{x-1}\) 就是 \(\sum_{|T|=n - x} f(T)\)。
不过等一下，如果容斥计数是对于每个 \(T\) 计数一遍，那么 \(g_x\) 是什么？
\(g_x\) 需要保证方案互不相同吗？需要，因为 \(g_x\) 并没有什么特殊的式子，它完全是为了好 dp 和计算 \(f\) 来设计的。
容斥对于一种相同方案可能计数多次的根本原因在于，它的计数标准并不是方案，而是集合。
怎么转移不会了
设 \(f_{u, x}\) 表示在 \(u\) 子树内，活的最久的点延续到了 \(x\) 时刻的方案数。
分类讨论
-
根节点延续到了 \(x\) 时刻。
任何子节点都可以在任意时刻被删除。
\(f_{u, x}=\prod_v \sum_{i\le x} f_{v, i}\)。 -
根节点在 \(x\) 前面某一个时刻寄了。
枚举剩下来哪一个子节点，和根节点啥时候寄了，于是 \(f_{u, x} = \sum_{v}(f_{v, x}\sum_{t<x}\prod \sum_{i\le t} f_{v',i})\)
对于后面这坨，预处理一下后缀积就行了。
P4495
裴蜀定理：存在 \(x,y\)，满足 \(ax+by=c\) 的充要条件是 \(\gcd(a, b)|c\)。
对于多个整数，情况类似。
题意即为回答有多少个子集 \(S\) 满足 \(\gcd(S, P)|w_i\)。
做一个 \(\gcd\) 容斥即可。
P7525 / P10272
结论：字符串增长速度要么等差数列，要么等比数列。
考虑 border 的最小周期，它要么在 \(\log\) 次增长后到底尽头，要么无限增长。
另一个结论：若 \(ST=TS\)，则 \(S\) 和 \(T\) 有相同周期。
标签：frac,sum,times,跨越,mathcal,binom,天堂,operatorname From： https://www.cnblogs.com/fjy666/p/-/2024-AprilExulans.AIC：很荣幸，能够在最后，遇到你们。