万分感谢Claris的验题以及验题组成员们给予的建议和帮助。 ## Rikka with Graph 如果连上1-$n$的边，最短距离就是1。所以所有情况下最短距离都是1。 考虑方案数，如果本来没有1-$n$的边，那么只能连1-$n$，方案数为1。否则怎么连都可以，方案数是$\frac{n(n-1)}{2}$。 ## Rikka with Tree 显然一棵树是独特的当且仅当任意处于每一个深度的点数是"1 1 1 1 ... 1 1 x"。所以直接DFS一下求出每一个点到根的距离然后判断一下就好了 。 ## Rikka with Graph II 如果图是联通的，可以发现如果存在哈密顿路径，一定有一条哈密顿路径的一端是度数最小的点，从哪个点开始直接DFS搜索哈密顿路径复杂度是 $O(n)$的。要注意先判掉图不连通的情况。 ## Rikka with Tree II 把所有点按照深度排序，然后枚举深度最深的点和次深的点。假设深度次深的点是第$i$深的，那么这个值的贡献就是$\frac{2^{i-1}}{(2^n-1-n)}$。 这样直接统计复杂度是$O(n^2)$的。可以发现当n很大的时候，一个方案的贡献可以近似为$2^{i-n-1}$，而题目只需要保留六位小数，所以当i比 较小的时候贡献可以忽略不计，$i$只要枚举到$n-60$左右就肯定可以通过这题了。 ## Rikka with Game 听说jiry_2这个ID加上1004这个题号会降低AC（胡）率，不知道是不是真的。于是今天就来逼真的演一把给大家送AK送温暖咯.. 考虑这样的DP，令$dp_{i,j}$为以$i$为根的子树，用了$j$次外交关系的最优值。然后每次合并两个部分$l$个$r$的时候，我们用两重for循环， 一边枚举到$\min (size_l ,k)$，一遍枚举到$\min (size_r,k)$，然后合并。 这个做法其实是$O(nk)$的.. 怎么证明复杂度，分这两个步骤： 1.我们先考虑所有合并之后的部分大小介于$[k,2k)$之间的合并过程，我们把这些合并过程都做了。这样每一个合并的部分一定是把一个树形子图 给合并到一起。如果这个子图的大小是$S$，那么这个子图中任意两个点在它们的LCA上产生了1的贡献。所以合并这个子图的复杂度是$O(S^2)$的， 那么每一个点产生的贡献就是$O(S)$即$O(k)$的，所以这个部分的复杂度是$O(nk)$。 2.考虑剩下的合并部分，这样合并的时候必定有一个部分的大小是大于等于$k$的，这样合并之后另一个部分相当于删掉了，因为在接下来的合并过 程中，这一部分并没有再产生贡献。所以此时删掉一个点的复杂度是$O(k)$，所以这个部分的复杂度还是$O(nk)$的。 所以这个算法是$O(nk)$的。 当然也有一些非常显然是$O(nk)$的算法..这儿就不多说了..考场上似乎也没有几个胆子大的小哥暴力强上这题..还是挺遗憾的。 我都演的那么逼真了！怎么AK的还是这么少！这不科学！

万分感谢zimpha验题以及在本人出题过程中的指导和帮助。 这套试卷的1000和1004的出题人是VictorWonder，1001、1002和1003的出题人是我。 ## 1000 Victor and Machine 首先是关于题意的问题，之前有人向我提出题意不清，对于y<w的情况，没有说明该如何处理，但是在咨询了其他几个小伙伴之后，我决定还是不修改题面了，因为题中已经说明了是“机器每次开启的瞬间”，也就是说机器关闭之后w就会清零。我不大清楚是否有人因为这个坑点而被hack或者fst了，如果有的话，对此我只能表示遗憾。 因为数据范围很小，所以我们可以手动模拟，枚举每个小球弹出的时刻，再特判一下机器的关闭情况就可以了。实际处理起来的话或许有些蛋疼，但是，只要细心一点并且耐心一点，都是能够AC的。 另外一种解法就是推公式，我们发现，在机器每次开启的时间，都有x/w+1个小球被弹出（无论w是否整除x），假设这个数目为a，那么每弹出a个小球就需要花费x+y的时间，那么，第n个小球弹出的时刻就是(n-1)/a*(x+y)+(n-1)%a*w。要注意的是，这里需要用(n-1)%a*w，因为题中求的是第n个小球弹出的时刻等于是弹出n-1个小球所花费的时间，然而，只要测试一下样例就能注意到这一点了。 ## 1001 Victor and World 部分人可能对这道题的题面有点熟悉，其实这道题的标题本来叫做Victor and Around the World的，但是因为太长了所以就省略了两个单词。当然，这道题与POI 2014的那道Around the World其实没有任何关系。 我们首先需要预处理出任意两个国家之间的最短距离，因为数据范围很小，所以直接用Floyd就行了。之后，我们用f[S][i]表示访问国家的情况为S，当前最后访问的一个国家是i所需要的最小总油量，其中，S的二进制表示记录了访问国家的情况，S在二进制表示下的第i位（不管是从左往右还是从右往左都可以）如果是1则表示第i个国家被访问过了，否则表示第i个国家没有被访问过，那么f[S|(1<<i)][i]=min(f[S][j]+f[i][j])，其中i和j满足S&(1<<j)=1且S&(1<<i)=0。最开始时，除了f[1][1]是0，其他情况都是无穷大，之后先枚举S，再枚举i（我验题的时候因为这里搞反结果WA了），那么最终的答案就是min(f[(1<<n)-1][i]+f[i][1])，其中i$\in$ [2,n]。总复杂度为$O(n^3+n^2*2^n)$。 ## 1002 Victor and Toys 首先分母就是$C(m,3)$，考虑如何计算分子。 注意到期望的独立性，我们可以首先用$O(n+m)$的时间利用差分前缀和预处理出每个点被几个区间覆盖，假设第$i$个点被$s_i$个区间所覆盖，那么第$i$个点对分子的贡献即为$w_i\times C(s_i,3)$，注意不要爆long long。 ## 1003 Victor and Proposition 这是一道图论题。其中，命题与命题之间的关系我们可以看成边，如果A命题是B命题的充分条件，那么我们就可以从A向B连一条有向边，同理，如果B是A的充分条件，那么就从B向A连一条有向边。那么如果两个命题i,j互为充要条件，那么i和j就会属于同一个强连通分量，所以，这道题就变成了求强连通分量的题目。强连通分量有两种求法，分别是Kosaraju算法和Tarjan算法，在这里我就不详细介绍了。这道题的关键实际上在于建图。 首先，题中给出了一个以1号结点为根的树形结构，我们在构图的过程中，要将结点i和以xi为根的子树中与xi深度差不超过di的结点连一条有向边。但是，结点最多有十万个，如果直接连的话肯定是会超时的，所以需要一些黑科技进行优化。我们要用线段树来优化建图。对于每个结点，我们都需要用一棵线段树来维护其子树中深度为i的结点有哪些，那么，连边的时候，我们只需要将结点i往xi的线段树中，dep[x_i]到dep[x_i]+d_i的范围内的所有结点连一条边即可，既然已经建了线段树，如果线段树上每个结点往其子节点都连一条边，那么我们只要将结点i与对应线段树中[dep[x_i],dep[x_i]+d_i]范围内的结点连一条边。但是这样一来，建图的速度反而变慢了，没有关系，我们可以进行线段树合并。首先，遍历整个树，对于树上的叶子结点，我们都建立一棵线段树，之后，在返回的过程中，每个结点对应的线段树都是其所有子结点线段树合并的结果，这样一来，建图的复杂度就变成$O(n\log n)$了。 ## 1004 Victor and String 这道题是这场比赛一开始就定下的一道题，虽然感觉AC人数可能不是很多，但VictorWonder还是毅然决然地拿了出来。 这道题的题意是简单的，而且，我相信没有操作一的话，有一部分人应该会做。操作三实际上就是查询有多少本质不同的回文串，在添加字符的时候用manacher处理一下就差不多了，操作四的话可能要麻烦一点，打个后缀自动机应该就差不多了（本人也没有试验过，所以如果不行的话就当我口胡好了）。但是，我们还有另外一种选择，那就是回文自动机（我更习惯叫它回文树）。在这里，我假设大家都了解回文自动机的构建方法（如有不懂请自行百度），那么本质不同的回文串数目就是回文自动机上结点的总数-2，因为初始化的时候初始化了0结点和-1结点。至于询问四，我们则需要额外维护一个变量depth，对于一个结点i，depth[i]表示的是，沿着结点i的后缀链走到0结点的距离，那么每次新增加一个字符，假设此时代表最长回文后缀的结点为x，那么答案就加上depth[x]。 然而，现在比较麻烦的是，多了向字符串的前端增加一个字符的操作，但实际上，并没有加大多少难度。 我们首先定义后缀结点是代表当前字符串最长回文后缀的那个结点，前缀结点是代表当前字符串最长回文前缀的结点，同理，我们定义一个结点x的后缀链指向的是结点x所代表回文串的最长回文后缀，定义结点x的前缀链指向的是结点x所代表回文串的最长回文前缀。往当前字符串的后端增加一个字符，我们只需要沿着后缀结点的后缀链走下去寻找到符合要求的位置再进行更新即可。那么，往当前字符串的前端增加一个字符也是类似，我们只要沿着前缀结点的前缀链走下去就行了。 在这个时候，或许有人已经发现了一个细节，那就是前缀链是完全不需要的，因为回文自动机上每个结点所代表的都是回文串，那么其最长回文前缀和最长回文后缀都是相同的，所以一个结点前缀链指向的结点和后缀链指向的结点是相同的，我们完全不需要前缀链，只需要记录前缀结点和后缀结点就行了。需要注意的是，如果新增加一个字符之后，使得当前串就是回文串，那么需要同时更新前缀结点和后缀结点。 另外，在新增字符的时候，我们需要沿着后缀链寻找符合要求的位置，在这个过程中，我们需要在当前字符串中进行查找，因此，我们必须要记录下整个字符串，我的做法是用一个长度为2n的序列进行储存，以n这个位置为起始位置，用L和R来记录字符串两端所处的下标，那么处理起来就方便了。 最后，虽然看起来好像有些繁琐，实际上在经过这样的扩展之后，回文自动机的复杂度并没有改变。往前加字符和往后加字符都需要写特定的函数，但只要复制粘贴再修改一下就行了。 一些坑点：pretest是随机的小数据，而最终的数据都是人工构造的大数据，构造方法是将一个回文串翻倍再翻倍。还有一个点是全部都是a的，所有回文串的数目是超出int范围的，需要注意。

本场题意出现了一些问题...在此向大家道歉.. ## 1000 Zball in Tina Town 出题人:wuzhuangtai00 这题就是求 $(n-1)!~~mod~~n$ 如果$n$为合数，显然答案为0. 如果$n$为素数，那么由威尔逊定理可得答案为 $n-1$ 注意有个trick为 $n$ = 4. ## 1001 Infoplane in Tina Town 出题人:zball 给出一个置换，求它的循环长度。数据范围 $3\times 10^6$。 其实没有什么好说的，就分解成循环求长度的最小公倍数就好了。对于这个模数要用unsigned int存，这个最小公倍数的求法不能用欧几里得，直接每次分解质因数，用线性筛预处理一下就好了。 时间复杂度:$O(n)$.分析 对于第一部分寻找循环每个点都恰好遍历一次,$O(n)$; 第二部分分解质因数，时间复杂度为 $ \sum_{i=1}^kf(|p_k|)$. $f=O(\log{n})$,$\sum_{i=1}^k|p_k|=n$. 显然有$f(|p_k|)\le p_k$,所以这部分时间复杂度$O(n)$. 第三部分快速幂加乘法同样分析. ## 1002 Falsyta in Tina Town 出题人:fsf $$x_n=\frac{(k^n-1)b}{k-1}+k^nx_0$$ $$\frac{(k^n-1)((k-1)x_0+b)}{k-1}\equiv 0\ mod\ p$$ 注意到$((k-1)x_0+b)/(k-1)$与$n$无关。 将$((k-1)x_0+b)/(k-1)p$约分，令分母为$q=(k-1)p/d$。 下面即要求解$k^n\equiv 1\ mod\ q$。 注意到若$q>10^9+9$，则我们可以很容易地得到一个不大于$10^9+9$的因子，接下来只需要将$q$拆成两部分分别质因子分解即可。 接下来一个显然的事情是，令答案为$ans$，则对于任何$k^n\equiv 1\ (mod\ q)$，有$ans|n$。 我们令 $$\phi(q)=\prod_{i=1}^lf_i^{g_i}$$ 那么我们枚举在每个$f_i$在最终答案中的次数即可。 暴力分解质因子的复杂度是$O(\sqrt{p})$，后一部分的复杂度是$O(log^2n)$的（然而需要快速乘还要多个log）。 注意判断特殊情形。 ## 1003 Trie in Tina Town 出题人:zball 我们可以先假设给出的是一个字符串.裸上的复杂度非常高,是$O\left(n^3\right)$的.我们显然可以用manacher算法计算,这样它的复杂度就降到$O\left(n\right)$了. 然而对于推广的问题,manacher其实还是可以做的(比较麻烦).我们只需要对于Trie的根节点DFS一下,顺便维护当前DFS下来的字符串,每次罗干到叶子节点统计一下就可以了,时间复杂度是$O(n\log{n})$,但是为了不让伪正解过,大概是卡掉了. 这里介绍一种处理回文串的利器(大概很多人也都会了),回文树.回文树可以在$O(n)$的时间内找出所有本质不同的回文串,而且它是一种在线算法. 类似KMP自动机,我们可以维护一个fail指针指向它的最长后(前)缀回文串,这样我们就可以实现实时更新了.这个匹配过程和KMP非常类似,只是同时在两端添加字符而已.对于回文树来说,fail指针一旦建好是不会变的.证明可以考虑回文串的性质:它的前缀必定已经处理过了. 这样我们就只需要在dfs时实时更新字符串和next指针,这个可以$O(1)$做到,而将字符添加进回文树内也是摊还$O(1)$的,证明可以仿造KMP.这样我们就可以建好一棵Trie的回文树了. 对于一棵回文树,显然可以在$O(n)$(n为节点数)的时间内统计出所有回文子串的长度之和,具体做法只需要对于它的每一个节点开一个cnt域,每访问一次cnt加一,最后对于加入节点的顺序反过来操作把fail指针所指的回文串cnt加上自己的cnt($O(1)$),这样就可以处理出每个回文子串出现的次数了.对于每个节点(除节点-1外)把这个cnt乘上他们长度的值的和就是回文串总长度了. 最后简要分析一下复杂度:构造回文树$O(n)$,统计$O(n)$,加起来还是$O(n)$的.至此我们已经完美解决这个问题了.加上读入优化标程未超过100行,大小不到2KB. 其实这道题可以做到动态查询，只要用LCT来维护回文树(的fail树)。但是窝们是送温暖出题人，就不要求大家写LCT啦~ ## 1004 Piano in Tina Town 这道题目就是要求$\sum \prod_{i=1}^{m} cos(k_iX)$并且$\sum_{i=1}^{m} k_i=n$ 这是一道比较有意思的数学题.. 我们设$f(n,m)$表示$\sum \prod_{i=1}^{m} cos(k_iX)$且$\sum_{i=1}^{m} k_i=n$ 再设$g(n,m)$表示$\sum \prod_{i=1}^{m-1} cos(k_iX)sin(k_mX)$且$\sum_{i=1}^{m} k_i=n$ $m=1$ $f(n,m)=f(n-1,m)\times cosX-g(n-1,m)\times sinX $ $g(n,m)=g(n-1,m)\times cosX+f(n-1,m)\times sin X$ $m>1$ $f(n,m)=f(n-1,m-1) \times cos X+f(n-1,m)\times cosX-g(n-1,m)\times sinX$ $g(n,m)=f(n-1,m-1) \times sin X+g(n-1,m)\times cosX+f(n-1,m)\times sin X$ 接下来我们只要用矩阵乘法加速一下这个递推就好了，时间复杂度$O(m^3n)$

不好意思，本场题意bug太多。。。出题人给大家道歉了。。 ## 1001 Distribution money 这题没什么好说的，排个序直接模拟一下就好了 ## 1002 Run 地球人都知道整点是不能构成正五边形和正三边形和正六边形的，所以只需暴力枚举四个点判断是否是正四边形即可。假如你不是地球人，那么即使暴力枚举正三边形和稍微不那么暴力地找正五边形和正六边形也是可以通过的（反正找不到）。 ## 1003 The mook jong 令f[i]为最后一个木人桩摆放在i位置的方案，令s[i]为f[i]的前缀和。很容易就能想到f[i]=s[i-3]+1,s[i]=s[i-1]+f[i],而s[n]即是所求答案。本题唯一一个值得注意的点就是当n接近60时会爆int。 ## 1004 digger 对于求“高山脉”长度，可以利用线段树。树节点中保存左高度连续长度，左高度连续区间的高度，左高度连续区间的状态（即是否高于第一个高度不同的山），右高度连续长度，右高度连续区间的高度，右高度连续区间的状态，每段区间内的“高山脉”数量。每次更新时更新高度即可，在pushup过程中去计算新产生的“高山脉”。写起来难度不是很大，然后对于n很大且必须在线做这个条件只需对于线段树动态建立节点去维护即可 ## 1005 Bribery 此题中，收买一个长官的价值是该长官自己的一个值加上在树中到主人公的距离，这个值在每次询问中都是变化的，如果直接依赖这个值来计算的话，是非常困难的。所以处理一下这个值，收买一个长官的价值改成该长官自身的值减去该长官在树中的深度，然后在最后的答案中再加上主人公的深度即可，此题中把每个长官的价值更新成该长官与该长官以上的长官的价值的最小值是有利于计算的。 然后对于一个询问。很显然val(p,(l,r))=val(p,(1,r))-val(p,(1,l-1))。那么只需要离线处理，一个一个计算出来，然后利用树链剖分去维护总价值。每隔询问拆分成两个排序后放在队列中，每次触发后计算。 具体的更新过程是：每次更新一个点。就把这个点到树根的这一段路径上每个点的sum加上一个价值，同时要记录每一段区间被更新了几次。这一步利用线段树处理。 询问过程：从这个点开始向上询问，每次询问到线段树中的一段就把这里的sum-已经计过的次数*这一段的最小长官贿赂价值 统计进答案。

## 1001 Untitled 对于一组可能的答案$c$，如果先对一个觉小的$c_i$取模，再对一个较大的$c_j$取模，那么这个较大的$c_j$肯定是没有用的。因此最终的答案序列中的$c$肯定是不增的。那么就枚举选哪些数字，并从大到小取模看看结果是否是$0$就可以了。时间复杂度$O(2^n)$. ## 1002 Three Palindromes 对原串前缀和后缀作一个01标记pre[i],suf[i]表示1-i和i-n能否能形成回文。记以i为中心的回文半径为r(i)。 这些都可以在O(N)时间内求出。也可以使用Hash+二分等方法O(NlogN)内求出。 我们考虑中间一个回文串的位置，不妨设它是奇数长度（偶数类似）。 那么问题变成了求一个i和d使得1<=d<=r(i)且pre[i-d]和suf[i+d]为真。 枚举i，实际上就是问pre[i-r(i)..i-1]和suf[i+1..i+r(i)]取反后 这两段有没有一个位置两者均为1，也就是and后不为0，暴力压位即可。 总时间复杂度为$O(N^2/32)$。 ## 1003 Gcd and Lcm 详见推导。 $Ans=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n [(i,j),(k,l)]$ 不妨先考虑下式 $r(n,d)=\sum_{i=1}^n\sum_{j=1}^n [(i,j)=d] $ 令f(n)=r(n,1)，则r(n,d)可以等价于f(n/d)。 $f(n)=sum_{i=1}^{n}\sum_{j=1}^{n}$ e[(i,j)] (e为单位函数) $ = sum_{d=1}^{n} u(d) [n/d]^{2} $ 令d1=(i,j),d2=(k,l)那么不难得出 $Ans=\sum_{d1=1}^n\sum_{d2=1}^n [d1,d2] f(n/d1)f(n/d2)$ 令p=(d1,d2)则 $\sum_{p=1}^n\sum_{d1=1}^{n/p}\sum_{d2=1}^{n/p} p*d1*d2*f(n/p/d1)*f(n/p/d2) e((d1,d2))$ $\sum_{p=1}^n\sum_{q=1}^{n/p}\sum_{d1=1}^{n/p/q}\sum_{d2=1}^{n/p/q} u(q)*p*q*q*d1*d2*f(n/q/d1)*f(n/q/d2)$ 令$T=p*q$ 令$g(n)=\sum_{d=1}^{n} u(d) f(n/d)^2 $ $ s(n)=\sum_{d|n} u(d)*d^2*(n/d) $ 则化简得$Ans=\sum_{T=1}^n s(T)*g(n/T)$ s为积性函数，可以O(N)时间内预处理出1-N的所有函数值。 可惜的是g并非积性函数，但我们亦可以在O(sqrt(N))的时间求出g(N)。 在最后的答案中我们对g(n/T)的每种取值均算一遍即可，注意多组数据时记忆化。 ## 1004 Dynamic Cactus 考虑离线，并对仙人掌进行分治。 类似于树的点分，每次的分治中心无非是两种情况：节点或者环。 这样每次新建节点时就去更新过分治中心的答案。 为了保证更新答案的两个点分属不同子树： 对于普通节点，只要维护最大和在另一子树的次大距离即可；对于环，由于环上的距离计算存在序的问题以及两种走法，我们可以在环上任选一个开始位置，需要分前后两部分更新和询问，可以用四个BIT维护前缀后缀和正负符号。 总时间复杂度为$O(NlogNlogN)$。