总结

今天是腊月十三！看了下日历，哈，新的一年，这么快，又要来了，什么时候要过去呢？来都来了，也没有什么好兴奋的了。

去重庆前最后一天模拟赛咯，曾师说明天模拟赛就不做了，复习。今天的模拟赛还蛮不难的。100 + 50 + 100 + 76。但是自己还是有一些问题，缺乏一些小技巧，和对简单模板的耦合度。

P.S. 今天标签可真多呀。

题解

来说说今天的题目，今天 DIV1 T4 是交互题，看起来很好玩，但是很难。（为什么会觉得不难）。

A. Signin

题面好难说啊。还得手打一遍。就是说有件物品。它们的价格分别可以表示为。

以这样的方式给出，其中为互不相同的质数。

令

现在你手上有元钱。以这样的方式给出，其中为给定的个可以相同的质数。

问是否存在方案，购买若干件物品（注意只有件物品），花光元钱。

手搓一下容易发现可以的和是不选的质数乘起来，然后乘上一个剩下的质数的积依次除以每个质数的和。那么显然里面一定有没有选的质数。那么如果没有选，一定在中出现。那么其必要性呢？容易发现剩下的那个和一定和剩下的质数都互质。因为互不相同，如果不互质，就一定有公因数，这是不可能的。所以如果选了，就不会在中出现。所以去掉相同的，验证一下是否相等就行。可以高精度或者 hash 验证。

，。

B. Y

这道题还是有点难的。每次随机生成一个的整数，生成了个，求前个的和比后个大的概率。

。

法一是组合方法，就是说可以转换成求相等的概率。那么相当于前几个和后几个加起来相等。考虑把后个取相反数，这样和就固定了，为。然后给后面都加上变非负，就转化成了，有个数，和为的方案数。这是一个经典的容斥。不是很熟悉，但是今天熟悉了。

法二是用多项式，能推出同样的式子。感觉似乎更容易想到？（虽然我考场上都没有想到）。

$$
F=\sum_{i=0} f_ix^i=\left(\frac{1-x}{1-x^{m+1}}\right)^n\Rarr S=\sum_{i=0}^{nm}([x^i]F)^2

$$

容易发现，因为是对称的（和上一种方法那个其实是本质相同的）。

那么得到

$$
S=x^{nm}=[x^{nm}]\left(\frac{1-x}{1-x^{m+1}}\right)^{2n}=x^{nm}^{2n}
$$

现在就和上面一样算就行了。

C. hashit

就是动态维护子串个数的题目。每次从尾巴上删除或加字符，求不同子串个数。一眼后缀平衡树，直接 hash + set 维护就行（两个）。似乎可以用广义后缀自动机，但那玩意我不会。当然也可以在 Trie 树上建立 SA，但还是觉得第一种真的太好写啦！

D. 点点的圈圈

就是平面上存在一些不相交也不相切的圆，然后每个圆有一个权值，要求选一些圆，选出的圆不能被包含。很容易想到建树然后跑 dp 就完了。那么问题在怎么建树呢？众所周知，这是 IOI 比赛，所以我们可以使用人类智慧法！

我们当然要使用更高级的方法！我们发现扫描线移动的时候圆的相对位置关系不会改变，因此每个圆维护一个上半圆和下半圆，放在里面，每次加圆维护下半圆的前驱，如果是上半圆那么和它是兄弟，下半的话就是儿子，否则就是一个根，可以连接向我们一个虚拟的根节点表示整个平面。

D. 图上的游戏

一个交互题。不会做摆在这里。就是告诉你一张连通图的，然后你每次可以询问在图中加入一些边（通过边的编号)，然后再询问一个点，表示加入这些边后能否从到达这个点，最后让你在次询问内得到这张图。

很容易想到做一个生成树然后加边。题解就从链、树、图的顺序来讲。链很简单，然后树就看不懂了，然后弄出生成树再拓展出其它边。打乱加点的顺序（看题解有一点迷惑，一会期望一会均摊的），然后不断二分就行。思路大抵是懂了，但是代码看起来就……好难。去补 atcoder 的题目了，luogu 还有一堆补题列表，唉。

接下来是 atcoder 的题目！

[ABC336G] 16 Integers

就是 01 序列，首尾相接，满足出现固定次数。

很容易想到之前很多类似的题目，就是那道 01 串使得子串数量最多的那个题目。（好像也就一道题吧？）可以建图构成一条路径。但发现经过点多少次的好像不会？还是根据之前那道题目，发现降一维就能变成边了！多少次相当于这条边连了多少次，那么就相当于找欧拉路径了！想到了什么？OI-WIKI 上面矩阵树定理的 BEST 定理！由于是路径，两个奇数点连起来就行。

后记

明天就不考试啦，明天就复习一些薄弱斑块吧。晚上好啊！