Contest Info

practice link

Solutions

A. Beautiful Regional Contest

签到题。

B. Beautiful Sequence

签到题。

C. Beautiful Mirrors with queries

签到题。

D. Beautiful Bracket Sequence

题目大意：定义一个合法的括号序列的代价为其最高的嵌套层数（意会一下），定义一个括号序列（合法或非法）的价值为其所有合法子序列的最大代价。给你一个括号序列，有些位置是 ?，问 ? 处填 ( 或 ) 的所有可能方案的价值之和。

题解：把 ( 视为 \(+1\)，) 视为 \(-1\)，那么一个合法的括号序列的代价就是它最大的那个前缀和，设为 \(p\)。那么容易证明，它一定存在一个子序列，由 \(p\) 个 ( 后接 \(p\) 个 ) 组成。所以一个括号序列的价值就是 \(\max_{0\le i\le n}\min(\text{cnt}_{1..i}[{\text{'('}}],\text{cnt}_{i+1..n}[\text{')'}])\)。如果能构造出更大代价的子序列，那么它一定会有一个子序列使得上式矛盾。

考虑这样来计算一个括号序列的价值：对于它的第 \(i\) 个左括号，如果它右边的右括号数量 \(\ge i\)，就给价值贡献 \(1\)。不妨设该括号序列的价值为 \(p\)，显然我们把分割线贪心地放在尽可能左，分割线右侧的右括号数量就越可能满足，所以贪心地选取左起第 \(p\) 个左括号是最优的，一定能在右边找到 \(p\) 个右括号。因此这样的答案恰好是括号序列的价值。

回到原问题。我们枚举第 \(i\) 个位置（不能是 )）作为第 \(j\) 个左括号，这就要求它左边恰有 \(j-1\) 个左括号，右边至少有 \(j\) 个右括号。设该位置左边有 \(x\) 个问号，\(u\) 个左括号；右边有 \(y\) 个问号，\(v\) 个右括号。那么答案为

\[ {x\choose j-1-u}\sum_{i=j}^{+\infty}{y\choose i-v} \]

如果我们预处理组合数的后缀和，那么就已经可以 \(\mathcal{O}(n^{2})\) 地求出答案，从而通过 D1。

再来推导一下式子：

\[ \begin{aligned} &\sum_{j=0}^{+\infty}\left({x\choose j-1-u}\sum_{i=j}^{+\infty}{y\choose i-v}\right)\\ =&\sum_{j=0}^{+\infty}\left({x\choose j-1-u}\sum_{i=j}^{+\infty}{y\choose y-i+v}\right)\\ =&\sum_{\delta=0}^{+\infty}\sum_{j=0}^{+\infty}{x\choose j-1-u}{y\choose y-j-\delta+v} \end{aligned} \]

\(j\) 显然涵盖了所有左边组合数合法的范围，根据范德蒙恒等式有：

\[ \begin{aligned} =&\sum_{\delta=0}^{+\infty}{x+y\choose v+y-\delta-1-u} \end{aligned} \]

同时发现，\(x+y\) 要么等于问号数量（选择了左括号），要么等于问号数量减一（选择了问号），所以预处理两种组合数的前缀和即可。

复杂度 \(\mathcal{O}(n)\)。

E. Beautiful League

凸费用流，pass

F. Beautiful Fibonacci Problem

题目大意：给出斐波那契数列 \(f_{0}=0,f_{1}=1,f_{n}=f_{n-1}+f_{n-2}\)，以及等差数列 \(a+id\)，满足 \(1\le a,d,a+(n-1)d<10^{6}\)。要求你构造出 \(b,e<2^{64}\)，使得 \(a+id\) 是 \(f_{b+ie}\) 的后 \(18\) 位的子串。

题解：注意到斐波那契数列在模 \(10^{k}\) 的意义下以 \(n=12\times10^{k}\) 为循环节。因此 \(f_{un}\equiv0\pmod{10^{k}}(u\in\mathbb{N})\)。又有公式 \(f_{n+m}=f_{n+1}f_{m}+f_{n}f_{m-1}\)。

考虑 \(f_{un+1}=f_{(u-1)n+1}f_{n+1}+f_{un}f_{n}\equiv f_{(u-1)n+1}f_{n+1}\pmod{10^{2k}}\)，从而 \(f_{un+1}\equiv f_{n+1}^{u}\pmod{10^{2k}}\)。又有 \(f_{n+1}=8t\cdot10^{k}+1\)，其中 \(t\) 不含 \(2\) 和 \(5\)（不会证），因此 \(f_{n+1}^{u}\equiv8ut\cdot10^{k}+1\pmod{10^{2k}}\)。这样基本就很简单了，我们令 \(k=9\)，让 \(u\) 是 \(125\) 的倍数，然后使得第 \(12-17\) 位为输入序列即可。

这怎么想嘛。。。