VEXOBEN
Vexoben
Oct 23, 2018
It takes 3 minutes to read this article.

比赛链接:AGC003

E. Sequential operations on Sequence

题意

给定长为 n 的一个序列, 第 i 个数为 i, 有 Q 次操作,每次给定一个 q[i], 表示将原序列无限延长(第 i 个数为 a[(i - 1) % n + 1])后, 截取前 q[i] 个数作为新序列。输出最终序列中每个数的出现次数。

n, q <= 100000, q[i] <= 1e18

题解

考虑两次操作 i, j, 如果 i < j 且 q[i] >= q[j], 那么操作 i 是没有意义的。从而我们可以得到一个升序的 q[i] 数组。

记 Solve(x) 为考虑最终序列的前 i 个数的答案数组, 我们要求的就是 Solve(q[m])

如果 x <= q[1], Solve(x) 可以直接求; 否则,找到一个最大的 i 满足 q[i] <= x, 就有 Solve(x) = x / q[i] * Solve(q[i]) + Solve(x % q[i])

x % q[i] < x / 2, 从而一段区间只会被这样切开 O(logx) 次

直到所有区间都被切得长度小于 q[1] 就可以打标记 O(n) 出解了。

代码

F. Fraction of Fractal

题意

给定一个 n * m 的方格图,有若干点被染成黑色。黑色的点保证联通。递归定义一组图形:

第 0 个图形是一个黑色的点。

若第 k 个图形的大小是 a * b, 第 k + 1 个图形的大小为 (a * n) * (b * m),对于每一个 a * b 的区域,若在方格图中为黑色,这块区域被画成第 k 个图形;否则这块区域全白。

求第 k 个图形黑色联通块的个数。

n, m <= 1000, k <= 1e18

题解

先定义一行连通当且仅当这一行最左边和最右边的格子都为黒色, 列连通同理。

如果存在一行联通且存在一列联通,可以发现整张图必然联通。从而答案为1。

如果不存在任意一行或一列联通,设黒色点个数为 c, 答案就是 c ^ (k - 1)

下面只考虑行连通的情况。

设方格中满足 (s[i][j] == ‘#’ && s[i][j + 1] == ‘#’) 的点数为 t, 可以猜到答案的递推式大概是 f(i) = c * f(i - 1) - g(i), 其中 f(1) = c, g(2) = t

首先 k > 1 的图案中如果两块区域位于网格图中的不同行,他们一定是不连通的。

递推 g(i + 1) 时, 考虑对 g(i) 有贡献拼接的时候, 如果第 i 行联通, 他们对应的这一行就会拼成一个联通块。

于是记连通行数为d, 有 g(i + 1) = g(i) * d。

直接上矩阵快速幂即可。

代码