POI 选做-526互联

E(Easy) / H(Hard) / I(Insane)

POI 2021

Druk

有一个 \(n \times m\) 的字符矩形。定义一个字符串 \(S\) 是好的，当且仅当矩阵能被划分为若干个横向或纵向的 \(S\)。

求 \(\{ L \mid S \text{ is good} \And |S| = L\}\)。

\(1 \leq n, m \leq 1000\)。

首先，\(L\) 的取值范围十分有限：其要么是 \(n\) 的因数，要么是 \(m\) 的因数。

证明：把矩阵按 \((i + j) \bmod L\) 染色，那么每个 \(S\) 都恰好覆盖每种颜色各一次。从而我们要求各颜色出现次数相同。不难发现这等价于 \(L \mid n\) 或 \(L \mid m\)。

因此我们枚举 \(L\)。当 \(L\) 固定时，\(S\) 也只有两种可能性，即 \((1, 1)\) 向下的 \(L\) 个字符或 \((1, 1)\) 向右的 \(L\) 个字符。考虑如何 check \(S\) 是否是好的。

一个重要的引理：若以 \((i, j)\) 为起点可以横向放置一个 \(S\)，但最终方案选择了纵向放置一个 \(S\)，那么 \(S_1 = S_2 = \cdots = S_L\)。

证明：我们考虑 \((i, j) \sim (i, j + L - 1)\) 这 \(L\) 个位置的放置。若它们都纵向放置，那么显然 \(S\) 所有位置都 \(= S_1\)。

否则，若存在一个 \(t\) 使得 \((i, j) \sim (i, j + t - 1)\) 纵向放置，而 \((i, j + t)\) 横向放置，那么 \(L - t\) 为 \(S\) 的一个 border。由 border 理论我们知 \(t\) 是 \(S\) 的周期，而前 \(t\) 个位置都 \(= S_1\)，这也能说明 \(S\) 全同。

因此，我们特判字符矩阵全同的情况。若字符矩阵不全同，能横着放就横着放一定最优，容易 \(\mathcal O(nm)\) check。

时间复杂度 \(\mathcal O(nm\cdot (d(n) + d(m)))\)。

POI 2020

Kolekcjoner Bajtemonów 2

有 \(n\) 个数对 \((a_i, b_i)\)。你要在每个数对里选出一个数，使所有选出的数 \(\gcd\) 最大。

\(1 \leq n \leq 10^6, 1\leq a_i, b_i \lt 2^{63}\)。

枚举 \((a_1, b_1)\) 选的是哪个，假设选出了 \(k\)，那么答案集合包含于 \(k\) 的因数集合，而 \(d(k) \leq 103680\)。

于是我们可以枚举一个 \(g \mid k\)，并判断是否能够在每一对里选出 \(g\) 的倍数，即 \(\sum[g \mid a_i \text{ or } g \mid b_i] = n\)。

我们考虑如何对每个 \(g\) 统计上式，实际上 \(\sum [g \mid a_i \text{ or } g \mid b_i] = \sum([g \mid a_i] + [g \mid b_i] - [g \mid \gcd(a_i, b_i)])\)。

因此我们用一个数组 \(c\) 统计答案。只需对 \(c_{\gcd(a_i, k)}\) 和 \(c_{\gcd(b_i, k)}\) 加一、对 \(c_{\gcd(a_i, b_i, k)}\) 减一，然后对 \(c\) 做一遍 Dirichlet 后缀和即可。此时 \(c_g = \sum[g \mid a_i \text{ or } g \mid b_i]\)。

时间复杂度 \(\mathcal O((n + d(V)) \log V)\)，需要用 Pollard-rho 分解 \(k\)。

POI 2019

Przedszkole

有一个 \(n\) 个点 \(m\) 条边的无向简单图。\(q\) 次询问，每次给定 \(k\)，求这张图的 \(k\) 染色方案数。

数据范围三合一。

Sub 1：\(n \leq 15\)。

Sub 2：\(m \leq 24\)。

Sub 3：图里只有环。

对于所有的数据，\(1 \leq n \leq 10^5, 0 \leq m \leq 10^5, 1 \leq q \leq 1000, 1\leq k \leq 10^9\)。

Sub 1

设 \(f(i, S)\) 表示 \(S\) 的点导出子图的 \(i\) 染色方案数（\(i \leq n\)）。询问时答案即 \(\sum_{i=1}^n \binom kif(i, V)\)。

转移：\(f(i, S) = \sum_{T \subset S \And T \text{ is independent}} f(i - 1, S \backslash T)\)。

时间复杂度 \(\mathcal O(n3^n + qn)\)。

Sub 2

考虑容斥，钦定一个边集里的边两端颜色相同，其余随意。

\[ans = \sum_{S \subset E} (-1)^{|S|} k^{\text{仅保留 } S \text{ 里的边时的连通块数}} \]

可以对于每个 \(1 \leq i \leq n\)，预处理出上式 \(k^i\) 前的系数 \(c_i\)，每次询问时计算 \(\sum_{i=1}^n c_i k^i\)。

时间复杂度 \(\mathcal O(2^m \log n + qn)\)。

Sub 3

一个环的答案是容易计算的：设长度为 \(i\) 的环的答案为 \(f(i)\)，则有 \(f(n) = k(k - 1)^{n - 1} - f(n - 1)\)。

即

\[\begin{aligned} f(n) &= \sum_{i=0}^{n - 3} (-1)^i k(k-1)^{n - i - 1} + (-1)^n k(k - 1)\\ &= k(k-1)^2 \sum_{i=0}^{n - 3} (-1)^i(k-1)^{n - 3 - i} + (-1)^n k(k - 1)\\ &= k(k - 1)^2(-1)^{n - 3}\sum_{i=0}^{n - 3} (1-k)^i+(-1)^nk(k - 1)\\ &= k(k-1)^2(-1)^{n - 3}\dfrac{1 - (1-k)^{n - 2}}k+(-1)^nk(k - 1)\\ &=(-1)^{n}((1 - k)^{n} - (1-k)^2 + k(k - 1))\\ &= (k - 1)^n + (-1)^n(k - 1) \end{aligned} \]

由于本质不同的环只有 \(\mathcal O(\sqrt n)\) 种，我们每次对于同一环长的环套用上述公式即可。

时间复杂度 \(\mathcal O(q \sqrt n \log n)\)。