BJOI 2019

奥术神杖

给你一个长度为$n$的串$T$，字符集为1234567890.。另外给你$m$个小串$s_i$，字符集为1234567890。每个小串有一个权值，对应为$v_i$。设$f(x)$表示$s_x$在$T$中出现的次数。现在要求你把$T$中所有的.替换为一个数字。设$C=\sum_{i=1}^mf(i)$，则要求你在替换后，最大化$\sqrt[C]{\prod_{i=1}^mv_i^{f(i)}}$。不用输出答案，输出任意一个替换方案。

$n,m,\sum s_i\le 1501, v_i\le 10^9$。

摘要：对数，二分，AC 自动机上 DP，精度。

设答案为$ans$，则做一下对数可以变成$\ln ans = \frac{1}{c}\sum f(i)\ln v_i$，就是一个经典的 01 分数规划问题了。你把$f(i)\ln v_i$理解为是$f(i)$个$\ln v_i$。设$mid=\ln ans$，那么得到$\sum (\ln v_i-mid)$。就可以二分了。

相当于，字符串每一次出现的权值变成了$\ln v_i-mid$，问是否存在一个替换方案使得权值和大于 0（or 小于）。这个可以对$s_i$建立 AC 自动机后 DP，设$F(i,j)$表示$T[1,i]$对应 AC 自动机上的状态$j$时的最大权值和。转移的时候记一下前驱和方案即可。

注意精度，大于 0 要写成大于 eps。

代码

光线

有$n$层玻璃。第$i$层玻璃的透光率和反光率分别是$a_i\%,b_i\%$。问$n$层玻璃从上到下依次叠一起时，从上到下的透光率。

$n\le 10^5,1\le a_i+b_i\le 100$。

摘要：叠一起后，你从上往下和从下往上就是不对称的情况（如果只有一层玻璃仍然是对称的）。

设$f(i)$表示前 i 个玻璃叠一起时，从上往下的透光率。答案就是$f(n)$。特别地，$f(0)=1$。

如何转移？考虑从$f(i-1)$转移到$f(i)$，相当于我们这一束光先透过前$i-1$层玻璃，然后透过第$i$层。但是会有一部分光反弹回第$i-1$层玻璃上去，这部分又可能弹回来。

因此我们还需要再设$g(i)$表示前 i 个玻璃，从下往上的反光率。这样我们就可以得到

$$\begin{aligned} f(i)&=f(i-1)(a_i+b_ig(i-1)a_i+(b_ig(i-1))^2a_i+\cdots)\\ &=f(i-1)a_i\sum_{j\ge 0}(b_ig(i-1))^j \end{aligned}$$

由于$b_ig(i-1)\le 1$，因此无穷级数可以化简封闭形式。类似地，$g(i)$也从$g(i-1)$转移：

$$g(i)=b_i+g(i-1)a_i^2\sum_{j\ge 0}(b_ig(i-1))^j$$

时间复杂度$O(n\log_2n)$。

代码

勘破神机

题意：设$F(n)$表示用多米诺骨牌填满$2\times n$的矩阵的方案数，$G(n)$表示用多米诺骨牌填满$3\times n$的矩阵的方案数。给出$l,r,k$，请分别求出$A,B$：

$$A=\frac{1}{r-l+1}\sum_{n=l}^r\binom{F(n)}{k}\\ B=\frac{1}{r-l+1}\sum_{n=l}^r\binom{G(n)}{k}$$

对 998244353 取模。

$T\le 5,l\le r\le 10^{18},k\le 501$。（$T$组数据）

摘要：斯特林反演下降幂转普通幂，特征方程求通项公式，然后做等式数列求和。要对根号扩域。

A 部分

对于$A$，可以先转化为求$\sum_{i=0}^n\binom{F(i)}{k}$，然后有

$$\sum_{i=0}^n\binom{F(i)}{k} =\frac{1}{k!}\sum_{i=0}^n F(i)^{\underline{k}}$$

根据第二类斯特林数的普通幂转下降幂，再套一个斯特林反演上去就可以反过来做：

$$x^{\underline{k}}=\sum_{i=0}^k(-1)^{k-i}s(k,i)x^i$$

于是得到

$$\sum_{i=0}^n F(i)^{\underline{k}}=\sum_{j=0}^k(-1)^{k-j}s(k,j)\sum_{i=0}^nF(i)^j$$

我们要快速算后面这部分，就得再做更多转化。容易发现$F(n)=F(n-1)+F(n-2)$且$F(0)=F(1)=1$，相当于是一个斐波那契数列（其实$F(i)=F_{i+1}$，移了一位）。由于

$$F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$$

设$A=\frac{1}{\sqrt{5}},x=\left(\frac{1+\sqrt{5}}{2}\right),B=-\frac{1}{\sqrt{5}},y=\left(\frac{1-\sqrt{5}}{2}\right)$，于是我们得到

$$\begin{aligned} \sum_{i=0}^nF(i)^j &=\sum_{i=1}^{n+1}F_{i}^j\\ &=\sum_{i=1}^{n+1}(Ax^i+By^i)^j\\ &=\sum_{i=1}^{n+1}\sum_{d=0}^j\binom{j}{d}A^dx^{id}B^{j-d}y^{i(j-d)}\\ &=\sum_{d=0}^j\binom{j}{d}A^dB^{j-d}\sum_{i=1}^{n+1}(x^{d}y^{j-d})^i\\ \end{aligned}$$

后面是个等比数列求和，可以写成封闭形式加速。

做到这里看似没有问题。但是$\sqrt{5}$在模 998244353 意义下不是二次剩余！但这也不难。我们对数扩域，把每个数表示成$a+b\sqrt{5}$的形式即可。最后算出来的答案一定满足$b=0$。因此不必担心。

B 部分

$B$的难点在于递推式的推导。容易发现$G(n)$在$n$为奇数时等于$0$，因此我们设$g_n=G(2n)$。我们尝试推导$g_n$的递推式。

经过一番推导可以发现$g_n=4g_{n-1}-g_{n-2}$。然后解一下特征方程就得到了

$$g_n=\left(\frac{1}{2}+\frac{\sqrt{3}}{6}\right)(2+\sqrt{3})^n+\left(\frac{1}{2}-\frac{\sqrt{3}}{6}\right)(2-\sqrt{3})^n$$

这样就可以求答案了。注意有点小细节，就是在这里是没有移一位的，所以$i\in[0,n]$而不是$[1,n+1]$。

时间复杂度$O(k^2\log_2n)$。

代码

排兵布阵

你有一个$s\times n$的非负整数矩阵$A$，满足$\forall i\in[1,s],\sum_{j=1}^nA_{ij}\le m$。你可以任意构造一个长度为$n$的非负整数序列$B$，使得$\sum_{i=1}^nB_i\le m$。你的序列的权值为

$$\sum_{i=1}^s\sum_{j=1}^n [2A_{ij}<B_j]j$$

求最大权值。

$n,s\le 100,m\le 20000$。

摘要：简单 DP。

发现每一列是独立的，把每一列的当作一组背包起来即可。

换一个说法，你想一个时间复杂度为$O(nms)$的算法就随便过了。

写的时候想写一个小优化，结果边界没处理好被卡 90 了好久……

代码

送别

题面太长。

摘要：估计是让你送别 OI 才出的这道题。

把一堵墙拆成两条并列的边。那么摸着墙走相当于在边上走。

进一步发现，整个图一定由若干个环构成。

于是我们用平衡树维护环，对于询问操作就先看他们在不在一个环上，在就查询距离，不在就输出 -1。

修改操作相当于要考虑加一个环，删一个环，把两个环连起来，把环断开。讨论即可。

时间复杂度$O((nm+q)\log_2(nm))$。平均代码复杂度 7k。

代码

删数

对于任意一个数列，如果能在有限次进行下列删数操作后将其删为空数列，则称这个数列可以删空。一次删数操作定义如下：记当前数列长度为$k$，则删掉数列中所有等于$k$的数。

现在有一个长度为$n$的数列$a$，有$m$次修改操作：

• 单点修改；
• 所有数$\pm 1$。

求第$i$次修改后的$a$，至少需要修改几个数才能删空？

$n,m\le 1.5\times 10^5,1\le a_i\le n$。

线段树 构造

对于一个静态的序列如何求出答案？

考虑建立权值数组，$c_i$表示$i$的出现次数。那么不妨把$c_i$当成一摞方块，那么我们把这个柱子向左平推推倒，这样会覆盖$[i-c_i+1,i]$。对每个权值这样操作后，没有被覆盖的位置的个数就是答案。证明：从合法性和最优性两个角度。

那么对于修改操作，所有数$\pm 1$相当于是数组的平移，记个指针就行。单点修改也很好维护。

使用线段树维护。时间复杂度$O((n+m)\log_2n)$。