## 20230105：
### CF1770E
概率期望DP。若确定了树的最终形态，则期望很好计算。
易得，$preans = \frac{2}{k(k-1)} \sum_{x} (k-siz_x)siz_x$ 。
设 $f_i$ 表示第 $i$ 个点上有蝴蝶的概率，则一开始 $f_i$ 由输入决定。
之后 $f_u=f_v=\frac{2}{f_v+f_u}$ 。
然后是一堆的细节/kk
没一遍过：细节爆炸。
### CF6D
DP，但是用搜索过了。
dfs(x,y) 表示已经攻击到第 x 个人，共攻击了 y 次。
然后爆搜。
### ABC243F
DP，巧妙的。
推出每个的概率，设 $f_{i,j,k}$ 表示前 $i$ 个物品选了 $j$ 个选了 $k$ 次的概率。
$$f_{i,j,k}=f_{i-1,j,k}+( \sum_{x=1}^k \frac{p_i^t}{x!}f_{i-1,j-1,k-x})$$
然后预处理一些东西，注意一些细节就可以了。
### P3919&P3834
主席树板子。
---
## 20230106:
### CF1771F
主席树很板子的题，但是INF设小了，改完后没开 long long 见了几次祖宗。
### CF1000F
主席树很板子的题，有点像1771F的弱化版，但是一遍过好诶。
### CF643D
巧妙的转化。找到关系后可以将其转化成DAG，搞个最长路就可以了。
但是犯了很sb的错误，由于过于sb，在此不叙述。
### CF466D
要观察性质，CF官方标签有个 DP 。先将每个 $a_i$ 变成 $h-a_i$ ，再将 $a_i$ 差分，设差分数组为 $dis_i$ ，易发现，若 $abs(dis_i) > 1$ ，则必定无解，再分类讨论一下 $dis_i==0/1/-1$ 就可以了。
### P5410
扩展KMP模板题。
### P6114
Lyndon分解板子。
---
## 20230107
### P1638
最小表示法板子。
### CF710F
正解要二进制拆分，但是不会（，所以大力暴力用 Hash 维护。
你会发现字符串的长度的总数不会超过 $\sqrt {10^5}$ ，但是注意卡自然溢出，所以双哈希（
### P4474
网络流经典套路，黑白染色，大水题。
~~[双倍经验](https://www.luogu.com.cn/problem/P2774)~~
### P8215
建图有一手的网络流，有点毒瘤。
但是搞清楚之后会发现很有意思也很奇妙。
---
## 20230108
### SP287
二分答案然后网络流判断。
将源点设为 0 ，1 设为汇点。
对于每次网络流，将源点连向特殊点连边，流量为 1 ，再将每对边的起点与终点连一条流量为当前二分的 mid 的边，然后跑网络流，判断最大流是否大与等于 k 。
因为已经限定了每条边经过的次数不超过 mid 次，所以最大流就是有多少个点能在 mid 的限制下到达 1 号点。
4.07s 时限，开个 long long 超时（
### CF468B
名字都叫做2-SAT了，那必然用并查集啊（
判断每个数能不能放到 A/B 集合中，分情况讨论，用并查集瞎搞就可以力。
---
## 20230110
### UVA1391
2-SAT ，根据年龄大小将其分为 0(A/B) ，1(C) ，再根据题目中所给的限制连边即可。
### P2158
数学，随便推一下就会发现：
$$ ans =
\begin{cases}
0, & \text{if }n\text{==1} \\
2\varphi (n-1)+1, & \text{if }n\geq\text{ 2}
\end{cases}$$
然后就可以力!
### ABC266G
容斥，或者排列组合！
设要填 $A$ 个 $R$ ，$B$ 个 $G$ ，$C$ 个 $B$ ，以及有 $K$ 个 $RG$ 。
易得，方案数为 $ \dbinom {(B-K)+(K+C+1)-1}{(K+C+1)-1} = \dbinom {B+C}{C+K}$ 。
因此最终结果为$\frac{(A+C)!K!}{(A-K)!C!}\times \dbinom {B+C}{C+K}$ 。
---
## 20230111
### ABC259H
分情况考虑。
当 $k\ge n$ 时，考虑动态规划，设 $f_{i,j}$ 为从这个颜色 $c$ 走到 $(i,j)$ 这个点的路径数， $f_{i,j}=f_{i-1,j}+f_{i,j-1}+[a_{i,j}==c]$ 。
当 $k\le n$ 时 考虑枚举起点 $(x,y)$ 与终点 $(q,p)$ ，然后组合计数，有 $\dbinom {q-x+p-y}{q-x}$ 条路径。
### CF1227F2
设 $f_i$ 表示比原来多对了 $i$ 个的方案数，显然有对称性，即 $f_i==f_{-i}$ ，而要求的是 $\frac {k^n-f_0}{2}$ 。
设可以产生差异的位置数为 $m$ ，则：
$$f_0=\sum_{i=0}^{\left \lfloor \frac{m}{2} \right \rfloor } k^{n-m}\times C^i_m\times C_{m-i}^i\times (k-2)^{m-2\times i}$$
然后就可以力。
---
## 20230112
### CF1227F1
CF1227F2 弱化版，思路一样。
### CF997C
一道推式子神题。
设 $f_{i,j}$ 表示 $i$ 行 $j$ 列的颜色相同，其他什么颜色不管， $g_{i,j}$ 表示恰好有 $i$ 行， $j$ 列的颜色相同。
$$f_{i,j}=\sum_{k=i}^n\sum_{t=j}^n \dbinom {k}{i}\dbinom {t}{j} g_{k,t}$$
这个东西是一个二维的二项式反演。
设
$$g_{i,j}=\sum_{k=i}^n\sum_{t=j}^n a_k a_t f_{k,t}$$
将 $f_{i,j}$ 关于 $g$ 的递推式代入。
$$g_{i,j}=\sum_{k=i}^n\sum_{t=j}^n a_k a_t \sum_{x=k}^n\sum_{y=t}^n \dbinom{x}{k}\dbinom{t}{y}g_{x,y}$$
$$g_{i,j}=\sum_{x=i}^n\sum{y=j}^n g_{x,y} \sum_{k=i}^na_k\dbinom{x}{k}\sum_{t=j}^na_t\dbinom {y}{t}$$
后面的式子详见：[tytyty](https://www.luogu.com.cn/blog/tytyty/jin-cheng-biao) 。
### P2742
二维i凸包板子。
---
## 20230113
### P7704
我们考虑对每个数质因数分解，然后需要删除的数就是出现次数为奇数的质数。
### P8916
设 $f_{u,j,k,c}$ 表示现在在 $u$ 的子树中有 $j$ 个黑色 $k$ 个白色且当前节点颜色为 $c$ 的方案数。
$$f_{u,j,k,0}= \sum_{v \in son_u} max(f_{v,j,k,1},f_{v,j+1,k,0})+(j+1)\times w_x$$
$$f_{u,j,k,1}= \sum_{v \in son_u} max(f_{v,j,k,0},f_{v,j,k+1,1})+(k+1)\times w_x$$
---
## 20230114
### CF1476F
我们设 $f_i$ 表示第 $i$ 个灯笼最多能照亮多少它的前缀。
若前 $i-1$ 盏灯无法照亮第 $i$ 盏，直接忽略， $f_i=f_{i-1}$ 。
当 $i$ 面向右边， $f_i=max(f_{i-1},i+p_i)$ ，其中 $f_{i-1}\geq i$ 。
当 $i$ 面向左边，就考虑它能和它的前缀一起构成更大的前缀，此时 $f_i=max(i-1,t+1+...+p_{t+1}i-1+p_{i-1})$ 。
### P1452
旋转卡壳模板。
### UVA11626
题目中已经给出了凸包上的点，找到最左下的点然后对其按极角排序后就可以了。