破解密码

from：Starzxy

这都是vfk出的QAQ你萌别打我

算法一

暴力枚举每一位的字母,判段Hash值是否相等,时间复杂度$O({26}^n)$。可以获得20分。

算法二

用高斯消元消元就好啦，时间复杂度$O(n^3)$。可以获得50分。

算法三

对于每一个$a_i$，把它变为$a_{i+1}$就是把$a_i$的首字母移到最后一位，对应的，设$a_i$首字母为$c$，$h_{i+1}=((h_i-{26}^{n-1}\mathrm{num}(c))\times 26+\mathrm{num}(c))modp$。对于每一位，我们枚举$c$，因为$p$是大于$26$的质数，且数据保证有解，可以确定每一位有且仅有$1$个小写字母满足。

我为什么用了算法三只有50分？

刚刚最后一句话在逗你，有除法的地方一定要考虑没有逆元的情况！（别怪我们坑人……样例里就有 ${26}^{n}modp=1$）

对于刚刚推出来的$h_{i+1}$和$h_i$的关系，当${26}^{n}modp=1$的时候，$h_{i+1}=26h_{i}modp$，所以这时候$26$个字母都是满足哒！可能就会出现填出$n$个 “a” 的情况，除非$h_0=0$，否则不会满足题目的条件。

所以对于这种情况要特判一下，把$h_0$转成$n$位的26进制表示,再对应的转成字符串$s$，此时$f(s)=h_0$，而这时$h_{i+1}=26h_{i}modp$，只要$f(s)=h_0$，后面对应的旋转表示的hash值就都会满足啦。

时间复杂度$O(n)$，可以获得100分。

AC代码在这

智商锁

from：jiry_2

大家好这里是冒充Picks的JRY，其实嘛大家看到题目和生成树有关就应该猜到是我出的了？（雾）

预告和实际出题人不符其实也是有着很深的缘由...粗略来讲大致就是：本来Picks出了一道很有趣B给UR#6，然后发了预告开始写程序造数据的时候发现这题比原来想象的要难多了...一开始我们本着"即使出成UHR也不换题"的良好心态硬着头皮闷声造Round，但是昨天大家突然感觉这样似乎不大好？于是VFK就把毒瘤题推到以后再和大家见面，我们匆匆忙忙又重新造了一道B，因为时间仓促这道B比较简单，就当给大家送分辣。（注：UHR即UOJ Hard Round）

算法一

随便画一下就可以发现，$n$个点的环的生成树个数恰好为$n$，于是当$1\le k\le 100$且$k\ne 2$的时候，我们都可以用环来构造。注意要特判$k=0$的情况。这样可以通过前两个测试点。

算法二

$n$的范围这么小，自然就可以想到暴力大法好。首先，$6$个点的标号无向图只有$2^{(\genfrac{}{}{0ex}{}{6}{2})}=2^{15}$个，我们可以枚举每一张无向图，如果可以求出它的生成树的个数，那么就可以解决第三个点和第四个点了。

求无向图的生成树个数是一个经典问题，可以直接用基尔霍夫矩阵解决，这样时间复杂度是$O(2^{(\genfrac{}{}{0ex}{}{n}{2})}{n}^3)$，可以通过三四两个点。

当然如果不会基尔霍夫矩阵也没关系，$n$的范围这么小，我们大可以暴力到底，直接用状压DP或者索性搜索来解决，当然这可能无法在时间范围内得到解答。注意到六个点的标号无向图虽然有$2^{15}$个，但是本质不同的无向联通图的个数不是特别多，所以输入的$K$一定也不是很多，我们可以对于每一个可能的$K$都大暴力求出一张可行的无向图然后打表大法好！

算法三

接下来三个测试数据告诉了我们输入，一道构造题硬生生变成了题答题 ，所以我们就可以用解决构造题的思想来求解这三个测试数据：寻找输入的特殊性。

大家都应该知道，$n$个点的完全图的生成树个数是$n^{n-2}$，然后对比一看，发现第五个点的输入正好是这个！于是我们就可以愉快地输出完全图通过第五个点。

第六个点的数都比较大，看起来就像是挺难找到规律的样子。但是我们观察出题人（其实是VFK）给部分分的风格：既然环这种简单无脑的思路都给了20分了，完全图没有理由不给20分啊！于是我们把$n^{n-2}$的表给打出来，果然这些数都是取模过的$n^{n-2}$。于是我们就可以接着输出完全图通过第六个点。

至于第七个点，我们跑一下分解质因数就可以发现所有数都可以表示成若干个小质数的乘积。而在算法一中我们已经知道了怎么在$K$很小的时候构造满足条件的图，可以考虑一下两者之间的关联性。很显然的是，如果我们用桥边把若干个较小的图给串起来，那么得到的新图的生成树个数应该是这些小图的生成树个数的乘积。于是我们只需要把几个环给串成糖葫芦，就可以通过这个点啦！

算法四

接下来我们来考虑一种合理的构造方法，直接构造是比较困难的，因为我们现在只能对答案进行乘法（见第七个点）而无法进行加法。于是我们就可以开始尝试乱搞。

标程的做法是：随机1000张点数为12的无向图，用基尔霍夫矩阵求出第$i$张图的生成树个数$f_i$。然后对于每一个$K$，我们试图找到一个四元组$(a,b,c,d)$使得$f_a\times f_b\times f_c\times f_d\equiv K(\mathrm{mod}998244353)$，这个显然是可以meet in middle的，我们预处理它们两两的乘积与乘积的逆元，借助hash表就可以在约${10}^6$级别的运算量下找到一个合法的四元组。

这个做法相当于自行对最终的图添加了一个比较严苛的条件进行求解，为什么这样是靠谱的呢？接下来提供一种对正确性大致的解释（以下是数学渣JRY在没有任何道理的情况进行的口胡）：

首先我们随机无向图的方法是每一条边生成的概率都是0.8，而12个点的完全图的生成树个数是${12}^{10}$，这是远大于模数的，所以我们可以近似地把$f_i$看做均匀分布的随机数（这个和我们平时写的哈希表的思想类似）。接下来我们把这1000个随机数的集合四次方再模上模数，这样我们就得到了${10}^{12}$个数，和刚才同理，我们也可以把这${10}^{12}$个数给近似地看成均匀分布的随机数。

接下来我们要求的是${10}^{12}$个小于等于${10}^9$的随机数完全覆盖$0$到${10}^9$之间所有数的概率是多少。首先一个数被覆盖的概率是$1-(1-\frac{1}{{10}^9}{)}^{{10}^{12}}\approx 1-{\mathrm{e}}^{-{10}^3}$，我们可以近似地认为所有数都被覆盖的概率是$(1-{\mathrm{e}}^{-{10}^3}{)}^{{10}^9}$，实际上这个数是非常接近1的（因为${\mathrm{e}}^{{10}^3}$比${10}^9$大到哪里去都不知道了）

而且实际上，我也用电脑跑过 $k=0\sim 998244352$，这个算法都可以找到一组合法的解，跑得电脑黑汗水流。当然，因为输入数据组数有限，可能大家随便乱搞搞出一个接近$100\mathrm{\%}$正确率的算法就能过掉这题，但是这样的话说不定什么时候就被SXBK的Hack狂魔给搞成了97分了。

总结

总而言之，这道题作为B还是比较简单的，送的部分分多的都不像是我出的题了（雾）。另外，大家以后见到Picks那题时候可以脑补一下，这场UR在没有换题之前是怎样鬼畜的画风。

最后感谢业界良心的策爷对出题的帮助。

懒癌

from：jiry_2

大家好这里居然还是JRY，之前也是在UOJ上出了几道题，不过好像因为宣传上出现了一点偏差，给人留下了一种我只会出生成树的感觉？所以是时候来一道题扭转画风辣！

这道题的一开始来自于一道某城市的小升初数学题...那道题是二十个人每个人一只狗，每个人可以看到别人的狗但不能看自己的狗，有一天至少有一只狗生病了，每天上午每一个人可以去看一遍别人的狗，下午同时开枪。已知第二天开枪，问有几只生病的狗。

那个时候看到这题也是觉得挺有意思的，然后随手改成n个人第k天开枪问有几只生病的狗给VFK看看能不能当A> <然后被跳蚤国王一眼识破：“这真的不是原题吗。”之后我们花了很长时间来研究这个问题的各种变形，最后出出来这道题，感觉还是挺有趣的。

那也不扯下去了，切入正题来讲一下题解。

算法一

感觉最水的还是完全图的十分？现在，假设伏特跳蚤国王是狗主人之一，然后以他的视角来模拟这个流程。

如果第一天，伏特跳蚤国王走出家门一看：“咦，别人家的狗都没生病？”好那一定是自己的狗病了，“砰”。

如果第二天，伏特跳蚤国王走出家门一看：“咦，我只看到了一只生病的狗？”然后他靠着他超高逼格的智商开始分析：如果我的狗没有生病，那么昨天这只病狗的狗主人应该没有看到任何一只生病的狗，那昨天就应该有枪声！好一定是我的狗病了，“砰”。

以此类推。

所以我们知道，如果有$k$只生病的狗，一定会在第$k$天传来第一次的枪声。而且因为这k个狗主人的状况是完全等价的，所以他们一定会同时开枪。所以一个有$k$只生病的狗的生病状况，对总开枪时间和总枪声数的贡献都是$k$。所以两问的答案都是$\sum _{i=1}^n(\genfrac{}{}{0ex}{}{n}{i})\times i$

期望得分：10分

算法二

上一个算法也还是挺有启发性的，我们发现我们在分析自己的狗有没有生病的时候的方法是：假设我没有生病，然后看前一天是否应该发出枪声。而这个方法对任意图都适用的。

考虑状压DP，令$d{p}_U$表示$U$集合中的狗生病时的开枪时间。然后我们接着靠着伏特跳蚤国王超高逼格的智商分析：如果我的狗没病，那么什么时候应该听到枪声呢？于是跳蚤国王在大脑中枚举了所有可能的生病情况$V$，那么如果他的狗没有生病，他最迟应该在$maxd{p}_V$的时间听到枪声。所以他会在第$maxd{p}_V+1$天开枪。

所以我们就知道怎么DP了！对于一个状态，我们枚举这个状态中每只生病的狗的狗主人，那么这个状态的开枪时间应该是这些生病的狗主人中开枪时间的最小值，从中我们也可以知道有多少人同时开枪。

那么一个狗主人会枚举哪些可能的生病情况呢：首先对于所有他看到的狗，他枚举的生病情况一定是和当前情况相同的，其次他自己一定是没有生病的，而至于哪些他看不到的狗，他就只好枚举这些狗的生病状况了。

最后，如果有限时间内不会开枪怎么办？事实上是存在这种情况的，但是没关系，如果我们发现转移出现了环，所以这个环中的所有状态都是在有限时间内不会开枪的。

时间复杂度似乎是O($4^{n}n$)？可以通过前两个测试点。

算法三

有了算法二，我们可以把表打出来看看，然后就可以发现一个小小的规律：对于生病状态$U$和$V$，如果$U\in V$，那么必然有$d{p}_U\le d{p}_V$。至于这一个规律的证明我放在后面。

所以拥有超高逼格智商的伏特跳蚤国王就可以只枚举一种生病情况：首先对于所有他看到的狗，他枚举的生病情况一定是和当前情况相同的，其次他自己一定是没有生病的，而至于哪些他看不到的狗，由刚才的规律，可以全部当成生病的。

所以时间复杂度就可以降到O($2^{n}n$)，可以通过前四个测试点。

算法四

为了取得更多的分，我们需要一个多项式算法。我们重新来考虑有限时间内开枪的条件：转移无环。实际上这是一个很强的条件。

考虑根据转移建一个新图，如果$i$不能看到$j$，那么就在$i$到$j$连一条有向边。这个新图中可能有若干个强连通分量，如果一个生病状态中有生病的狗的主人是在一个多于一个点的强连通分量中，那么这一个状态一定无法在有限时间内开枪（转移有环），否则一定能在有限时间内开枪（转移无环）。

那么我们先把所有可以到达大小大于 $1$ 的强连通分量的点连同和他们相关的边一起删掉，于是我们得到了一个DAG！接着我们继续站在这张图的立场上来想怎么求一个状态的开枪时间：

首先这张图上有一些点被染黑了，黑点表示这只狗有病，白点表示这只狗没病。接着每一时刻，我们可以把一个黑点染白，然后把这个点连向的点的集合的一个子集染黑。若干轮之后，所有点都变白了。假设有$k$个点一度被染黑，那么开枪时间就是所有操作方案中最大的$k$。

看起来这个转化比较意识流，但是如果我们考虑怎么DP所有操作方案中最大的$k$，我们会发现这个DP方法和算法二是等价的。如果再要解释的话，首先枚举狗主人相当于枚举反转的黑点，算狗主人开枪时间中的$max$体现在求最大的一度被染黑的点数，算状态的开枪时间中对狗主人开枪时间取$min$体现在多次被染黑的点只被计算一次。

而在这个模型下，算法三的小规律就很显然辣！增加黑点对答案的贡献一定非负。所以问题又变成了：

一个DAG上有一些点被染黑了，接着每一时刻，我们可以把一个黑点染白，然后把这个点连向的点全部染黑。若干轮之后，所有点都变白了。假设有$k$个点一度被染黑，求所有操作方案中最大的$k$。

这不就是求DAG上一个点集能直接或者间接到达的点数吗？

所以我们把判断一个生病状态在第几天开枪转化为了求DAG上一个集合能直接或间接到达的点数。这样第一问已经非常简单了。考虑算每一个点的贡献，如果一个点能被$i$个点到达（包括自己），而DAG上一共有$N$个点，那么显然这个点的贡献就是$(2^i-1)\times 2^{N-i}$

接下来考虑第二问，一个人要在DAG上满足什么样的条件才会在第一天开枪呢？在原来的DP中，我们是在取$min$的过程中得到同时开枪的人数的，而我们知道，在现在的模型中，算状态的开枪时间中对狗主人开枪时间取$min$体现在多次被染黑的点只被计算一次。

所以我们脑补一下可以得到：如果一个点第一个反转，且之后得到的状态无论怎么操作都无法再把这个点染黑，那么这个点对应着一个最早开枪的狗主人。

所以第二问也可以很简单的解决了，还是考虑算每一个点的贡献，如果一个点能被$i$个点到达（包括自己），而DAG上一共有$N$个点，那么显然这个点的贡献就是$2^{N-i}$。

因为计算DAG中每一个点可以被多少点到达是O($nm$)的，而在这个DAG中$m$是O($n^2$)的，所以时间复杂度是O($n^3$)，可以通过前六个点。

算法五

最后的技术含量就很低辣，这个问题显然是可以压位的嘛，所以可以把时间复杂度搞到O($\frac{n^3}{32}$)，可以通过所有测试点。

什么，你说这个复杂度过不了$n=3000$？毕竟这个算法常数还是很小的嘛> >

好吧其实真相是本来数据范围我们放的是$n=1000$，然后写了一发$n^3$的暴力，发现只要跑0.1s 然后我们发现$n=3000$的时候标程0.2s暴力5s似乎非常和谐的样子，然后就放在这个数据范围啦！

VFK：今夜，我们都是Sereja

总之，如果有人因为$n=3000$而没敢写标算，请允许我做一个悲伤的表情。

总结

最后让我们来看看这道C到底是什么东西：

给定一个DAG，对所有的$i$求这个DAG上能到达第$i$个点的点的个数。

这题居然是UR的C！妈妈这次UR的画风不对。还有比我更良心的UR出题人吗！

最后这道题还有一个我们没有解决的EX版本大家做完这题可以想一想：

把最开始给的条件“至少一只生病的狗”改成“至少$t$只生病的狗”，其他不变。