假设 f_i 表示第 i 步恰好结束的概率，g_i 表示第 i 步还未结束的概率，h_{k, i} 表示第 i 步恰好结束并且以字符 k 结尾的概率。F(x), G(x), H(x) 分别是 \{f_i\}_{i=0}^\infty, \{g_i\}_{i=0}^\infty, \{h_i\}_{i=0}^\infty 的普通生成函数。

显然我们知道 F(1) = 1 ，要求 E = F'(1) 。

READ MORE

考虑倒推，我们把操作从后往前做以从结束状态倒推会起始状态。

显然把两个操作互换一下位置是不会影响操作结果的，我们可以先做所有对列的操作再做所有对行的操作。显然操作完所有的列后所有的行都是一样的，这时我们选了若干行进行取反，那么任选两行要么相同要么取反。

假设两两相同的分别有 a 个和 b 个，显然 a + b = n ，那么需要进行的行变换次数即 \min(a, b) 。列也同理。

将期望乘以总方案数，转化为算总和来做：

\begin{aligned} \binom nk ans &= \sum_{i=0}^k \binom m i \binom {n-m} {k-i} i^L \\ &= \sum_{i=0}^k \binom m i \binom {n-m} {k-i} \sum_{j=0}^L i^{\underline j} \left\{\begin{matrix}L \\ j\end{matrix}\right\} \\ &= \sum_{j=0}^L j! \left\{\begin{matrix}L \\ j\end{matrix}\right\} \sum_{i=0}^k \binom m i \binom {n-m} {k-i} \binom i j \\ &= \sum_{j=0}^L j! \left\{\begin{matrix}L \\ j\end{matrix}\right\} \binom m j \sum_{i=0}^k \binom {m-j} {i-j} \binom {n-m} {k-i} \\ &= \sum_{j=0}^L j! \left\{\begin{matrix}L \\ j\end{matrix}\right\} \binom m j \binom {n-j} {k-j} \\ \end{aligned}

READ MORE

定理：确定分块大小后，至多只有一种划分方案。

暴力 DP

DFS 自底向上计算，用 dp_u 表示到 u 为止，未被分块的节点个数。

每次需要重新枚举块的大小，时间复杂度为 O(n \cdot \sigma(n)) ，会获得 TLE 的好成绩。

巧妙的优化

有个显然的事情就是每个点只能属于一个联通块。

也就是说，前面我们统计的那个 dp_u ，在做到 u 这个点时，要么把自己和子树未被分配的点分到同一个块内，要么就留着自己等着之后配。也就是说，每个联通块的最高点（深度最浅点）一定满足其子树大小是当前块大小 size 的倍数。

可以证明如果以 size 为大小分块有一种划分方案，那么至少存在 n / size 个点的子树大小是 size 的倍数，反之亦然。

我们可以直接统计下每个点的子树大小放在桶里，然后枚举下分块大小去扫描。复杂度显然低于调和级数的复杂度，故上届为 O(n \log n) ，可以通过此题。

READ MORE

Solution1 - 二元生成函数

注意到比较难办的一个限制即每个数只能选一次，考虑 \forall \; i \in [1, n] 用一个二元生成函数 1 + y x^{a_i} 来表示。最后我们要求的即

\forall \; i , \; [y^k \cdot x^i] \prod_{\textrm{or}} 1 + y x^{a_i}

考虑对于给 F_i(x) = 1 + y x^{a_i} 做一次 or transformation 是什么

[x^k] \operatorname{FWT_{\textrm{or}}} (F_i(x)) = \begin{cases} 1 & (a_i \notin k) \\ 1 + y & (a_i \in k) \\ \end{cases}

把点值乘起来以后每一位就是 (1+y)^\theta ，显然我们只需要对于每一项求出 [x^k] (1+y)^\theta ，这其实就是 \binom \theta k 。

\theta 也是好求的，每一个 F_i(x) = 1 + y x^{a_i} 只会对答案贡献 1 ，且一定是在 a_i \in k 的位置。可以直接定义 G(x) = \sum_{i=0}^\infty x^i \sum_{j=1}^n [a_j = i] ，然后做一次高维前缀和。

求出 [y^k] \prod_{\textrm{or}} F_i(x) 后，事情就变得简单了起来，一遍 interverse or transformation 加上一遍 and transformation 直接带走。

Solution2 - 容斥

记 cnt_S = \sum_{i=1}^n [a_i \cup S = \emptyset] ，即与 S 没有交集的 a_i 个数。

考虑对于每一个询问 \operatorname{query}(S) 统计方案数。这相当于我们硬点了一个子集里的特性没有出现过，然后容斥。

显然

\operatorname{query}(S) = \sum_{T \in S} (-1)^{|T|} \binom {cnt_T} k

求出 cnt_S 后拿 (-1)^{|T|} \binom {cnt_T} {k} 来做一趟 or transformation 即可。

READ MORE

注意到其实只有这 4 种骨牌是实际有效的

把原来的题意转化为这样：我们可以往角落依次里堆骨牌，可以放当且仅当其每个格子的左边和右边都被填满或是边界，最后要堆成一个 n \times m 的矩形。

把轮廓线提出来，一段自下而上走的记为 0 ，自左向右走的记为 1 。显然一开始为 n 个 0 连着 m 个 1 ，最后要变成 m 个 1 连着 n 个 0 。

考虑到四种图形对应的变换如下

before transformation after transformation image
0001 1000
0011 1010
0101 1100
0111 1110

发现中间的 2 个二进制位都是固定的，变化的只有第四位的 1 跑到了第一位去。

于是我们又可以转换题意，每次可以选择一个 1 ，然后把它向前移 3 格。分模 3 意义下讨论，每一部分就变成了杨氏矩阵计数，可以用钩子公式解决。

定义杨表的钩子为在这个格正下方和正右方的格子个数。钩子公式对于由 n 个格子组成的杨表，给其标号的方案数为 n! 除以每个格子的钩子大小 + 1 。

READ MORE

一个非常套路的 O(n^3) DP 就是用 f_{i, j} 表示做了前 i 项，其中最后一项是前 i 个中第 j 大的方案数，转移即

f_{i, j} = \begin{cases} \displaystyle \sum_{k=1}^{i-1} f_{i-1, k} & (s_{i - 1} = \textrm{<}) \\ \displaystyle \sum_{k=i}^j f_{i-1, k} & (s_{i - 1} = \textrm{>}) \\ \end{cases}

这个 DP 很难再进行优化，需要考虑别的算法。

考虑我们可以固定所有的 \textrm{>} ，并用容斥的方式来解决 \textrm{<} 。这样就变成了只有 \textrm{>} 和 \neq 两种限制。可以看做排列被 \neq 分成了若干段，每段的排列的大小关系都是确定的，假设每段的大小分别为 a_{1 ... m} ，那么贡献即 \displaystyle \frac {n!} {\prod_{i=1}^m a_i} 。另外容斥系数只与硬点了几个 \textrm{>} 有关，可以和组合数放在一起 DP 。具体为

dp_n = \begin{cases} 1 & (n = 0) \\ \displaystyle \sum_{j=0}^{i-1} [j = 0 \textrm{ or } s_j = \textrm{<}] (-1)^{cnt_{i-1} - cnt_j} \frac {dp_{j}} {(i - j)!} & (n > 0) \\ \end{cases}

注意到的这个式子非常类似于分治 NTT 的形式，可以在 O\left(n \log^2 n\right) 的时间复杂度内解决。

READ MORE

官方题解是什么神仙东西看啊看不懂的。

Link

考虑我们维护一个分数类 (x, y) 表示 \frac x y 。假设 f(a_1, a_2, ..., a_n) = \frac x y 那么 f(a_0, a_1, a_2, ..., a_n) = \frac {a_0 x + y} {x} 。可以考虑用矩阵来维护转移。

定义将 (x, y) 到 (a x + y, x) 的转移为

\left[\begin{matrix} a & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} x \\ y \\ \end{matrix}\right] = \left[\begin{matrix} ax + y \\ x \end{matrix}\right]

反之，从 (ax + y, x) 到 (x, y) 的转移为

\left[\begin{matrix} 0 & 1 \\ 1 & -a \\ \end{matrix}\right] \left[\begin{matrix} ax + y \\ x \\ \end{matrix}\right] = \left[\begin{matrix} x \\ y \\ \end{matrix}\right]

那么

\begin{aligned} Ans_{l, r} &= \left[\begin{matrix} a_l & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a_{l + 1} & 1 \\ 1 & 0 \\ \end{matrix}\right] \cdots \left[\begin{matrix} a_r & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] \\ &= \left[\begin{matrix} 0 & 1 \\ 1 & -a_{l - 1} \\ \end{matrix}\right] \left[\begin{matrix} 0 & 1 \\ 1 & -a_{l - 2} \\ \end{matrix}\right] \cdots \left[\begin{matrix} 0 & 1 \\ 1 & -a_1 \\ \end{matrix}\right] \left[\begin{matrix} a_1 & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a_2 & 1 \\ 1 & 0 \\ \end{matrix}\right] \cdots \left[\begin{matrix} a_r & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] \end{aligned}

可以分别处理出前缀和

\begin{aligned} F_n &= \left[\begin{matrix} a_1 & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a_2 & 1 \\ 1 & 0 \\ \end{matrix}\right] \cdots \left[\begin{matrix} a_n & 1 \\ 1 & 0 \\ \end{matrix}\right] \\ G_n &= \left[\begin{matrix} 0 & 1 \\ 1 & -a_{n} \\ \end{matrix}\right] \left[\begin{matrix} 0 & 1 \\ 1 & -a_{n - 1} \\ \end{matrix}\right] \cdots \left[\begin{matrix} 0 & 1 \\ 1 & -a_1 \\ \end{matrix}\right] \end{aligned}

READ MORE

对于给定的 n+1 个点的坐标可以列出 n+1 个方程

\begin{cases} \left( a_{1, 1} - x_1 \right)^2 + \left( a_{1, 2} - x_2 \right)^2 + ... + \left( a_{1, n} - x_n \right)^2 = r^2 \\ \left( a_{2, 1} - x_1 \right)^2 + \left( a_{2, 2} - x_2 \right)^2 + ... + \left( a_{2, n} - x_n \right)^2 = r^2 \\ ... \\ \left( a_{n+1, 1} - x_1 \right)^2 + \left( a_{n+1, 2} - x_2 \right)^2 + ... + \left( a_{n+1, n} - x_n \right)^2 = r^2 \\ \end{cases}

考虑展开以后的 r^2 及 x_{1...n}^2 比较难以处理。让 [2, n + 1] 方程与第一个方程做差，得到 n 个线性方程

\begin{cases} a_{2, 1}^2 - a_{1, 1}^2 - 2 x_1 (a_{2, 1} - a_{1, 1}) + a_{2, 2}^2 - a_{1, 2}^2 - 2 x_1 (a_{2, 2} - a_{1, 2}) + ... + a_{2, n}^2 - a_{1, n}^2 - 2 x_1 (a_{2, n} - a_{1, n}) = 0 \\ a_{3, 1}^2 - a_{1, 1}^2 - 2 x_1 (a_{3, 1} - a_{1, 1}) + a_{3, 2}^2 - a_{1, 2}^2 - 2 x_1 (a_{3, 2} - a_{1, 2}) + ... + a_{3, n}^2 - a_{1, n}^2 - 2 x_1 (a_{3, n} - a_{1, n}) = 0 \\ ...\\ a_{n+1, 1}^2 - a_{1, 1}^2 - 2 x_1 (a_{n+1, 1} - a_{1, 1}) + a_{n+1, 2}^2 - a_{1, 2}^2 - 2 x_1 (a_{n+1, 2} - a_{1, 2}) + ... + a_{n+1, n}^2 - a_{1, n}^2 - 2 x_1 (a_{n+1, n} - a_{1, n}) = 0 \\ \end{cases}

高斯消元即可求得

小 \clubsuit 是 OI 国马拉松协会的会长。有一天，他打算举办全国青少年马拉松奥林匹克联赛（National Olympiad in Marathon in Provinces, NOMP），于是准备在 OI 国中修建一条赛道。

OI 国有 n (n \leq 5 \times 10^4) 个城市，一共有 n - 1 条道路将它们连通。也就是说，OI 国的结构是一棵树。

小 \clubsuit 会选择一个城市作为起点，再选择一个城市作为终点，这样赛道的长度就等于起点到终点路径上的边数。由于 OI 国的群众非常懒，所以赛道长为 0 也是允许的。

由于一些特殊原因，赛道的终点只能是一些特定的城市，而赛道的起点可以是任意一个城市。

现在小 \clubsuit 想知道：对于每个城市，如果选择它作为起点，那么赛道的长度有几种可能的取值？

READ MORE

给定 n (n \leq 100) 和长度为 n 的数组 \{a_i (a_i \leq 10^9)\} _{i=1}^n ，求满足 \forall i \in [1, n], c_i | b_i, b_i | a_i 并且 \prod_{i=1}^n c_i^2 \leq \prod_{i=1}^n b_i 的 \{b_i\}_{i=1}^n 和 \{c_i\}_{i=1}^n 的方案数。

假设 B = \prod_{i=1}^n b_i, C = \prod_{i=1}^n c_i^2 ，易证 C < B 的方案与 C > B 的方案是相同的，那么我们可以算出总共的方案加上等于的方案再除以二即可。

考虑等于的方案，这样即可把每个质因数分开考虑，相当于做个背包取第 0 项；

考虑总共的方案，对于质因数 x 在 a_i 中出现了 k 次，贡献为 \frac 1 2 (k + 1) (k + 2) 。

READ MORE

可以发现每条边出现的概率都是相同的，那么

ans = \frac{2 n^{n-3}}{n^{n-2}} \sum_{i=1}^{n} \sum_{j=i+1}^{n} (i+j)^k = \frac 2 n \sum_{i=1}^n \sum_{j=i+1}^n (i+j)^k

只需要求后面的值，假设 f(n, k) = \sum_{i=1}^n i^k

\begin{aligned} \sum_{i=1}^n \sum_{j=i+1}^n (i+j)^k &= \frac 1 2 \left( \sum_{i=1}^n \sum_{j=1}^n (i+j)^k - \sum_{i=1}^n (i+i)^k \right) \\ &= 2^{-1} \sum_{i=1}^n \sum_{j=1}^n (i+j)^k - 2^{k-1} \sum_{i=1}^n i^k \\ &= 2^{-1} \sum_{i=1}^n \sum_{j=1}^n (i+j)^k - 2^{k-1} f(n, k) \end{aligned}

只需要求中间的那个双重和式，后面的可以插值

\begin{aligned} \sum_{i=1}^n \sum_{j=1}^n (i+j)^k &= \sum_{d=1}^{2n} d^k \sum_{i=1}^n \sum_{j=1}^n [i+j=d] \\ &= \sum_{d=1}^n d^k (d-1) + \sum_{d=n}^{2n} d^k \left(2n-(d-1)\right) \\ &= \sum_{d=1}^{n-1} d^{k+1} + \sum_{d=n}^{2n} 2n d^k - \sum_{d=n-1}^{2n-1} d^{k+1} \\ &= f(n-1, k+1) + 2n \left( f(2n, k) - f(n-1, k) \right) - \left( f(2n-1, k+1) - f(n-2, k+1)\right)\\ \end{aligned}

可以处理出 f(n, k), f(2n, k), f(n, k+1), f(2n, k+1) 并快速转移。复杂度为拉格朗日插值的复杂度。

发现主要瓶颈在于 1. 求快速幂 2. 求逆元 。前者是一个完全积性函数，可以使用线性筛求得；后者我们可以先线性求逆元，然后分别做一趟前缀 / 后缀和即可。

令人自闭的考试 ...

语文那个《母鸡吃蛋》的阅读始终没有搞懂主旨是什么，或许是 oi 带来的副作用吧，刚主旨读了 15 分钟啥都没读出来 ...

数学好像错了好多傻逼错误，果然太久没做注意不到很多细节了么

英语全靠蒙，早知道带个骰子去了，可能会更方便点

物理很清真，吃老本还是吃得起的

化学由于题做的太少了导致常数过大，要不是加了个 clock() / (double)CLOCKS_PER_SECOND > 0.9 就输出随机数的特判估计就直接 TLE 了

生物竟然还考时事还好水知乎水到过

READ MORE

  1. 1
  2. 2
  3. 3
  4. 4
  5. ...
  6. 8