【题单】计数专题

https://cplusoj.com/d/senior/contest/69c0c2001363e1a0769fa9ee/problems

P3978 [TJOI2015] 概率论

GF。

CF891E Lust

\(\sum_{a',x} n^{-(\Sigma-\Sigma')-1}\times \frac{(\Sigma-\Sigma')!}{\prod (a_i-a'_i)!}\prod_{x\ne i} a'_i\)。
统计的 \(a'\) 满足 \(0\le \Sigma-\Sigma'<k\)。

GF 描述：\(\sum_{i,0\le s< k} \frac{1}{n}[\frac{x^s}{s!}]e^{x}\prod_{j\ne i} (a_j-\frac{x}{n})\)。
合并一下，等于说求 \(\frac{1}{n}\sum_{0\le s<k}[\frac{x^s}{s!}]e^x F(x)\)，其中 \(\deg F=O(n)\)。
也就是 \(\frac{1}{n}\sum_i f_i\sum_{0\le s<k}s^{\underline i}\)。
\(\sum_{s=0}^{k-1}s^{\underline i}=i!\sum_{s=0}^{k-1} \binom{s}{i}=i!\times \binom{k}{i+1}\)，组合意义表示新增一个选出当前选法是贡献给哪个 \(s\) 的。

TopCoder14170 DivFree

相邻两项 \(A,B\) 满足 \(A>B\) 且 \(A\bmod B= 0\) 就是不合法的。
求出每个长度的不合法段的方案数，然后容斥合并。

CF1221G Graph And Numbers

孤立点最后计算。
容斥：\(f(S)\) 表示集合 \(S\) 内的和不存在。
\(f(\varnothing)-f(0)-f(1)-f(2)+f(0,1)+f(1,2)+f(0,2)\)。

• \(f(1)=2^{连通块数量}\) 每个连通块颜色相同。
• \(f(0,1)=f(1,2)=1\)。
• \(f(0,2)\) 即每个连通块黑白染色。
• \(f(\varnothing)=2^n\)。
• \(f(0)=f(2)\)，那么 0 不能相邻，这是独立集计数。
  • \(n\) 不大，考虑折半搜索，高位前缀和处理限制。

P6276 [USACO20OPEN] Exercise P

一个 \(a\) 的答案是所有置换环长度的 \(\operatorname{LCM}\)。
考虑每个 \(p^{\ge k}\) 的贡献。
暴力 dp 有 \(f_{i,j\lor [p^k|l]}\leftarrow f_{i-l,j}\times \frac{(i-1)!}{(i-l)!}\)，注意是指数部分所以是对 \(P-1\) 取模。
考虑第一次取到 \(p^k\) 的倍数，以后可以乱取，可以预处理。
前面的递推：\(f_{i,1}=\sum_{p^k|l}f_{i-l,0}\times \frac{(i-1)!}{(i-l)!},f_{i,0}=(\sum_{l} f_{i-l,0}\times \frac{(i-1)!}{(i-l)!})-f_{i,1}\)。
那么 \(f_{i,1}\) 可以按照同余系转移，维护增量。\(f_{i,0}\) 的那个求和也可以维护增量。
总复杂度 \(O(n^2)\)。

AT_abc144_f [ABC144F] Fork in the Road

可以求出每个点对于点 1 的贡献，那么修改一条边就可以 \(O(1)\) 求。复杂度 \(O(nm)\)。

AT_arc102_c [ARC102E] Stop. Otherwise...

对于 \(s\)，会有若干冲突的对。那么答案 GF 是形如 \((1+x)^{a}(\frac{1}{1-x})^b(\frac{2}{1-x}-1)^{c}\)，最后一项等于 \(\frac{1+x}{1-x}\)。
维护增量就好。

AT_arc096_c [ARC096E] Everything on It

T4