P9108
较火的题。
设 \(f_{i,l,r}\) 表示第 \(i\) 行涂 \([l,r]\) 的方案数，\(sum_i=\sum\limits_l\sum\limits_r f_{i,l,r}\)。转移
\[f_{i,l,r}=sum_{i-1}-\sum\limits_{R<l}\sum\limits_{L} f_{i-1,L,R} - \sum\limits_{R}\sum\limits_{L>r} f_{i-1,L,R} \]再设 \(fl_{i,l}=\sum\limits_{R<l}\sum\limits_{L} f_{i-1,L,R}\)，\(fr_{i,r}=\sum\limits_{R}\sum\limits_{L>r} f_{i-1,L,R}\)。
有转移
\[fl_{i,l}=fl_{i,l-1}+\sum\limits_{L\le R=l-1} sum_{i-1}-fl_{i-1,L} - fr_{i-1,R} \]\[=fl_{i,l-1}+\sum\limits_{L\le R=l-1} sum_{i-1}-\sum\limits_{L\le R=l-1} fl_{i-1,L} - \sum\limits_{L\le R=l-1} fr_{i-1,R} \]随便优化，\(O(nm)\)。
P10681
考虑若 \(A_{i,j}=1\) 则连边 \((i,j+n)\)，那么最后形成若干个环或链的二分图。
预处理 \(f_{i,0/1}\) 表示一边放 \(i\) 个点，另一边放 \(i-(0/1)\) 个点组成连通块的方案数。有
\[f_{i,1} = f_{i-1,0}\times \frac{2i}{2i+1} \times i \times \frac{1}{2} \]\[f_{i,0} = 2\times f_{i,1} \times i \times \frac{2i+1}{2i} \]即
\[f_{i,1} = i! \times(i-1)! \times \frac{1}{2} \]\[f_{i,0} = i! \times(i-1)! \times (2i+1) \times \frac{1}{2} \]设 \(F_{i,z}\) 表示左边 \(i\) 个点右边 \(z\) 个点方案数，三个转移。
\[1\le j \le n,F_{i+j,z+j}+=F_{i,z}\times\binom{i+j-1}{j-1}\times\binom{z+j}{j}\times f_{j,0} \]\[1\le j \le n,F_{i+j,z+j-1}+=F_{i,z}\times\binom{i+j-1}{j-1}\times\binom{z+j-1}{j-1}\times f_{j,1} \]\[1\le j \le n,F_{i+j-1,z+j}+=F_{i,z}\times\binom{i+j-2}{j-2}\times\binom{z+j}{j}\times f_{j,1} \]比较相似，我们只考虑一个。
\[1\le j \le n,F_{i+j,z+j}+=F_{i,z}\times\frac{(i+j-1)!}{(j-1)!i!}\times\frac{(z+j)!}{j!z!}\times (j!) \times (j-1)! \times (2i+1) \times \frac{1}{2} \]\[+=F_{i,z}\times\frac{(i+j-1)!}{i!}\times\frac{(z+j)!}{z!} \times (2j+1) \times \frac{1}{2} \]发现和 \(j\) 有关的只有 \((2j+1)\)，是可以两遍前缀和优化的。
做到 \(O(n,m)\)，可能需要细致的边界处理。
P5400
从小到大填入每个极大的数。
设 \(f_{i}\) 表示钦定了 \(i\) 个极大的数的方案数。为了方便设 \(g_{i}=(n-i)(m-i)(l-i)\)。
有
\[f_{i}=f_{i-1}\times g(i-1)\times \binom{g(0)-g(i)-1}{g(i-1)-g(i)-1}\times (g(i-1)-g(i)-1)! \]再
\[f_{i}=f_{i}\times \binom{g(0)}{g(i)} \times g(i)! \]答案为
\[\frac{1}{g(0)!} \times \sum_{i\in[k,n]} (-1)^{i-k} \times f_{i}\times \binom{i}{k} \]计算 \(g!\) 较慢，于是优化式子。
\[f_{i} = \binom{g(0)}{g(i)} \times g(i)!\times \frac{f_{i-1}}{\binom{g(0)}{g(i-1)} \times g(i-1)!}\times g(i-1)\times \binom{g(0)-g(i)-1}{g(i-1)-g(i)-1}\times (g(i-1)-g(i)-1)! \]\[= \frac{g(0)!}{g(i)!(g(0)-g(i))!} \times g(i)!\times f_{i-1}\times \frac{g(i-1)!(g(0)-g(i-1))!}{g(0)!} \times \frac{1}{g(i-1)!}\times g(i-1)\times \frac{(g(0)-g(i)-1))!}{(g(i-1)-g(i)-1)!(g(0)-g(i-1))!}\times (g(i-1)-g(i)-1)! \]\[= \frac{1}{(g(0)-g(i))} \times f_{i-1}\times g(i-1) \]可以做到 \(O(n)\)。
AT_agc064_d
考虑什么串是合法的。不妨观察这个操作的过程。
你可以认为 B 是一个栈。每次找到一个 R 要把它放入到一个它后面的栈中，每次找到一个 B 也要把它放入后面的栈中。
发现如果把 B 放入后面的栈，相当于这个栈当前最顶层的 R 的数量已经确定了，这段 RRRRRB 一定对应结果串的一段 RRRRB。而再在这个放入栈后面加 R 就和在原栈中加 R 一样了。
所以条件转为每次遇到 B 都要有可以定下来的 RRRRB 栈。于是贪心的填，即把结果串除了最后一段 RRRRRB 的 R 的数量排序，要求遇到 B 时之前的 R 都能塞满一个新的结果串中的下一个 RRRRB。
设 \(f_{i,j,k,l}\) 表示放了 \(i\) 段 RRRRB，当前最长的一段长 \(j\)，一共长 \(k\)，最长的一段当前放了 \(l\) 段。
\[f_{i,j+1,k,0}+=f_{i,j,k,l} \]\[f_{i,j,k+j,l+1}+=f_{i,j,k,l}\times \frac{1}{k+1}\times (m-i) \]其中 \(m\) 表示 B 的个数 -1。
P11270
相交的情况直接哈希算掉。
不交可以根号分治，小于根号的串，我们可以先暴力 DP 把它推到根号长度。大于根号的暴力翻折容斥。
P10104
容斥。考虑枚举边集 \(S\) 并钦定 \((u,v)\in S,b_u=b_v\)，容斥系数 \((-1)^{|S|}\)。选择的边把图化成若干 \(b\) 相等连通块，每个连通块的限制变为 \(\min a_u\)，问题转化到 \(m=0\)。
\(m=0\) 的话可以考虑枚举从高位到低位从前到后第一个突破上界限制的数是哪一个，之后除了那个数以外任选的，用那个数调整异或结果即可。
称每种选边方案实际在限制 \(b\) 的点为关键点（每个奇数连通块有一个点），问题变为计算所有关键点集对应所有选边方案的容斥系数的和。
首先我们只关心连通块，设 \(h_S\) 表示点集 \(S\) 组成联通块的所有块内选边方案的容斥系数和。
继续考虑容斥计算 \(h\)，即：边任选方案 \(-\) 不连通方案。
结论：对于一个不为空的边集，其所有选法容斥系数为 \(0\)，空集为 \(1\)。证明考虑选择一条边观察，它选或不选时其他边选择方案一一对应且互为相反数。
于是我们考虑如何计算不连通答案。枚举 lowbit 所在连通块，即子集 \(T\)，此时我们已经计算了 \(h_T\)。再让剩下的部分任选，即使用上述结论。不难发现此时我们已经不重不漏计算所有情况。至此完成 \(h\) 的计算。
继续计算，设 \(f_S\) 表示关键点集为 \(S\) 时：所有连通块构成关键点集合为 \(S\) 的方案的容斥系数 \(\times\) 该方案偶数连通块任选的方案数。
转移考虑从小到大加入点。对于当前加入的点，小于它的点状压是否为关键点，大于它的点状压是否已经被选入连通块。有两种转移：
- 这个点是关键点，枚举以它作为最小值，点数为奇数的子集 \(T\) 转移 \(f_S=\sum f_T\times h_T\)。
- 这个点是不是关键点。
- 这个点之前已经被选入连通块，直接转移。
- 枚举以它作为最小值，点数为偶数的子集 \(T\) 转移 \(f_S=\sum f_T\times h_T\times (a+1)\)。
至此完成 \(f\) 的计算。
接下来枚举集合做 \(m=0\) 就好了。时间复杂度 \(O(n3^n)\)。
标签：,连通,le,frac,sum,times,binom From： https://www.cnblogs.com/lizhous/p/18679957