页面载入中...

当前位置: 感悟生活网 > 吕布简介正文

Panasonic Programming Contest 2020 Task E Three Substrings

题目链接
又是一道好题。
2020/3/15

这道题我没想到的一个点:对于两个串 $a, b$,如何快速判断 $b$ 相对于 $a$ 偏移 $k$ 是否可行?我只想到对二者重合的那一段逐个位置地判断。更好的方法是判断任意两个字符 $a_i, b_j$($i=0\dots |a|, j=0 \dots |b|$)是否相容(),若不相容则说明 $b$ 相对于 $a$ 偏移 $i - j$ 不可行。这样用 $|a| imes |b|$ 次判断就可以标记出哪些偏移量不可行

题目。
这题太好了。怎么赞美都不为过。

There is an arithmetic progression with $L$ terms: $s_0 , s_1 , s_2 , \dots , s_{L ? 1}$.

The initial term is $A$ , and the common difference is $B$. That is, $s_i=A + B i$ holds.

Consider the integer obtained by concatenating the terms written in base ten without leading zeros. For example, the sequence $3 , 7 , 11 , 15 , 19$ would be concatenated into $37111519$ . What is the remainder when that integer is divided by $M$?

Constraints

  • All values in input are integers.
  • 1 ≤ L , A , B < $10^{18}$
  • 2 ≤ M ≤ $10^9$
  • All terms in the arithmetic progression are less than $10^{18}$.

From official editorial.
Paraphrasing the problem as follows

  • We have two integers $X$ and $s$ written in base 10. Initially, $ X=0$, $s=A$.
  • In one operation, $s$ is appended to $X$, then incrase $s$ by $B$.
  • After $N$ operations, calculate the value of $X \bmod M$.

Denote the number of $d$-digit elements as $C_d$, $C_d$ can be easily obtained by subtracting the number of elements below $10^{d}$ from the number of elements below $10^{d-1}$.

The operation of concatenating $C_d$ elements with $d$ digits to the end of $X$ is equivalent to repeating $(X, s) \mapsto (X imes 10d + s, s + B)$ $C_d$ times. And this operation can be reduced to a matrix product as follows.

\begin{equation}
(X, s, 1) \begin{pmatrix} 10^d & 0 & 0 \\ 1 & 1 & 0 \\ 0 & B & 1 \end{pmatrix}=(X imes 10^d + s, s + B, 1)
\end{equation}

Therefore, the $C_d$ power of this 3 × 3 matrix needs to be obtained quickly, and the result is obtained with $O(\log C_d)$ time by the iterative square method.

If the above calculation is performed for $d=1, 2, \dots, 18$ in this order, the final value of $X \bmod M$ can be obtained quickly.

$2N$ 个格子(cell)排成一行,从左到右编号。每个格子是黑色或白色。现要进行 $N$ 次操作。每次操作选择两个编号不同的格子将二者之间(包括二者)的所有格子的颜色翻转。每个格子只能被选择一次。问有多少种方案使得最后所有格子都是白色。结果模 $10^9+7$ 输出。

最终结果和操作顺序无关。即答案可表为 $M N!$,$M$ 是不计顺序的方案数。

用 $(l, r)$ 表示一次操作,$l < r$。

对于一个方案里的两次操作 $(l_1, r_1)$,$(l_2, r_2)$,若 $\max(l_1, l_2) < \min(r_1, r_2)$ 则 $(l_1, r_1),(l_2, r_2)$ 和 $(l_1, r_2), (l_2, r1)$ 效果相同。这意味着对于每个格子来说,真正重要的是它作为左端点还是作为右端点。用 $L, R$ 分别表示一个方案中左、右端点的集合。若两个方案的左右端点合集分别相等,则这两个方案等价。

一个格子作为左端点是效果是翻转了「它和前一格子是否同色 」,而作为右端点则翻转了「它和后一格子是否同色」。
对于相邻的两个格子,若他们同为左/右端点,则二者是否同色结论将翻转,若一为左端点,一为右端点,则二则是否同色结论保持不变。据此,我们可以看出,某个格子是作为左端点还是右端点是确定的,因为最左端的格子一定是作为左端点。

余下的问题就是求左右端点的配对方案数(即上文所说的 $M$),不表。

Analysis

)

有 $n$ 个正整数 $a_1, a_2,\dots, a_n$($3\le n\le 300$,$1\le a_i \le 300$)。现在要把每个数涂成红,绿,蓝,三种颜色之一。将同色的数之和分别记作 $R,G,B$。试求使得 $R,G,B$ 是某三角形的三边长的涂色方案。结果模 $998244353$ 。

这道题的正解是考虑能构成三角形的涂色方案的数量。拿总方案数 $3^n$ 减去这个数量。

注意到 $R,G,B$ 三个数之和固定,将此和记作 $S$,即 $S=\sum_{i=1}^{n} a_i$ 。

$R,G,B$ 能构成三角形的充要条件是 $R,G,B$ 中某个数大于等于 $ S/2$ 。

又注意到,当 $S$ 是奇数时,$S/2$ 不是整数,上述充要条件变为 $R,G,B$ 中某个数大于 $S/2$ 。

我们先来考虑 $R, G, B$ 三者中某个数大于 $S/2$ 的方案数。
注意到 $R,G,B$ 三者中最多有一个数可能大于 $S/2$ 。由于染色方案的对称性,我们不妨先考虑 $R > S/2$ 的染色方案数。我们可以用类似于背包的 DP 求出使得 $R$ 等于某个确定值的染色方案数。令 $f[i][j]$ 表示对前 $i$ 个数染色,使得其中被染成红色的数之和为 $j$ 的染色方案数。那么 $3 \sum_{ R=\floor{S/2} + 1}^{S} f[n][R]$ 即为使得 $R, G, B$ 三者中某个数大于 $S/2$ 的染色方案数。

若 $S$ 是偶数,我们可以沿用上述方法求出使得 $R=S/2$ 的染色方案数,即 $f[n][S/2]$ 。但是若直接把 $3f[n][S/2]$ 加到总数里边,会导致重复计数。具体地说,这样做将使得 $R=S/2, G=S/2, B=0$,$R=S/2, G=0, B=S/2$ 和 $R=0, G=S/2, B=S/2$ 这三种情况被计了两次。而这三种情况的数量即从给定的 $n$ 个数中选择一些数使得其和为 $S/2$ 的方案数,用类似于背包的 DP 可以求出这个数量。将此数量记作 $k$ 。

总之,若 $S$ 为奇数,答案是 $ 3^n - 3 \sum_{ R=\floor{S/2} + 1}^{S} f[n][R] $;若 $S$ 为偶数,答案是 $3^n - 3\sum_{ R=S/ 2}^{S} f[n][R] + 3k$。

Key observation: 最后剩下的小球最初所在的盒子必定是连续的一段。

将盒子从左到右编号为 $1$ 到 $n$ 。

如果最初在 $i$ 号盒子里的小球,从左侧消失,那么 $1$ 号到 $i$ 号盒子中的小球必定都从左边消失了。

如果最初在 $i$ 号盒子里的小球,从右侧消失,那么 $i$ 号到 $n$ 号盒子中小球必定都从右边消失了。

我们可以二分搜索最后剩下的小球最初所在的范围的左右边界。

《Panasonic Programming Contest 2020 Task E Three Substrings》:等您翻牌子呢!

发表评论