dp 专场。
CF1784E Infinite Game
题意：一个由 a 和 b 构成的字符串 \(s\)，长度为 \(n\)。两个人 Alice 和 Bob 在玩游戏，第 \(i\) 场中如果 \(s_{(i-1)\bmod n+1}\) 为 a 则 Alice 赢，否则 Bob 赢。两人遵循三局两胜原则：每当一个人胜场满两场时，称那个人赢了一轮，然后清空胜场记录开始新的一轮。设 \(w_i\) 为前 \(i\) 轮中 Alice 赢的轮数，当 \(i\to \infty\) 时若 \(\frac {a_i}i>\frac 12\) 则 Alice 是赢家，若 \(\frac {a_i}i =\frac 12\) 则两人平局，若 \(\frac {a_i}i<\frac 12\) 则 Bob 是赢家。现在 \(s\) 中挖了一些空，求所有可能的 \(s\) 中 Alice 赢、两人平局、Bob 赢的方案数分别是多少，模 \(998244353\)。 \(1\le n\le 200\)
确定 \(s\) 后，设有 \(n\) 个点 \(0,1,2,...,n\)，每个点表示当前轮结束后的位置，每个点向下一轮结束的点连有向边，不难发现这些点形成基环树，所以游戏一直无限进行下去时，一定是一直在环上绕。
Alice 赢的条件是环上 Alice 赢的轮数比 Bob 多，Bob 赢的条件是 Bob 赢的轮数比 Alice 多，平局的条件是一样多。
每次经过 \(0\) 时可能不是完整一轮，有 \(4\) 种状态（每人可能得 \(0/1\) 分）。考虑每个状态扫过一个 \(s\) 后的得到的状态，这些状态形成基环树，找到这个环即可。
现在需要知道谁赢，可以考虑记下环上的状态的 Alice 赢的轮数 - Bob 赢的轮数总和，计入状态，但问题是我们根本不知道哪些状态在环上。可以一开始先暴力枚举是哪些状态，然后 dp，最后计算时判断一下。
时间复杂度 \(O(n^2)\)，常数为 \(2^4\times 4^4\)，可过。
CF1842H Tenzing and Random Real Numbers
题意：有 \(n\) 个变量 \(x_{1...n}\)，在 \([0,1]\) 中随机取值。有 \(m\) 条限制，每条形如 \(x_i+x_j\ge 1\) 或者 \(x_i+x_j\le 1\)，求满足所有限制的概率。 \(1\le n\le 20\)
考虑 \(x_i+x_j\ge 1\) 转化为 \(\frac{x_i+x_j}2 \ge 0.5\)，这样相当于对一对变量的平均值限制为 \(\le 0.5\) 或 \(\ge 0.5\)。
考虑一开始有一条 \(0.5\) 的分隔线，我们按照与 \(0.5\) 差的绝对值从小到大加入变量，每次可以加在最上面或者最下面。
设 \(f[S]\) 表示加入的变量集合为 \(S\) 的合法概率。加入 \(x_i\) 在上面时，不难发现 \(x_i\) 与 \(S\) 中每一个变量的平均值都 \(\ge 0.5\)，判断一下即可。
然后每个变量在上面和在下面概率为 \(\frac 12\)，这些变量与 \(0.5\) 的差的绝对值的每一种可能的大小顺序概率为 \(\frac 1{n!}\)，乘上就行，\(O(n2^n)\)。
CF1874E Jellyfish and Hack
题意：一个排列 \(P\)，定义 \(w(P)\)： 我们把 \(P_{2...n}\) 以 \(P_1\) 为根据分成 \(<P_1\) 和 \(>P_2\) 且相对顺序不变的两个序列 \(L,R\)，然后 \(w(P)=|P|+w(L)+w(R)\)。
求出多少种长度为 \(n\) 且 \(w(P)\ge lim\) 的排列 \(P\)，模 \(10^9+7\)。 \(1\le n\le 200,\space 1\le lim\le 10^9\)
\(lim\) 过大没有用。容斥，改为求 \(w(P)<lim\)。
一个显然的 DP：设 \(f[i,j]\) 表示有多少个长度 \(i\) 的排列，且其 \(w\) 值为 \(j\)。
\[f[i,j]=\sum_{k=1}^i \sum_{l=0}^j f[k-1,l]\cdot f[i-k,j-l] \]卷积，设 \(F_i(x)=\sum\limits_j f[i,j]x^j\)。
那么
\[F_i(x)=\sum_{k=1}^i F_{k-1}(x)*F_{i-k}(x) \]接下来很妙的一步，考虑带入 \(x\)，拉插插出多项式 \(F_n(x)\)。
可知次数为 \(k=\frac{n(n+1)}2\)，带入 \(k+1\) 个不同的 \(x\)，为 \(x=1,2,...,k+1\)。
然后我们可以把卷积改成点乘，dp 是 \(O(n^4)\) 的。
然后拉插插出多项式，有 \(k+1\) 个点值。对于第 \(i\) 个，分母是容易算的，分子是 \(\frac{\prod_{j=1}^n x-x_j}{x-x_i}\)，上面部分预处理，下面直接暴力除。
时间复杂度 \(O(n^4)\)。
CF1804H Code Lock
题意：有一串密码，长度为 \(n\)，由前 \(k\) 个小写字母组成。有一个密码盘，输入密码时，每秒可以
-
输入一个小写字母
-
将箭头往左移一格
-
将箭头往右移一格
请设计这个密码盘（包括初始箭头指向），使得输入密码的秒数最小，求出这个数，以及有多少种设计方案。 \(1\le k\le 16,\space 1\le n\le 10^5\)
首先对于密码串，我们可以只保留 \(cnt_{i,j}\) 表示字母 \(i,j\) 出现相邻的次数。这样，密码盘的代价就是 \(\sum\limits_i\sum\limits _j \text{dist}(i,j)\times cnt_{i,j}\)，其中 \(\text{dist}(i,j)\) 是两个字母之间的最小移动次数。
关键问题是他是一个环，两个字母之间有两种移动方式，我们难以判断是顺时针移动还是逆时针移动。
设 \(p_i\) 表示字母 \(i\) 的位置，那么 \(i,j\) 之间的距离就是 \(\min(|p_i-p_j|,p_i+n-p_j,p_j+n-p_i)\)。
我们很容易想到需要把式子拆掉，然后两个字母分开贡献。但是仍然无法处理 \(\min\) 和绝对值的问题。
先考虑 \(k\) 为偶数的情况。仔细思考，两种移动方式的距离的分割线是 \(\frac k2\)，考虑折半的方法，我们可以在 \(k\) 中间砍一刀，然后左边和右边同时从前往后填字母。这样一来，不难发现，填写字母时，我们很容易知道他对于哪些段的贡献是怎样的。
如上图，\(S,T\) 是已经填写的字母集合，而 \(S',T'\) 未填写。当我们给 \(S'\) 最前面的位置（\(S\) 的后一个位置）填写一个字母 \(x\) 时，不难发现对于 \(S'\) 和 \(T\) 中字母，\(x\) 与他们的移动距离就是位置相减，其中 \(p_x\) 的贡献应是减去，系数为 \(\sum\limits_{y\in \{S' \cup T\}}cnt_{x,y}\)。同理，对于 \(S,T'\) 贡献应是加上。
为了知道 \(S',T'\) 中分别是哪些字母，我们需要提前枚举左边和右边的字母集合。
转移考虑枚举 \(S,T\) 后分别填写字母 \(x,y\)，然后计算各自的贡献。
这样的转移是 \(O(k^2)\) 的。由于 \(x,y\) 之间两条路径长度是一样的，考虑让 \(x\) 归为 \(S'\)，让 \(y\) 归为 \(T'\) 来计算。为了避免需要额外计算 \(x,y\) 之间的贡献，我们转移可以考虑拆开枚举：先枚举 \(y\) 来从前面转移过来，再枚举 \(x\) 把当前转移到后面，这样可以做到 \(O(k)\) 转移。
最后考虑 \(k\) 为奇数的情况。我们让左边部分后面多一个字母，容易处理，可以发现正确性也是对的。
时间卡一卡就能过了。
标签：总结,2024.2,le,frac,23,字母,0.5,Alice,sum From： https://www.cnblogs.com/Sktn0089/p/18030431