新年的促销

from vfleaking

远离 OI 多年的 vfk 老当益壮，又来出送分题辣 ~\(≧▽≦)/~

题意是说 $n$ 个物品的01背包，但是有买 $a$ 赠一和买 $b$ 赠一的白给活动，是不是很喜闻乐见呢？

算法一

对于前两个点，$n\le 10$。所以我们只需要枚举所有可能的购买方案，然后按题意模拟就好啦。

时间复杂度 $O(n\cdot 2^n)$，期望得分 20 分。

算法二

对于前六个点，$O(n^{3}m)$ 的复杂度应该是跑得动的。

我们可以考虑 DP，暴力把所有东西记下来。用 $f[i,u,q,j]$ 表示前 $i$ 袋米，购买了 $u$ 袋，白拿了 $q$ 袋，共花了 $j$ 块钱的情况下总重量的最大值。

DP 方程易得：

$$f[i,u,q,j]=min\{\begin{array}{ll}f[i-1,u,q,j]& \text{不购买，不白拿}\\ f[i-1,u-1,q,j-p_i]+w_i& \text{买！}\\ f[i-1,u,q-1,j]+w_i& \text{拿！}\end{array}$$

判一判边界情况，然后 DP 结束后取出那些 $q\le \lfloor u/a\rfloor +\lfloor u/b\rfloor$ 的状态更新下答案就可以拿到 60 分咯。

算法三

对于第 7, 8 号点，需要在 $O(n^{2}m)$ 的时间内解决，但有个特殊条件是 $a=b$。

重新考虑考虑算法二，就会发现这种情况下在 DP 结束之后只需要判断 $q\le 2\lfloor u/a\rfloor$，也就是 $u-a\lceil q/2\rceil \ge 0$。所以我们在 DP 的时候可以把 $u,q$ 这两维换成 $u-a\lceil q/2\rceil \in [-n,n]$ 和 $q$ 的奇偶性，这样 DP 的复杂度就降为 $O(n^{2}m)$ 了。

结合算法二，期望得分 80 分。

算法四

对于所有数据，需要在 $O(n^{2}m)$ 的时间内解决，且没有特殊条件。

让我们来考虑一下这样一个判定性问题：如果已知自己要购买或者白拿的所有米袋，怎么判断手上的 $k$ 块钱是否够用？

显然，我们可以把这些米袋按价格排序，然后按价格从低到高依次买，买到不能买的时候判断下剩下的米袋是否可以全部白拿走。

所以 DP 的时候也可以这样做：先把所有物品按价格排序，即 $p_1\le p_2\le \cdots \le p_n$，然后依次决定买还是不买，拿还是不拿。

由前面的判定性问题可知，在最优方案里肯定存在一个 $I$ 使得对于 $i\le I$ 的米我们要么买要么不买，一定不会白拿；对于 $i>I$ 的米，我们要么白拿要么不白拿，一定不会买。

所以我们可以使用普通的背包 DP 求出 $f[i,u,j]$，表示前 $i$ 袋米，购买了 $u$ 袋，共花了 $j$ 块钱的情况下总重量的最大值。再用普通的 DP 求出 $g[i,q]$ 表示后 $n-i$ 袋米，白拿了 $q$ 袋的情况下总重量的最大值（其实这里排个序贪心就好了）。然后枚举 $I$ 的值，就可以轻松 $O(n^{2}m)$ 啦。

期望得分 100 分。

道理我都懂，但为什么我 80 分？

因为你可能算 $g[i,\lfloor u/a\rfloor +\lfloor u/b\rfloor ]$ 的时候没有判断 $\lfloor u/a\rfloor +\lfloor u/b\rfloor >n-i$ 的情况导致了某种越界。

新年的新航线

from peehs_moorhsum

zhouyuyang哥哥帮忙看了题，并且造数据卡掉了乱搞

gamegame是此题一血

算法一

我会枚举生成树！

时间复杂度 $\mathrm{\Theta }(2^{2n-3})$，可以通过第一个subtask，预计得分 $20$。

算法二

这道题大概有许多种乱搞..

比如随机一个删点序列，满足每次删掉一个最外围的点；删掉的时候随机将它相连的两条边之一取出来，最后三个点随机选两条边，这样一定是生成树

然后按照序列顺序一轮轮看，看每轮连的边换成另一条之后二度点的个数是否减少，减少则交换

长时间没有更新则改变序列重来

时间复杂度 $\mathrm{\Theta }(\mathrm{玄}\mathrm{学})$，经测试可以通过前两个subtask；写得优美可能通过subtask 5。 预计得分 $40\sim 50$。

算法四

考虑将三角形作为顶点构建生成树；然后对每棵子树，和边界上多边形顶点的度数/连通性进行DP

可以做到线性。但由于实现复杂度较高、时空常数较大，这里不再展开。

算法五

事实上，如果$n\ne 3$ 则一定有解。

明确这一点之后，考虑一个最外层的点；则它的用处是：将相邻两点之一度数加一。

设它相邻的点为$u$, $v$，点本身为$i$，考虑删去$i$，并在$u$到$v$的边上标上$i$，表示$u$, $v$中要恰有一个点和$i$连边。

于是我们面对这一个，边界上的每条边可能有标数的凸多边形。

如果顶点数不超过$4$，可以暴力搜索。

否则仍然考虑一个最外层的点$i$，以及其相邻点$u$，$v$.

如果$(i,u)$，$(i,v)$均无标数，如前文所述删掉即可。

如果$(i,u)$，$(i,v)$均有标数，将所标的数都连向$i$，并抹去标数，可以转化成均无标数的情况。

如果$(i,u)$，$(i,v)$一个有标数、一个没有，不妨$(i,u)$有标数$s$

则连接$(i,u)$, $(s,u)$，删去点$i$即可。此时边$(u,v)$不需要标数。

一直删点，直到点数不超过$4$，而后搜索。

对每个点记一下有标号相连的点的数组，容易做到线性。

时间复杂度 $\mathrm{\Theta }(n)$，预计得分 $100$。

新年的复读机

from EntropyIncreaser，zhouyuyang

算法一

考虑进行区间 DP，则有 $f(l,r)=\underset{k=l}{\overset{r-1}{min}}f(l,k)+f(k+1,r)+g(l,k)+g(k+1,r)$。

其中 $g(l,r)=gcd\{a_l,a_{l+1},\dots ,a_r\}$。

时间复杂度 $\mathrm{\Theta }(n^3)$，预计得分 $5\sim 20$。

算法二

事实上这一过程有一个非常强的性质：必然存在某个最优解中有一个数，每次都是这个数和相邻的进行合并。

我们考虑将合并过程看做一颗二叉树，假设存在某个节点的左右子都有孩子且任意一种 rotate 后的情况都不优，不妨这四个孩子为 $gax{r}_1,gacxy{r}_2,gbcxy{r}_3,gby{r}_4$，其中这些数的取法为：先将四个数的 $gcd$ 取为 $g$，并将整体除以 $g$，然后取 $x=gcd(a_1,a_2,a_3)$，将这三者除以 $x$……以此类推。这样我们就可以根据两种旋转都不优推出两个式子：

$$ax+by<ax+x,ax+by<by+y$$

两式相加得到 $ax+by<x+y$，而 $a,b\ge 1$，因此矛盾。

故最优解树上可以不存在同层的 $4$ 个节点，这样一个方案必然是某个数一直和相邻的数合并得到的。

因此区间 DP 可以直接改为 $f(l,r)=max(a_l+g(l+1,r)+f(l+1,r),a_r+g(l,r-1)+f(l,r-1))$。

取决于 $g$ 的不同计算方法，时间复杂度为 $\mathrm{\Theta }(n^2)\sim \mathrm{\Theta }(n^2\log a)$。预计得分 $20\sim 35$。

算法三

接下来的叙述需要用到以下引理：

引理 1

给 $k$ 个数求 $gcd$，直接递推调用欧几里得算法，时间复杂度为 $\mathrm{\Theta }(k+\log a)$。

注意到欧几里得算法执行 $(a,b)$ 的过程与 $(\frac{a}{gcd(a,b)},\frac{b}{gcd(a,b)})$ 相同，所以我们可以得到一个复杂度的表示 $\mathrm{\Theta }(\log \frac{a}{gcd(a,b)})=\mathrm{\Theta }(\log a-\log gcd(a,b))$。

我们进行递推的时候，复杂度裂项相消就得到了 $\mathrm{\Theta }(k+\log a)$。

引理 2

对于一个数列 $n$，前缀 $gcd$ 的连续段有最多 $\lfloor {\log }_{2}a\rfloor +1$ 个。

由于前缀 $gcd$ 如果有变化则至少除以 $2$，得证。

那么接下来我们考虑对每个数为起点进行 DP，注意到我们的过程一定是这个数向一个方向合并直至 $gcd$ 发生变化，而两个方向都最多改变 $\log$ 次，那么我们在这个简化的状态上进行 DP 即可，状态数为 $\mathrm{\Theta }({\log }^{2}a)$，通过正确的求 $gcd$ 方法可以使得转移的复杂度总共也是 $\mathrm{\Theta }({\log }^{2}a)$，因此本算法的复杂度为 $\mathrm{\Theta }(n{\log }^{2}a)$。

预计得分 $65$。

算法四

本来标算是上面的做法，但是 zhouyuyang 进一步加强了此做法。

我们考虑变换视角，当我们当前合并的一整段为 $[l,r]$ 时，记 $R(l,k)$ 表示左端点为 $l$，下一步行动为向右合并，目前的 $gcd$ 为从 $l$ 开始的 $gcd$ 连续段的第 $k$ 段出发，接下来的最小代价。类似的我们可以定义 $L(r,k)$。通过离线基数排序我们可以在 $\mathrm{\Theta }(n\log a)$ 时间内计算出 DP 的转移图。时间复杂度为 $\mathrm{\Theta }(n\log a)$。

预计得分 $100$。

新年的追逐战

from EntropyIncreaser

算法一

对于 $n=1$ 的情况，就是要计算出所有无向简单图的连通块数量的求和。

记无向简单图的 EGF 为 $G(x)=\sum _{n\ge 0}\frac{2^{(\genfrac{}{}{0ex}{}{n}{2})}{x}^n}{n!}$，则联通图的 EGF 为 $C=\ln G$。不难得到连通块数量的 EGF 由枚举连通块如何插入一个图得到，即为 $G\ln G$。

预计得分 $20$。

算法二

我们考虑给我们一组 $G_k$ 的序列之后如何计算连通块数量。

首先考虑在每个图中选一个点，如果某个选的点数的度数为 $0$（我们称其为“孤立点”），则这个点序列在 $H$ 上对应的点是孤立点。

否则我们考虑每个图中选择一个大小 $>1$ 的连通块。考虑这些连通块的乘积得到的连通块有多少。注意到现在每个点都有邻边，且是无向图，因此我们可以在一条边上反复走。两个点序列之间的可达性可以简化为路径长度的奇偶性。

如果两个点在一个存在奇环的图中，那么显然奇数长度和偶数长度的路径都有。

如果两个点在一个二分图中，那么这和他们是否在同一部中有关。

因此我们可以得到：如果选的这 $n$ 个连通块中有 $k$ 个不存在奇环，那么这些连通块的乘积将会给答案贡献 $2^{max(k-1,0)}$ 个连通块。

因此我们只需要知道全体大小为 $m_k$ 的图可以有多少个孤立点，多少个无奇环的连通块，多少个连通块，则可以由此算出答案。

我们考虑染色二分图的 EGF：$B=\sum _{n\ge 0}\sum _{m\ge 0}\frac{(\genfrac{}{}{0ex}{}{n+m}{n})2^{nm}{x}^{n+m}}{(n+m)!}$，则无奇环的连通块显然恰有 2 种方法染色，可以得到 EGF 为 $\frac{\ln B}{2}$，无奇环连通块数量可以通过 $\frac{G\ln B}{2}$ 表示。

然而 $B$ 的 EGF 这里要 $\mathrm{\Theta }(n^2)$ 计算，预计得分 $50$。

算法三

我们考虑如何快速计算 $B$。

我们考虑在一开始生成两部的时候将两部内部的边去掉，也就是乘以 $2^{-(\genfrac{}{}{0ex}{}{n}{2})}$，可以得到

$$B=\sum _{n\ge 0}\sum _{m\ge 0}{2}^{(\genfrac{}{}{0ex}{}{n+m}{2})}\frac{2^{-(\genfrac{}{}{0ex}{}{n}{2})}{x}^n}{n!}\frac{2^{-(\genfrac{}{}{0ex}{}{m}{2})}{x}^m}{m!}$$

可以看到只需要先计算 $\sum _{n\ge 0}\frac{2^{-(\genfrac{}{}{0ex}{}{n}{2})}{x}^n}{n!}$ 即可。

这种转换也有另一个名字，叫做 z 变换。

时间复杂度 $\mathrm{\Theta }(n\log n)$，预计得分 $100$。

新年的邀请函

idea 来自 bulijiojiodibulido

peehs_moorhsum造了标程/数据，并和提供idea的哥哥一起想了标算；

whzzt哥哥验了题，并提供了另一种标算

fjzzq2002是此题一血，也是全场唯一通过的人

算法一

我会枚举素数，用欧拉判别法判二次剩余！

时间复杂度 $\mathrm{\Theta }(m)$，预计得分 $10$。

算法二

由于生成的数在${10}^9$范围内，容易发现，会有约$400$个数的素因子只含有前$30$个素数。

利用高斯消元和二次剩余的积性，可以求出来前$30$个素数是否是二次剩余。（在随机的情形下，可以解出所有）

基于二次互反律，我们在枚举$p$模$4$的余数之后，可以知道$p$模前$30$个素数中的每个是否是二次剩余。

我们考虑前$k$个素数的乘积$s$，则$p$模$s$的余数只有约$s/2^k$种（事实上，由于素数$2$以及余数不能为$0$，会更小一些）

取 $k=10$ 并枚举所有模$s$合法的素数$p$，用欧拉判别法判断。

时间复杂度 $\mathrm{\Theta }(s+m/2^k\ast log(m))$。 可以通过前四个点，预计得分$40$。

算法三

在算法二的基础上略加改进。

判断时，我们先判断$p$模前$30$个素数中剩下的那些是否满足；如果不满足直接返回false，否则再用欧拉判别法对每个$t_i$依次判断。

这样单次判断的期望复杂度减到$\mathrm{\Theta }(1)$

时间复杂度 $\mathrm{\Theta }(s+m/2^k)$。 可以通过前六个点，预计得分$60$。

算法四

每个素数均可以写成 $a\ast s+b$的形式；其中$b$的合法取值只有约$s/2^k$种

对每个$a$，用一个bitset记录每个合法的$b$在当前是否被筛掉。

而后考虑第$k+1$到第$k+u$个素数；用每个素数去筛掉那些模该素数不合法的。

这一步只需要对 $a=0,1,...,$p-1$$

求$p$个bitset $r_0$, $r_1$, ..., $r_{p-1}$,

表示对应哪些$b$不行

然后对每个$a$，将$a$对应的bitset与$r_{amodp}$ 的反取交即可。

最后对没有筛掉的所有数进行判断。这样数的个数只有约$m/2^{k+u}$

时间复杂度 $\mathrm{\Theta }(s+m/2^{k+u}+u\ast s/2^k\ast p_{k+u}+m/2^k/w\ast u)$。

实践中取$k=8$, $u=10$最快，可以在400ms内通过最大的测试数据，预计得分$100$。

算法五

考虑模前$10$个素数乘积$r$的余数$u$和模第$11$到$15$个素数乘积$t$的余数$v$。

利用中国剩余定理合并；知模$rt$的余数为$u+s\ast r\ast (v-u)$, 其中 $s\ast r$ 模 $t$ 余$1$。

上式可写为$(u-s\ast r\ast u)+s\ast r\ast v$，前者只与$u$有关，后者只与$v$有关。

可以Meet in Middle求出所有1e12以内的余数，而后像之前一样检验。

预计得分$100$。