数数题随机做
[ABC241Ex] Card Deck Score [2881*]
标签：生成函数，tricky problem。
直接写出答案为 \([x^m]\prod\limits_{i = 1}^{n}\dfrac{1 - (a_ix)^{b_i+1}}{1 - a_ix}\)。
由于 \(n \leq 16\)，分子可以直接 \(2^n\) 枚举，那么就变成快速求 \([x^r]\prod\limits_{i = 1}^{n}\dfrac{1}{1 - a_ix}\)。
根据有理因式部分分解，可知 \(\prod\limits_{i = 1}^{n}\dfrac{1}{1 - a_ix} = \sum\limits_{i = 1}^{n}\dfrac{c_i}{1 - a_ix}\)。
即 \(1 = \sum\limits_{i}c_i\prod\limits_{j \neq i}(1 - a_jx)\) 。对每个 \(i\) 代入 \(x = a_i^{-1}\) 就可以解出 \(c_i\)。
进而可以 \(O(n\log n)\) 计算 \([x^n]\prod\limits_{i}\dfrac{1}{1 - a_ix}\)。
ABC238Ex Removing People [*3247]
标签：区间 dp，正难则反。
时光倒流，设 \(f_{l,r}, g_{l,r}\) 分别表示 \([l,r]\) 都复活，且 \(l, r\) 是最先复活的的概率和期望。
转移枚举 \(l < k < r\)，复活 \(k\) 的方案为 \(cnt = [s_l = R]+[s_r = L]\)，权值为 \(coe = [s_l = R](k - l)+[s_r = L](r - k)\)。
于是有 \(f_{l, r} \leftarrow f_{l,r}+cnt \times f_{l, k} \times f_{k,r}\)，\(g_{l,r} \leftarrow g_{l,r}+coe \times f_{l,k}\times f_{k,r}+f_{l,k}\times cnt\times g_{k,r}+f_{k,r}\times cnt\times g_{l, k}\)
初始值 \(f_{i, i+1} = 1\)，答案是 \((\sum\limits_{i}g_{i,i}) /n!\)
ARC134F Flipping Coins [*3530]
标签：另类容斥，多项式。
这种容斥方法之间做到过，可一结合起来就不会了。。。
连边 \(i \to p_i\) 形成若干个环，只用对环计算答案后 exp 即可。 考虑算环
通过手玩一个环可以发现，一个环最后翻上去的个数等于极长上升子段为长度奇数的个数。 严谨证明不会。
然后就考虑把每个极长连续段的 OGF 写出来，为 \(F(x) = \sum\limits_{i \geq 1}x^iW^{[i \bmod 2 = 1]}\)。
但极长这个限制很棘手，只能通过容斥凑系数的方式解决：即设 \(G(x)\) 满足 \(\dfrac{1}{1 - G(x)} = F(x) \Rightarrow G(x) = 1 - \dfrac{1}{F(x)+1}\)。
然后用 \(\hat{G}\) 来拼接：\(\exp(\sum\limits_{i \geq 1}\dfrac{\hat{G}}{i!}(i - 1)!) = \exp{\ln(\dfrac{1}{1 - \hat{G}(x)})}\) ，所以答案为 \(\dfrac{1}{1 - \hat{G}(x)}\)。
只需要两遍多项式求逆。
ABC236Ex Distinct Multiples [*2898]
标签：另类容斥，子集 dp。
简单的思路是容斥，钦定有 \(k\) 个数相等然后做 dp。不过写出来就会发现这里的容斥系数并不是简单的奇加偶减。
实际上我们应该用边来容斥，设边集 \(E\)，其中有边相连的点权值一定相等，无边相连的没有要求，设其对应的方案数为 \(C(E)\)，则答案为 \(\sum\limits_{E}(-1)^{|E|}C(E)\)。
因为整个图的容斥系数等于每个连通块的容斥系数，于是可以只考虑每个连通块。
又因为对于一个连通块而言，要求他们相同的方案是一样的，于是变成了如下问题：
将 \(n\) 个点通过边连成一个连通块，一个连边方案的权值为 \((-1)^{|E|}\)，求所有连边方案的权值。
直接给出结论：设 \(h_n\) 表示 \(n\) 的答案，则 \(h_n = (-1)^{n - 1}(n- 1)!\)。
证明：所有方案的总和显然为 0，考虑一个不合法方案，1 的连通块大小，若不为 \(n - 1\) 则剩下的连边会奇偶相消，于是枚举孤立点，有：\(h_n = -(n - 1)h_{n - 1} = (-1)^{n - 1}(n - 1)!\)。
然后直接根据这个系数来 dp 即可。时间复杂度 \(O(3^n)\)。
AGC032F One Third [*3975]
标签：积分，转化。
麻了，这种阴间题永远不会。
对于每刀而言，把切的第一刀标记为红色，旋转 \(\dfrac{2\pi}{3}\) 后标记成蓝色，再旋转 \(\dfrac{2\pi}{3}\) 后标记成绿色，那么答案就是异色线段之间的最短距离。
引理 1：在 \([0, 1)\) 之间随机选择 \(n - 1\) 个点分割成的 \(n\) 条线段当中，第 \(k\) 小的期望为 \(\dfrac{1}n(\sum\limits_{i = 1}^{k}\dfrac{1}{n - i+1})\)。
证明：当 \(k = 1\) 时，即是最短线段的期望，计算所有线段 \(\geq x\) 的概率，积分可得：
\[E(mn) = \int_{0}^{\frac 1 n}(1 - nx)^{n - 1} = \dfrac{1}{n^2} \]当 \(k > 1\) 时，采用归纳法证明即可。
只考虑 \([0, \dfrac{2\pi}3)\) 这一部分的贡献，因为剩下两部分是对称的。
由于异色线段最小值只有可能在相邻两个点之间取得，枚举异色线段为第 \(k\) 小，这要求前 \(k - 1\) 小的线段都是同色的，概率就是 \(\dfrac{3^{n - i+1} - 3^{n -i}[i \neq n]}{3^{n}} = 3^{-i +1} - 3^{-i}[i \neq n]\)，因为 \(n\) 个线段不可能全部同色，于是答案就是:
\(ans = \dfrac{1}{3n}\sum\limits_{i = 1}^{n} (3^{-i+1} - 3^{-i})\sum\limits_{j = 1}^{i}\dfrac{1}{n - j+1} = \dfrac{1}{n}\sum\limits_{j = 1}^{n}\dfrac{1}{n - j+1}3^{-j}\)
ABC225H Social Distance 2 [*3061]
标签：生成函数，组合数学。
还算简单。
只用考虑三种情况的生成函数：
- 两端都有人时：为 \([x^{n+1}]\dfrac{x^m}{(1 - x)^{2m}} = \dbinom{n+m}{2m - 1}\)
- 一端有人时：\([x^n]\dfrac{x^m}{(1-x)^{2m+1}} = \dbinom{n+m}{2m}\)
- 两端都没人：\([x^n]\dfrac{x}{1 - x} \times \dfrac{x^{m - 1}}{(1 - x)^{2m - 2}}\times \dfrac{1}{1 - x} = \dbinom{n+m - 1}{2m - 1}\)
把每一段的分治卷起来，over。
ARC132F]Takahashi The Strongest [*3076]
标签：FWT，构造。
由于 \(P\) 能战胜 \(R\)，\(R\) 能战胜 \(S\)，\(S\) 能战胜 \(P\)，把 \(R\) 看作 1， \(S\) 看作 2，\(P\) 看作 3，将一个操作序列看作 4 进制下长度为 \(k\)，的数，然后考虑如下的运算：
\(x \otimes y = \begin{cases} 0 \ \ \ x \neq y \\ x \ \ \ x = y\end{cases}\)
那么一个操作序列 \(S\) 的答案就是 \(A,B\) 做卷积后，至少有一位与 \(S\) 相同的个数，代表着存在一轮，\(A,B\) 出的都相同，而 \(C\) 恰好出了能获胜的哪一个。
根据 FWT 相关理论，可以构造出真值表为：
\(\begin{bmatrix} 1 \ \ 1 \ \ 1 \ \ 1 \\ 0 \ \ 1 \ \ 0 \ \ 0 \\ 0 \ \ 0 \ \ 1 \ \ 0\\ 0 \ \ 0 \ \ 0 \ \ 1\end{bmatrix}\)，（其实就是把 0 看作 1, 2, 3 的子集，其中 1 2 3互不包含时的高位后缀和），显然其逆矩阵为：\(\begin{bmatrix} 1 ,-1,-1 , -1 \\ 0 \ \ \ \ 1 \ \ \ \ 0 \ \ \ \ 0 \\ 0 \ \ \ \ 0 \ \ \ \ 1 \ \ \ \ 0\\ 0 \ \ \ \ 0 \ \ \ \ 0 \ \ \ \ 1\end{bmatrix}\)
然后考虑求至少有一位与 \(S\) 相同的的方案，容易转化为计算每一位都与 \(S\) 不同的方案，显然也可以 FWT 计算。
[ARC132E] Paw [*3144]
标签：结论，期望。
首先应该观察最终形态，最终状态一定形如 [<<<****>>>] 的形式，其中 * 是相邻两个 . 之间的 <>。
于是考虑枚举相邻的两个 ..，在中间的可以前缀和算出来，对于左右两边的方案，是对称的，不妨算左边。
设含有 \(n\) 个 .，且最后的状态为 <<< 的概率为 \(f_n\)。
考虑所有 \(2n\) 中情况，只有把最靠右的一个往右移是非法的，其他的均能转化成 \(n - 1\) 的情况，故 \(f_n = \dfrac{2n - 1}{2n}f_{n - 1}\)。
P6633 [ZJOI2020] 抽卡
标签：多元拉格朗日反演，牛顿迭代。
先转为计算抽了 \(n\) 次都没有抽到连续 \(k\) 张卡的概率，再转化为计算从抽到 \(x\) 张到抽到 \(x+1\) 张不同的期望轮数。
设 \(f_n\) 表示抽出 \(n\) 张不同的卡且没有连续 \(k\) 张的方案，答案就是 \(\sum\limits_{i}\dfrac{f_i}{\binom n i}\times \dfrac{n}{n - i}\)。
显然每个连续段是独立的，只用对单个连续段算出后分治乘起来即可。
对于一个长度为 \(n\) 的连续段而言，不超过 \(k\) 的生成函数为 \(F(x) = \dfrac{x - x^{k+1}}{1 - x}\) ，那么 \(f_{n+1 - i} = [x^{n+1}y^i] \dfrac{1}{1 - yF(x)}\)。
设 \(H(x) = \dfrac{1}{1 - yx}\)，\(G(x) = F^{(-1)}(x)\)
回忆扩展拉格朗日反演：\([x^n]H(F(x)) = [x^n]H(x)(\dfrac{x}{G(x)})^{n+1}G'(x)\)
二元生成函数也可以进行拉格朗日反演：\([x^{n+1}]H(F(x)) = [x^{n+1}]H(x)(\dfrac{x}{G(x)})^{n+2}G'(x) = [x^{n+1}]\dfrac{1}{1 - yx}(\dfrac{x}{G(x)})^{n+2}G(x)'\)
于是只用把后面两个算出来后，\(x\) 的第 \(t\) 项就对应 \(y\) 的 \(n+1 - t\) 项。
至于怎么求出 \(G(x)\)，显然可以牛顿迭代。柿子：
\(F(x) = F_0(x) -\dfrac{(1 - x)F - F^{k+1} - x}{1 - x - (k+1)F^k}\)。
时间复杂度 \(O(n \log^2 n)\)，常数应该非常大。
标签：数数,limits,dfrac,sum,容斥,times,标签 From： https://www.cnblogs.com/henrici3106/p/16995216.html