OI, 梦开始的地方。
uoj 192
题意：给出一个带边权树，求出树上所有路径积为完全平方数的条数。
我们考虑完全平方数的条件，则它的每个质因数出现偶数次
那么我们联想到异或，我们可以记录路径异或值，然后问题转化为多少条路径异或和为0
这里我们可以对每个质因数指定一个Hash值，然后异或起来就行
注意根据生日攻击的原理，权值范围要远大于$n^2$，那么我们$\text{rand}$一个long long 范围的数
具体有一个近似的公式
$$
\sqrt{\frac \pi 2 n}
$$
那么我们预处理$\sqrt{w}$以内的质数，每次枚举质数分解质因数即可，注意数本身是个大质数的情况
然后就可以求多少条路径异或和为0了，这是经典问题，即拆分路径以后做
1、异或–两两消除
2、Hash–暴力不行时想想
BZOJ 5369
题意：给定$n$长序列$a_i$，求任意该序列排列最大前缀和的和。
我们考虑状压。
最大前缀和性质即我们可以找到一个位置 $p$ ，使得在这之前的 $ i $ 都满足 $\text{sum} (i) \leq \text{sum} (p)$，在这之后的 $i$ 都满足 $\text{sum} (i) \geq \text{sum} (p)$
考虑集合 $S$ 的数组成最大前缀和的方案数，那么计算就是一个求贡献
那么设 $g(S)$ 为 $S$ 集合组成序列最大前缀和是 $\text{sum}(S)$ 的方案数
$f(S)$ 为 $S$ 集合组成序列的任意最大前缀和都小于 $0$ 的方案数。
则$g(S + i)=\sum g(S), f(S)=\sum f(S-i)$
那么最后答案就是$\sum f(S)g(C_US)\text{sum}(S)$
Codeforces 1097D
题意：给定 $n,k$，一共会进行 $k$ 次操作，每次操作会把 $n$ 等概率的变成 $n$ 的某个约数
求操作 $k$ 次后 $n$ 的期望是多少
考虑到质因子的概率是独立的，那么我们只需要解出$n=p^k$的期望即可。
考虑设$dp(i, j)$为$p^i$操作$j$次的期望，那么
$$
dp(i,j)=\sum_{k=0}^i\frac{1}{i+1} dp(k,j-1)
$$
然后分解质因数乘起来即可。
Codeforces 1191F
题意：给定平面上$n$个点，每次可以用$x\in [l,r],y \in [a,+\infty)$作为限制条件来得到一个点集。求能得到多少种不同的点集。
很显然要扫描线。
发现$y \in [a,+\infty)$，那么从上往下即可。
考虑从上往下，从左到右加点，然后统计新加的点的答案。
可能一开始会想到一个找这个点的左上角的所有点乘上右上角所有点，但是有重复。
考虑缩小右上角点的范围，那么我们只需要统计矩形$([x_i,x_{i+1}], y_i), y_i=y_{i+1}$的点的个数作为右上角点的范围即可。
注意这里每列的赋值只能最多一，那么我们能想到用线段树维护，但是这里由于只是单点修改，我们完全可以开一个树状数组和一个vis数组来判断某个地方加了1没有即可完成。
坐标数据大离散化即可。
poj 2311
题意：有一张$n \times m$的格子，两个玩家轮流每次可以剪下一行/一列，第一个剪下$1\times 1$的玩家获胜。两个玩家都采用最优决策，求先手是否必胜。
考虑将一张格子定义为一个有向图游戏，最终游戏的$\text{SG}$值即为所有有向图游戏的异或和
考虑这个$1\times 1$获胜不符合我们有向图游戏的定义，我们做一些转化。
考虑到我们剪下$1 \times x, x \times 1$会使得当前的玩家必败。那么我们可以将局面
$(2,3), (3,2), (2,2)$设为必败局面，然后
$$
\text{SG}(x,y)=\text{mex}(\text{SG}(x - i,y) ⊕ \text{SG}(i,y) \cup \text{SG}(x ,y- i) ⊕ \text{SG}(x,i))
$$
注意多组询问完全可以将之前的$\text{SG}$函数值保留。
BZOJ 1563
题意：有一个长度为 $n$ 的序列 $A$ 和常数 $L,P$ ，你需要将它分成若干段，每一段的代价为 $|\sum A_i−L|^P$ ，求最小代价的划分方案。
易得暴力DP
$$
dp(i) = \min_{j = 0} ^ {i - 1} (|\text{sum}(i) - \text{sum}(j) - L|^P + dp(j))
$$
发现这个$dp$满足决策单调性，即如果我们把每个位置$i$由哪个位置转移而来记为$g(i)$，则$g(i)$为单调不减的
这个可以数学证明也可以打表验证
然后我们就可以通过一个队列来完成优化，即我们队列存的是三元组$(l,r,j)$表示$[l,r]$区间的$dp$值的最优决策为$j$
那么我们每次在队头删掉$r$小于当前枚举的$i$的三元组
然后就就可以取队头元素来计数$dp(i)$
然后我们在队尾处理，如果当前有决策$i$, 队尾三元组$(l_t,r_t,j_t)$，则如果$\text{val}(i, l_t) \leq \text{val}(l_j, l_t)$，那么删掉队尾三元组
然后我们尝试插入当前的$i$，我们在当前$[l_t,r_t]$中二分一个位置$pos$，使得$j_t$是$[l_t,pos-1]$的最优决策，$i$是$[pos, r_t]$的最优决策
最后注意开 long double 来判断是否大于$10^{18}$
知识点
打表验证决策单调性
局面：游戏过程中面临的状态
先手：整局游戏第一个行动的
后手：整局游戏第二个行动的
必败局面：在某一局面下无论采取什么行动都会输
必胜局面：在某一局面存在某行动能够使对手面临必败局面
1、两名玩家交替行动
2、可执行的合法行动与轮到谁无关
3、不能行动判负
设$S$表示一个非负整数集合，则
$$
\text{Mex}(S)=\min_{x \in \mathbb{N}, x \notin S} (x)
$$
$$
\text{SG}(x)=\operatorname{Mex}\limits_{i=1}^k(\text{SG}(y_i))
$$
一个有向图
$$
\text{SG}(G)=\text{SG}(s)
$$
$$
\text{SG}(G)=\text{SG}(G_1) \text{xor} \text{SG}(G_2) \text{xor} … \text{xor} \text{SG}(G_m)
$$
局面必胜：$SG > 0$
局面必败：$SG=0$
BZOJ 4870
题意：给定$n,p,k,r$，求
$$
\sum_{i=0}^{∞} C_{nk}^{ik+r}
$$
注意到$ik+r \mod k=r$，则我们考虑组合数的组合意义
从$nk$个物品中选 $\mod k=r$ 的个数的物品的方案数
那么设$dp(i,j)$为前 $i$ 个物品选择 $\mod k$ 为 $j$ 的方案数.
转移即
$$
dp(i,j)=dp(i-1,j)+dp(i-1,(j-1+k)\mod k)
$$
矩阵快速幂优化即可。
BZOJ 4818
题意：求$n$长序列值域$[1,m]$，求序列和是$p$倍数并且序列至少有一个质数的序列个数。
转化题意，则
$\text{ans}=$满足和为$p$的倍数的方案数$−$满足和为$p$的倍数且不含质数的方案数
那么我们先考虑满足和为$p$的倍数的方案数怎么算，显然我们可以设$dp(i,j)$为前$i$个和模$p=j$的方案，然后可以这样转移
$$
dp(i,j)=\sum_{k=1}^m dp(i-1,(j-k) \mod p)
$$
考虑优化，我们想办法让它与$m$复杂度无关，我们发现$i$位填$u$和填$u+pv$效果是一样的，所以我们直接记$cnt_i$表示$1∼m$中$\mod p$为$i$的个数，那么转移为
$$
dp(i,j)=\sum_{k=0}^{p-1} dp(i-1,(j-k) \mod p) \times cnt_k
$$
那么现在复杂度为$O(np^2)$
发现$n$很大，考虑矩阵优化到$O(\log n \times p^3)$
矩阵构造就循环一下构造就行，然后就是常规的优化方法
注意vis数组要开成bool