7/17
Valid Bitonic Permutations
题意：
构建一个以 \(k (2 \le k \le n-1)\) 为峰值的单峰序列 \(a\) ，使得在 \(i,j\) 位置上的数为 \(x,y\)，问在模 \(10^{9}+7\)下有多少种序列。多测
\(t,n \le 100\)
设 \(x,y\) 为两个特定值的位置， \(nx,ny\) 为两个特定的值。
枚举峰值可能在哪里，设此时在 \(i\)，同时因分讨 \(nx,ny\) 哪个较大。
$ nx > ny : $
$ i < x : \binom{x-i-1}{n-nx-1} \times \binom{y-x-1}{nx-ny-1} \times \binom{n-y}{ny-1}$
$ x < i < y : \binom{i-x-1}{n-nx-1} \times \binom{y-i-1-((n-nx-1)-(i-x-1))}{nx-ny-1} \times \binom{n-y}{ny-1}$
$ nx < ny : $
$ y < i : \binom{i-y-1}{n-ny-1} \times \binom{y-x-1}{ny-nx-1} \times \binom{x-1}{nx-1} $
$ x < i < y : \binom{y-i-1}{n-ny-1} \times \binom{i-x-1-((n-ny-1)-(y-i-1))}{ny-nx-1} \times \binom{x-1}{nx-1} $
然后特判一下两个值为 \(n\) 的情况以及两个值为 \(n\) 但是在首尾的情况即可。
Two Chess Pieces
题意：
给定一个 \(n\) 个点的树，一开始在根节点\(1\) 有一个黑棋和白棋，每次可以选择一个点移动一条边，给定黑点和白点分别一定要经过（没有顺序）的点，给定一个限制 \(k\) ，使得两个在任何时刻距离不能超过 \(k\)，最后都要返回根节点，问最小操作数是多少。
\(n,k \le 2 \times 10^{5}\)
可以想到，每个棋最多经过一条边\(2\)次，那么我们把边下压到点上，判断对于黑棋和白棋，每个节点是佛需要经过。
要经过一个点，当且仅当两种情况：
1.在当前子树内，有相同颜色需要到达的点。
2.在当前子树内，两种颜色最深需要到达的节点深度差 $ > k-1$
那么用 $ dfs $ 查一下就行，没有一个需要经过的点 \(ans+=2\)。
Chain Chips
题意：
给定 \(n\) 个点有边权的链，每个点上初始有一辆车，可以将车移动，有 \(m\)次询问，每次修改一条边的边权并求最小的代价使得最后每辆车都不在初始点上且每个点上恰好有一辆车。
\(n,q \le 2 \times 10^{5}\)
\(a_{i} \le 10^{9}\)
对于一个区间，如果相互交换，对于每条边，可以做到被经过的次数少于等于两次，而不可能为一次（两边数量要相同），那么只有可能被经过两次或零次，那么我们可以将有没有被经过化为被不被选中，那么只要满足相邻两条边至少要选中一条（不然这个点就动不了了）即可，就变成了最小覆盖问题。
设$ f_{i0}\(为到当前边且当前边不选的最小值，\)f_{i1}$为到当前边且当前边选的最小值。可得转移方程:
\(f_{i,0}=f_{i-1,1}\)
\(f_{i,1}=min(f_{i-1,0},f_{i-1,1})+a[i]\)
而又有修改，想到动态 \(DP\) ，将转移方程变成\(\begin{bmatrix} \infty & a[i] \\ 0 & a[i] \end{bmatrix}\)在线段树上维护即可。
Roulette
题意：
小 \(A\) 在进行赌博，一开始他有 \(n\)块钱,第 \(i\) 局小 \(A\) 先投注 \(a_{i}\) 块钱，如果他赢了就拿回 \(2\times a_{i}\) 块钱，输了就拿不回来，每次赢的几率为 $\frac{1}{2} $。
\(a_{1}=1\) ，如果第 \(i-1\) 局赢了，那么 \(a_{i}=1\) ，如果第 \(i-1\) 局输了，那么 \(a_{i}=2 \times a_{i-1}\)。当小A赚了 \(m\)块钱或他付不起\(a_{i}\)，那么小\(A\)收手。问在模 \(998244353\) 下他赚了 \(m\)块钱的概率。
\(n,m \le 10^{9}\)
可以想到，他下注的钱数为$ 2^{0} + 2^{1} + 2^{2} + 2^{3} + 2^{4} ... $，如果在他下注\(2^{i}\)块钱时，他会得到\(2^{i+1}\)块钱，那么与初始相比，他一共赚了 \(1\)块钱，也就是说，我们可以将这么输输输输输输输赢的一个步骤为一轮，一轮有 \(i\) 个回合，也就是说一共有 \(m\) 轮，我们要求经过 \(m\) 轮后他还没死的概率。
对于一轮，我们可以正难则反，求他这一轮的 \(i\) 个回合全部输的概率，用\(1\) 减去这个数就是这一轮赢得一块钱的概率，那么我们只要将所有轮赢得一块钱而不中道崩殂的概率乘起来就行。
然而 \(m \le 10^{9}\)，但是我们发现，当一轮的回合数相同时，赢的概率都为 \(1 - \frac{1}{2^{i}}\)，那么我们只要对 \((2^{i}-1,2^{i+1}-1]\) 分块求值就行，时间为 \(log(m)\)。注意收尾的区间。
标签：复健,le,17dp,times,nx,ny,块钱,binom From： https://www.cnblogs.com/shihoghmean/p/17565434.html