icpc训练营题选做

很久之前就想开这个坑了（

计划写hdu多校，ptz营，nowcoder之类的。但是比较咕啊。可能上了带学也会做吧，但是先上个带学再说/fendou

很多是胡的，不保证正确性，仅供参考。欢迎您来交流讨论，可以在评论区给我留言/se

hdu多校

这些题可以在vj上看到题面，但是并不能提交。讲道理胡题可以锻炼思维的精确度，也就是说你想出来基本是对的?（狡辩

hduoj好像马上就要复活了。如果你想写一遍所有的题，请放弃，因为这将是巨大的时间浪费。

2009

刚开始做你会觉得很水，但是后面几场难度还是有一点的（

D1

A. A sequence of numbers

签到题。如果是等差数列，那么两个差分是一样的，否则必然不一样。

B. Building Block

签到题。并查集。

C. Swap

不需要最小化步数/jy

考虑从行来看，每一行的内容不变，它们只是被换来换去，并且在列上重排了而已。那么如果某一行没有1，或者某一列没有1，必然完蛋了。

否则，我们可以考虑找到一个列的排列$p$，使得$i$行$p_i$列都是1，那么只需要按照$p$的逆来换就行了。可是这个只做了列的交换。为了证明必要性(或者你会认为它是充分性?)，我们考虑如果现在同时允许行列的交换，得到了一个对角线的1，那么我们换两行，再换它们对应的两列，对角线上还是全是1。同时显然行列的交换是独立的，那么我们这样就可以用列的交换代替行的交换。

那么接下来问题就很简单了，我们只需要在这里面找一个排列。但是想了想发现这个问题并不是很简单（

建一个图，有$n$个数，每行连到它有的数，那么这就是一个匹配。跑网络流即可。

D. Permutation

状压dp。

E. Pusher

这个游戏好像已经因为flash player的退休而退出历史舞台了/ll

完全没看懂题。据说搜就行了，那就搜就行了吧。

F. Dogs

01bfs。

G. The widest road

求出两边的凸壳，然后如果有交那就完蛋了，否则双指针卡一卡。

H. The Euler function

签到题，直接线筛。那个时候毒假筛还没普及吗?

I. Wireless password

先建一个acam再说。然后你发现直接dp就行了，那么为什么这个题数据范围这么小?

D2

A. The troubles of lmy

我们先找到一个具有某种特征的边，比如最短的，然后把它们对齐即可。

B. The Evaluation of Determinant

板子。为什么hdu多校还有板子?可能这是上古场所以很水吧（

C. Lamp

这个看起来是要挑战npc。

然后又读了一遍题，你发现一个开关最多可以控制两个灯，也就是说一个开关只会在两个灯的表达式中出现。但是这还不是一个2-sat。

考虑建个图，容易想到灯是点而开关是边。如果一个开关只控制一个灯，那么可以把这个开关和这个灯直接删掉，此时与这个灯相连的别的开关也只控制一个灯了，最后整个连通块都会删掉，也就是说如果一个连通块有一个开关只控制一个灯那就赢麻了。

然后容易想到猜测连通块边数够的时候总是不会出问题。考虑边数够就必然有环，我们保留一个环，从环出发找随便一棵dfs树，然后把树的部分删一度点删空，环上的就转一圈即可。所以只有连通块是一棵树的时候会无解。

D. Lawrence

直接dp就过了。

这看起来很凸，于是可以尝试wqs二分之后斜率优化。但是我懒得试（

E. Matrix Swapping II

这会只能交换两列了。看起来好像更困难了（

我们枚举一个行的区间，然后求出有多少列包含这个行的区间，把它们换到一起就彳亍了。枚举区间的一个端点，这个东西是关于另一个端点单调的，于是我们直接扫过去就行了。

F. Plants VS Zombies

让我想起一个经典牛逼题（

签到题，直接贪就行了。

G. Snail’s trouble

如果你看过具体数学的哪怕一点，就可以开始猜答案了（

实际上好像打表即可。

H. WuKong

交的肯定是连续的一段，于是枚举这一段，然后看它是不是有可能在最短路上，跑四遍Dij即可。

I. Girl Friend II

直接dp。难度在于读题。

D3

A. Operating system

经典问题。贪心踢掉下一次出现最晚的即可。

B. Traversal

线段树优化dp。

C. Calculation

快速幂。

D. Cow Sorting

注意到交换对两个牛是独立的，也就是说它们的贡献可以拆开，并且冒泡排序对每个元素都达到了交换次数下界，于是直接BiT求每个数被换了多少次即可。

E. Game

看起来它是越改越小了。

每个位置是独立的。

考虑能否直接把它变成nim。然而这是一个不平等博弈。

不过没有关系，你发现数的大小只有区区$15$，于是我们可以直接爆力搞出状态之间的转移。然后怎么才能合并这些堆?看起来sg定理在这里不起作用，于是我们尝试使用超现实数。看起来我需要尝试复习超现实数?

以前尝试过写超现实数入门，但是失败了。现在就去写/fn

这题有两个人交了，全wa了，网上还没有题解/jy

然后这个题应该就是直接做就彳亍了。

F. Self-Replicating Numbers

如果是输出所有的，那看来个数非常少。

考虑这个写个式子就是$x^2\bmod{b^n}=x$，那么也就是$x(x-1)\bmod{b^n}=0\Leftrightarrow b^n\mid x(x-1)$，那么$x,x-1$中$b$的幂次应该足够多($0$包含每个素数的任意次)。注意到如果$p\mid x$，那么必然有$p\not\mid x-1$，于是我们枚举$b$的每个素因数出现在$x$还是$x-1$中，然后上一个crt即可。比如样例中有$2^4\mid 9376,5^4\mid 9375$。

考虑了一下最后crt出来是膜$b^n$，所以每种情况下只有一个解，最后解的个数有上界$2^{\omega(b)}$。

G. Visible Trees

能看到等价于互质，直接莫反。

H. Chinese Rings

考虑这个式子会是什么。设答案是$f(n)$。

首先我们肯定要拿下第$n$个环，于是我们必然需要让$n-1$在上面，而$1,…,n-2$全都拿掉了。这是$f(n-2)$。

拿完第$n$个之后，只剩下$n-1$在上面，这个我们设只拿下$n-1$的步数是$g(n-1)$。答案是$f(n)=f(n-2)+g(n-1)+1$。

考虑$g(n)$，我们要把$n-1$放上去，然后把$n$拿下来，然后把$n-1$拿下来。为了把$n-1$放上去，我们需要把$n-2$放上去，然后把$n-1$放上去，然后把$n-2$拿下来。为了把$n-1$拿下来，看起来这是一样的，于是有$g(n)=2g(n-1)+1$。矩阵快速幂即可。

然后据说它等价于$f(n)=f(n-1)+2f(n-2)+1$。

I. I Will Win

一眼看上去像是签到题?

然而会让人有点迷惑，因为考虑0 0(但是实际上0 0不会出现，它表示结束)，就可以把很多猜的结论hack掉了。于是还是得强行计算。

两人分别赢了$a,b$场下胜率是$p$的概率应该与胜率是$p$下两人分别赢$a,b$场的概率成正比，那么根据二项分布，这个概率是$\binom{a+b}{a}p^a(1-p)^b$，而$\binom{a+b}{a}$是常数，于是胜率是$p$的概率就是$\displaystyle\frac{p^a(1-p)^b}{\int_0^1 x^a(1-x)^b\ \mathrm{d}x}$，于是答案就是$\displaystyle\frac{\int_0^1 p^{a+1}(1-p)^{b}\ \mathrm{d}p}{\int_0^1 x^a(1-x)^b\ \mathrm{d}x}$。这里随便找了一个$x$当变量名?

这俩积分咋算?扔进wolfram alpha(然而它比较拉，得把两个积分分开算再合起来，不然跑不出来)，然后它就是

于是答案就是$\frac{m+1}{n+2}$。看起来还是挺优美的?

这个东西看起来是经典结论，那个积分被称为beta函数，它和gamma函数就是有那个关系，如果你想要了解更多可以百度一下。

J. Coins

whuacmers指的是whu的acmer，这个词造的可真是太离谱了（

模板 背包。

D4

A. Beans

直接dp。

B. Repository

直接多串sam。

也可以对查询建acam。

C. Binary String

长度最小，长度相同字典序最小，看起来就是比较这个数的大小。

不过这个没啥用。考虑数位dp，我们dp出最小长度，再从高往低找最小字典序就好了。

D. Number Cutting Game

签到题。

看起来很像是搜。感觉上状态数实在是很少，于是搜应该就行了（

E. For Kisses

在题目的最前面加上一句话 你是一名骨科医生。

直接状压dp即可。想了半天怎么搜（

F. Load Balancing

上来就说这个是np-hard可还行（

讲道理，背包也是np-hard的。

答案在1e6级别，于是spj那个1e3看起来像是根号?也可能只是一个随便加上去的常数。

感觉上直接退火就过了，但是感觉总是会骗人的（

考虑先生成一个很优的解，然后随机调整。我们从大到小加入所有任务，每次把当前这个任务扔到时间最短的机器上。然后我就没有什么想法了（

G. Lode Runner

看不懂题/cy

据说是直接最短路。

H. KiKi’s K-Number

set。

I. Assignment

最大权匹配。

D5

A. Central Meridian Number

注意到$a,b$都可以对$n$取膜，所以打表就行了。

B. Fibonacci Check-up

这个公式看起来很眼熟，我们打个表观察一下它是啥。

打出不爆int的项。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
1
3
8
21
55
144
377
987
2584
6765
17711
46368
121393
317811
832040
2178309
5702887
14930352
39088169
102334155
267914296
701408733
1836311903

扔进oeis，这是$f(2n)$，$f$是fib数。实际上肉眼也可以看出来。

如何解释?组合意义天地灭，考虑fib数的ogf $\frac{x}{1-x-x^2}$，但是这个不能表示对它做那个带组合数系数的前缀和，这需要egf。

关于fib数的egf，我们有微分方程$F^{\prime\prime}-F^\prime-F=0$，这个实在是懒得解，我们直接卷上$e^z$得到$e^zF^{\prime\prime}-e^zF^\prime-e^zF=0$。我们希望把它凑成$e^zF$的一个微分方程，也就是说求导的时候都是对$e^zF$求导，而不是只对$F$求导。

我们先尝试强行做这个事情。

给$e^zF^{\prime\prime}$凑一个$e^zF+2e^zF^\prime$，我们得到$(e^zF)^{\prime\prime}-e^zF^\prime-e^zF=e^zF+2e^zF^\prime$，移项得$(e^zF)^{\prime\prime}-3e^zF^\prime-2e^zF=0$。

给$-3e^zF^\prime$凑一个$-3e^zF$，我们得到$(e^zF)^{\prime\prime}-3(e^zF)^\prime-2e^zF=-3e^zF$，化简得$(e^zF)^{\prime\prime}-3(e^zF)^\prime+e^zF=0$，于是我们知道它的递归式就是$a_n=3a_{n-1}-a_{n-2}$。同时斐波那契数的递归式是$f_{2n}=f_{2n-1}+f_{2n-2}=2f_{2n-2}+f_{2n-3}=3f_{2n-2}-f_{2n-4}$，所以它俩确实是一样的。你也可以用这个方法直接推式子（

C. Find Its Place

看起来非常简单，我们爆力给边上的几列强行解方程，然后中间的部分可能的最大行数将会非常小，比如爆力边上10列就可以给中间开十次根号，于是继续爆力即可。

D. Mirror and Light

计算几何/jy

直接做。

E. Oil on the Mars

题意有点不明确，说的大概是，有一个棋盘，你可以选一些连在一起的格子，使得它的边界看起来是单调的，也就是最左边的点到最上面的点看起来是单调的，最上面的点到最右边的点看起来是单调的这样的。

考虑直接dp，设$dp(i,j,l,r,0/1,0/1)$表示走到$i$行，选了$j$个，这一行选了$[l,r]$这个区间，左边接下来应该往左/往右，右边接下来应该往右/往左这样的，然后它的复杂度是$O(n^5)$，如果感觉空间危险，把$i$滚一下变成$n^4$就好了。

F. Phalanx

直接dp，可以用二分hash来转移，就$n^2\log n$了。

考虑能不能做到$n^2$。我们要查询一个行的区间和一个列的区间的lcp，这个看起来很像是z algo做的事情，但是实际上它并不是（

考虑先把所有的行和列拼成一个串，现在问题是有一个串，每次查两个子串的lcp，这个sa就做掉了，使用sais和四毛子st表，复杂度是严格$O(n^2)$。

G. Regroup

模板 并查集。

H. Stools

直接dp。

I. The Crazy O2jamer

二分答案，然后问题变成这个过程分成了若干段，你要给每一段分配一些note，然后段之间会爆一个miss。问题在于如何分配good和cool。

打cool和good的顺序区别不是特别大，我们可以钦点每一段先打cool再打good，这样就不会出问题。

贪心地，只有两种可能的方案，也就是把cool尽可能塞在一起，或者平均分配。事实证明塞在一起是对的，感性理解就是cool占一个位置可以得到两倍于good的jam加成。

D6

A. FunnyXEN

看起来还挺有趣的，相当于是说求$1,…,2n$在整除意义下的最长反链和不包含于任何最长反链的元素。

然而想了一下还是过分简单。最长反链长度等于最小链覆盖，所以看起来就是选所有的素数了。然后如果一个数包含两个素因数，选了它这两个素数都没法选了，所以它就不能被选，然后$1$总是不能被选，然后就是求素数幂个数了，然后这玩意是不是还可以加强到1e11上min25筛（

B. Tree Fence

看起来比A更有趣。

考虑直接对选的桩子dp，也就是从左往右走，记录上凸壳和下凸壳的走向和最右的点，转移需要三角形数点，可以差分成三个 原点和两个桩子的三角形 数点，然后我们就爆力预处理这个就行了，复杂度$O(nm^2)$。

C. Sum of Digits

直接dp，看起来只需要dp一遍就可以回答所有询问。

D. Dirt

直接最短路。

E. Repairman

走到的是一个区间，区间dp。

F. Two Mirrors

真实的计算几何。直接做。

G. Chinese Chess

这是一个二分图匹配，我们要找到其中必流的边。

看起来这是经典问题。做法是dinic，然后在残量网络上kosaraju，然后如果一条边满流，并且两个端点不在同一个scc，那么它必流。如果两个端点在同一个scc，说明可以沿着某条路径把它换掉，于是它不必流。

H. Network

看起来很有意思。

注意题目中把很多个$2^n$写成了$2n$，并且时限足有10s，所以复杂度可能是$2^{3n}$这样的。

贡献方式看起来是，用的少的那一种要付钱，用的多的免费。

注意到这个pair贡献是假的，它对两个人其实是独立的，所以我们可以预处理每个人在每个祖先处的贡献。

然后考虑dp，我们决策一个人的时候，把他到根的链上每个点是A多还是B多记入状态。但是这样会出问题，因为我们dp过去就dp过去了，不能保证钦定了A多最后就是A多这样的。

考虑了一下子树为状态的，直觉上感觉不行，是因为它可能不能保证 不管这个点A多还是B多，子树总是采用局部最优策略。考虑如果这个点A多，它的儿子也是A多，那么可能有一个叶子翻转的代价很大，而只考虑儿子的子树翻它不划算，考虑上这个点翻它就划算了(在这个点不翻它的代价更大)。

考虑一个离奇做法，我们每次找到一个点，如果翻了可以使答案减小那就翻，啥也不翻的话答案不会超过5e8所以最多翻这么多次，树高是10所以容易找到哪里可以翻，但是我不会证单谷。

切队长之言可谓切中了肯綮，考虑我们把两个dp拼起来，同时记录到根链上的状态和这个点子树有多少个A，然后转移是背包，复杂度是树卷积，多了一维所以是$O(4^nn)$。

这个故事告诉我们，如果你的两个dp状态设计都有不能考虑到的问题，不妨把它们拼起来。或者说想到一个要记的东西的时候，就总是记它直到你写出一个可以优化的dp，然后在优化的时候删掉多余的信息，除非你确定有别的更简单的东西可以替代它，或者确定记这个东西不会有任何效果。

I. Robot

看起来类似于 美食家，但是做法不是很一样。我们直接dp，然后分析复杂度，看起来是$O(mT)$，于是做完了。

J. Scales

平衡三进制。

K. Increasing Speed Limits

BiT优化dp。

D7

A. Top Shooter

一秒一个可真是恐怖啊/jk

贪心地，先打更低的。

B. “Base B”

直接做。先用B进制表示，如果有太小的，从高位退下来。

C. Birthday Toy

几分钟玩1e9个珠子/jy

考虑冲一个burnside。burnside指出，置换群作用下不同的染色个数等于每个置换作用下不变的颜色数量的平均值。这里置换只有1e9个，所以我们先枚举一个置换，对于转$i$下的置换，它确定了$\gcd(i,n)$个等价类，每个等价类颜色必须是一样的，于是问题变成有$\gcd(i,n)$个珠子排成的环，中间还有一个珠子，不考虑同构，相邻的必须不同的方案数，设为$f(\gcd(i,n))$好了。搞完这个，我们的问题就是对所有$n$的因数$d$求$f(d)$然后反演算贡献而已。

然后这个$f$看起来很不好算。现在我们要算$f(d)$。考虑中间的珠子相当于ban了一个颜色，然后考虑容斥，钦点$i$个间隔使得两边相同，这会产生$n-i$个连通块(钦点了$n-1$或$n$个都得到一个连通块)，于是方案数就是$\displaystyle\sum\limits_{i=0}^n\binom{n}{i}(-1)^i(k-1)^{n-i}+(-1)^n(k-2)=(k-2)^n+(-1)^{n}(k-2)$，后面那个是钦点$n$个的时候少算的。

另一个做法是矩阵快速幂优化dp。

然后复杂度就是$O(\sqrt{n}\log n)$了，可以光速幂再砍$\log$。不过不知道莫反的部分是啥复杂度?反正能做。

D. Special Prime

考虑如何判断一个数是不是特殊的。我们移过去变成$p=\frac{m^3-n^3}{n^2}=m\left(\frac{m}{n}\right)^2-n$，如果有一组$n,m$使得这个成立就彳亍了。然而这个看起来比较困难。

考虑$\frac{m^3-n^3}{n^2}=(m-n)(\frac{m^2}{n^2}+\frac{m}{n}+1)$。这个也失败了。

考虑$n^2(n+p)=m^3$。注意到如果$n^2(n+p)$是立方数，要么$n^2,n+p$都是立方数，要么$p\mid n$。然而设$n=kp$，那么$n^2(n+p)=k^2(k+1)p^3$，于是$k^2(k+1)=k^3+k^2$必须是立方数，然而$(k+1)^3=k^3+3k^2+3k+1>k^2$，于是它不可能是立方数。于是只可能$n^2,n+p$都是立方数，并且容易感觉到这个是充要的。

问题是能不能找到一个$n$使得$n^2,n+p$都是立方数。注意到$n^2$是立方数，当且仅当$n$是立方数，因为一个素因数的次数是否被$3$整除，不管乘上多少个$2$都不会影响。

问题是能不能找到一个$n$使得$n,n+p$都是立方数，也就是$p$是不是一个立方差。设$p=a^3-b^3=(a-b)(a^2+ab+b^2)$，注意到$a^2+ab+b^2\neq 1$，于是$a-b=1$，否则$p$就不是素数了。

设$p=(x+1)^3-x^3=3x^2+3x+1$，解二次方程即可。复杂度$O(1)$。这题是不是mo味道过于浓重了?

E. Continuous Digit

从高到低逐位确定这个数的大小。它的值看起来不超过1e19，于是数位dp将会非常快。

F. Neighbor Friend

我们直接按照这个关系建图，如果$a$到$b$的所有路径上存在别的点，那么$a,b$不可能挨着。如果不存在别的点，那么我们感觉上总可以找到一种方案让它俩挨着。

问题是求两点间的最长路，枚举起点，拓扑排序即可。

G. Paper Cutting Game

注意切一刀是同时切所有的纸/jy

模拟。

H. Largest Submatrix

枚举答案由哪个字符贡献，然后dp或者单调栈。

I. Memory Control

模拟。

D8

A. Another Snake

直接dp。

B. Bomb Game

注意到有 炸弹相撞会消失 的规则，于是我们似乎不能用sg定理了。

诶真的不能用吗?考虑两个同一位置的炸弹相当于没有，这是真的，因为后手可以模仿先手操作。于是我们可以把这个规则删去，答案是不变的。递推sg值即可。

C. Connections between cities

注意 no circle exists as well 说的是真的没有环，而不是可能没有环。板子。

D. DNA Sequence

第二类限制是一组里面两两不同，可以连个边。

为什么我会以为是要计数（

计数非常复杂，感觉上像是不弱于图着色，没法多项式时间做掉。这个问题相当于是有一些边，然后要做一个四染色，对相邻的还有一些要求。

观察一下这个相邻的要求，看起来是说相同的不能相邻，AC不能相邻，CG不能相邻，GT不能相邻，于是可能相邻的只有AG，AT，CT，这个形成了一条链，每一步只能往左或者往右走。我们枚举第一个，然后整个串可以用一个二进制数表示，于是状态数缩减成$2^n$了，但是这还是没啥用。

不妨假设第一位是A或者C，那么奇数位只能是A或者C，偶数位是G或者T，于是这看起来像一个2-sat了。直接建图跑即可。

怎么求2-sat方案数啊?

E. Ellipse, again and again

一开始看成Eclipse了，感觉很有诗意啊（

不过我可能一直以为eclipse是日落的意思了，实际上那是sunset，eclipse是日食/月食，也比喻权力/地位的丧失，也作动词表示使丧失。

算就行了。我不懂几何啊，但是我知道算肯定可以（

F. Florid Banner

rnm，每一行是独立的啊/fn，注意题面中说这些东西都不能转，也就是说只能横着摆。

直接dp即可，用hash table找一下合法的转移。

G. Great World of Goo

原题面写的很烂，并且据说有错误。转化之后是，二分图，有若干条特殊边，特殊边需要选至少一条，最大匹配计数，答案超过$2^{16}-1$则输出overflow!。

那这个是不是简简单单啊!我们跑一个最大匹配，然后开始搜交替路来扩展，用map支持 扩展到走过的状态就跳，搜够$2^{16}-1$种就溜。复杂度未知。

据说一个直接做法是，直接搜选哪些边，然后用dancing links维护。

H. HeHe

前面有一个 Self-Replicating Numbers 指出，$x^2\equiv x\pmod{n}$变换成$n\mid x(x-1)$，并且$x\perp x-1$，于是需要把$n$的素因数成两部分分别扔进$x$和$x-1$，然后通过乘上一些东西使得它俩差$1$。这是两条直线，所以只可能有一个解，而由于裴蜀定理必然有一个解，所以方案数就是$2^{\omega(n)}$。求和即可。

看起来可以做到$\tilde{O}(n^\frac{3}{5})$，也就是用因数个数函数$d$构造powerful number，然后问题变成算$d$的前缀和$S_d$在$n$的基本和组处的值。基本和组就是$\lfloor\frac{n}{i}\rfloor$形成的集合，它只有$O(\sqrt{n})$个元素。

我们有方法在$O(n^\frac{1}{3}\log n)$内算$S_d$在$n$处的值，参见 https://www.luogu.com.cn/problem/SP26073 (divcnt1)。

考虑对于大的部分上这个，小的部分打表，积分可以得到大的部分的复杂度，解个方程得到打表长度为$\tilde{\Theta}(n^\frac{3}{5})$时最优，复杂度是$\tilde{O}(n^\frac{3}{5})$。

可能有复杂度更低的做法，不过最practical的还是直接上$O(n^\frac{2}{3})$的爆力，也就是把sb树那个东西换成整除分块。

I. Ingredient

求lcm。

J. Jack’s struggle

直接dp。5s慌什么!

D9

A. The k-th String sequence

在子序列自动机上逐位确定。

B. kebab

不能分成实数，但是我们也不需要分成实数，所以当成可以分成实数做也是对的。

先烤截止时间更近的。

C. Orefield Design

看起来是说，选五个点，要包含五种不同的矿物，然后最小化斯坦呐树边权和。直接dp，设$dp(u,S)$表示$u$子树内选了$S$内的矿物的最小斯坦呐树边权和，转移直接做，复杂度是$O(3^5n)$。

D. Drr1 Numbers

枚举位数$k$和最后一位$c$，问题变成有多少个$k-1$位数$x$满足$10x+c\mid 10^{k-1}c+x$。这个看起来还挺困难的（

进一步注意到$\frac{10^{k-1}c+x}{10x+c}$不超过$9$，因为极端情况下第一位是$1$而最后一位是$9$。于是我们进一步枚举这个值，设为$d$。

此时得到$d(10x+c)=10^{k-1}c+x$，解得$x=\frac{(10^{k-1}+d)c}{10d-1}$，于是直接就把这个数求出来了。要求它膜$100000$的值，注意到分母只可能是$9,19,29,39,49,59,69,79,89$，它们都与$100000$互素，于是可以exgcd求逆。

E. Lou 1 Zhuang

显然必然是分成若干个$2$和$3$的乘积。讨论一下是尽可能分$3$因为$2^3<3^2$，分到只剩$O(1)$再打个表看看就彳亍了。

F. Watering Hole

把挖井看成连向一个虚点，跑一个mst，然后对于每条加进来的边，在mst上尝试替换形成的环的最大边，使用fib堆优化prim和四毛子lca，复杂度$O(n\log n+m+p)$。

G. Check Corners

矩形$\max$是经典分治扫描线。复杂度忘了，猜一手$O((nm+q)\log^2 n)$（

gp of zhejiang里面有个题指出矩形加矩形$\max$可以做到一个$\log$，方法是让线段树支持清空(直接在根上打标记)，然后每次扫分治树的一层。

H. Without Zero

这玩意就是九进制。

I. Longest Repeated subsequence

请注意subsequence应为substring/jy，这玩意谁能看出来/jy

考虑使用后缀树，我们直接在后缀树上模拟。如果一个点的子树中还有至少$k$个叶子，并且可以从中选出$k$个不相撞的串(也就是说如果这个点深度是$d$，可以选出$k$个叶子对应的后缀位置两两差$\geq d$)，这个点就合法，然后只需要找最深的合法点。如何判断 不相撞?感觉并不好做。

考虑二分答案，然后这个点的深度就是固定的了，然后我们找到所有这样的点，它们子树中叶子个数和是$O(n)$的，于是直接贪心选取即可。复杂度$O(n\log n)$。

D10

A. addHP

dp，设$dp(i,j)$表示$i$时刻刚刚加上了一些血，现在血量为$j$，之前的最小血量是多少。转移枚举上一次加上血的时间，然后中间是个前缀和。但是转移量很大，看起来复杂度是$O(nmv)$，不太行啊。

最小值最大，考虑二分答案$d$，然后状态变成$dp(i,j)=0/1$这样的。注意到固定$i$，$dp(i,j)=1$的$j$只有最大的那个有用，于是维度交换，设$dp(i)$表示$i$时刻刚刚加上了一些血，最小血量$\geq d$，现在血量的最大值，转移还是枚举上一次操作，看起来复杂度是$O(nv\log v)$，1e7带$\log$真的行吗?

然后你发现我们没有办法进一步优化了，因为这玩意不弱于背包，boos一上来第一炮把血条打干净，后面不开炮了，你就是在跑完全背包(现在我已经不知道该叫完全背包还是无限背包了，很年轻的时候学的是前一种，但是看起来两种说法都很流行?)。所以交上去，直接就过掉了。

B. area

首先根据平抛的结论求出落地点，然后问题是圆和多边形交的面积。考虑多边形的顶点，以及多边形和圆的交点，从这些点到圆心连线，这会把交分成若干个扇形和三角形。求即可。

C. cube

扫描线，问题是矩形加减，每次操作后查询全局$>0$位置数。只需要维护$0$的个数，然后k-dt维护一下就行了，复杂度$O(n\sqrt{n})$。

D. DeBruijin

这是一个欧拉回路的经典问题。如果直接搞则转化为哈密顿回路，我们就完蛋了，考虑把这个数当成边而不是点，两个数可以转一下相互得到，就让它们有公共端点。

E. Edit distance

模拟。

F. 病毒侵袭

kmp。

G. 邂逅明下

这怎么看都是一个经典问题。

直接做看起来并不行。

考虑一个经典想法，不管先手怎么取，后手总可以保证两个人一共取$p+q$个，如果最后剩下$\leq p$个，也就是说$n\bmod{(p+q)}\leq p$，那么后手将绝杀。否则，先手上来取$n\bmod{(p+q)}-1$个，就必胜了。

H. 旋转

不会，但是是板子。

D11

A. A Simple Language

模拟。

B. Travelling

枚举全排列。

C. King of Destruction

无源汇最小割。这个不需要学习科技，直接最小割树就行了（

stoer-wagner，sw算法说的是，考虑我们随便求一个$s$到$t$的最小割，如果它不是答案，那么说明在割掉全局最小割之后，$s,t$在同一个连通块，此时把它们缩点不会影响全局最小割。于是每次求出随便一个有源汇最小割并合并源汇，合并$n-1$次之后，必然有一次得到了全局最小割。

结论 随便选一个点开始跑prim最大生成树，设最后连通的点是$t$，倒数第二个是$s$，那么$(V-t,t)$是一个$s$到$t$的最小割。

证明 略（

于是做即可。fib堆优化prim，复杂度$O(n^2\log n+nm)$，一般实现小常数的$O(n^3)$。

D. Pupu

注意 all of a PuPu’s skins has been changed from opacity to clarity 是说都至少变成clarity一次，而不是当时全都是clarity。直接算即可。

E. The Chess

显然只可能动车，马，炮，车炮，马炮。

车是简单的，bfs即可。马，炮是一样的。

车炮是简单的，都bfs一下，然后枚举最后的位置即可。马炮是一样的。

F. The Different World

好像很难看懂题。大概是说，求第$n$个数$m$，满足存在一个$k$使得$\sum\limits_{i=k+1}^{k+m}i^2=m^3$，输出$m,k$。

直接自然数幂和，然后展开那个式子，发现$m$是三次的而$k$是二次的，于是爆力求解$k$，得到$k=\frac{\sqrt{33m^2+3}}{6}-\frac{m+1}{2}$，看起来如果它是整数我们就找到了一组$m,k$。

打表发现，只要那个根可以开出来，也就是说$33m^2+3$是平方数，得到的$m,k$就必然是整数。接下来证明这个事情。

如果$m$是奇数，那么问题就变成$\frac{\sqrt{33m^2+3}}{6}$是整数，也即$\sqrt{33m^2+3}$是整数且是$6$的倍数。由于$m$是奇数，有$33m^2+3\bmod{2}=0$；显然也有$33m^2+3\bmod{3}=0$。所以只要求$33m^2+3$是平方数就行。如果$m$是偶数，问题就变成$\sqrt{33m^2+3}$是整数，是$3$的倍数且不是$2$的倍数，证明看起来是一样的。但是打表发现好像没有$m$是偶数的解。

剩下的问题是求所有使得$33m^2+3$是平方数的$m$。

设$u^2=33m^2+3,v^2=m^2$，那么问题变成求所有$u^2-33v^2=3$的正整数解。这是一套经典的理论，称为Pell方程，我也是现学的。

结论 要求$ax^2-by^2=c$的所有整数解，先求$x^2-aby^2=1$的最小正整数解$x_0,y_0$，以及$ax^2-by^2=c$的最小正整数解$x_1,y_1$，那么$ax^2-by^2=c$的第$k$个正整数解即为

。这显然是它的一个根，但我不会证明这是所有根。知道这个之后爆力求解即可。

Pell方程的那一套里面，最复杂的部分这题并不涉及，是用连分数求$x^2-ny^2=-1$的最小正整数解。我并不打算学，要是哪里出连分数题大家应该都不会。

G. The Number of set

状压，背包。

H. Buried memory

最小圆覆盖。

I. Warcraft

直接dp，设$dp(i,j)$表示现在是$i$时刻，你有$j$法力，boss的最小血量。不需要记你的血量，因为boss一直在打你。前面好像有一个更强的题?

D12

A. Go Fishing

搜肯定没问题。

是不是可以费用流做到多项式复杂度啊/kel

B. N Knight

注意这里的knight说的是车/jy

类似于错排的经典容斥。

C. Cut Pyramid

不要几何题啊/fn

体积可以强硬插值积分，所以就结束了。但是我不会写/cy

D. Travel around the world

哈密顿路/jy

考虑一对$(a,b>a)$什么时候是可行的，看起来最优策略总是先从$a$走到最小值，然后从最小值走到最大值，然后从最大值走到$b$，于是这玩意两边是两段双调的，可以强力dp，中间如果没有断层就不用管，有就直接输出$0$，复杂度是$O(n^4)$。

考虑优化，我们写出dp的式子，设$l(i,j)$表示从$i$走到最小值，从最小值走到$j$是否可行，$r(i,j)$类似，转移枚举下一个点给哪一边，复杂度是$O(n^2)$。求出这个之后，我们枚举$a,b$，看$l(a,a+1)\operatorname{r(b,b+1)}$，然后这个东西很好做到$O(n)$。

考虑进一步优化，设$l(i)$表示从$i$走到最小值，从最小值走到$i+1$是否可行，$r(i)$类似，转移枚举上一个在最小值到$i+1$路径上的点。注意到一个性质，因为我们只要可行性，所以如果有相邻三个点都在$i$到最小值的路径上，那么中间那一个换到最小值到$i+1$的路径上不会更差，于是转移的枚举量是$O(1)$，总复杂度$O(n)$。这就加强到1e6出给小朋友。

E. Tetris

模拟。

F. Counting Problem

看到题目名，就好这口啊!

然而是简单题。选选选就行了。注意不能求逆元，需要递推组合数。

G. Disharmony Trees

卡笛尔树。找到高度的$\min$，然后求$\min$跟所有树的贡献，这个贡献看起来只需要用一个值域BiT维护一下有多少距离更小的。然后递归两边。复杂度$O(n\log n)$。

H. Man Down

dp。

I. Treasure Division

背包。

J. Ant Trip

题意好像是连通块数?

K. Tracing Fairy

终于有二次元题面图片了（

L. Tracing Fairy

模拟，

D13

A. To Be Or Not To Be

模拟。

B. Nim or not Nim?

先模拟一下算个sg值，然后找找规律。

你发现当$n\bmod{4}=3$时，$\mathrm{SG}(n)=n+1$，当$n\bmod{4}=0$时，$\mathrm{SG}(n)=n-1$($n=0$时为$0$)，此外$\mathrm{SG}(n)=n$。做即可。

C. I love sneakers!

看起来是什么所谓分组背包，每组至少选一个。这个简简单单，我们只需要依次处理每一组，记一个$0/1$表示有没有选这一组就好了，如果没选则不能转移到下一组。

D. Board Game

搜。

E. War

平面图最小割，也就是对偶图最短路。

F. Escape

军训的教官还敢喝酒/jy

显然可以二分答案之后线性规划多物品流。考虑有没有正常一点的做法。

注意到每个门处理的是一个连续的区域。同时注意到，只要每个门处理的是一个连续的区域，并且这个区域包含自己，那么它一定是满负荷运转的，也就是说每秒都有一个人出去。于是这个区域的花费就是区域的大小。问题变成，对于原图每个连通块，把点分成若干个部分，每部分连通且包含恰好一个E，最小化最大的部分的大小。

设原图中一个连通块有$n$个人和$c$个E，感觉上下界$\lceil\frac{n}{c}\rceil$一定是可以达到的。于是多源bfs就做完了。复杂度是$O(rc)$，是不是赢麻了（

G. Saving Beans

隔板一下，答案是个组合数，然后Lucas就行了。

H. How Many Answers Are Wrong

加权并查集。

I. A high-dimensional problem

知道了点积就知道了平面。高消解一解就好了。

D14

A. Happy Girls

模拟。

B. Bee

经典问题。二分答案，然后模拟。

C. Josephus Again

看图你就理解题意了。

这玩意形成了一个类似stern-brocot环的形状，我们可以求出一个点的子树里面有多少点，然后二分即可。

D. Number game

状压dp，然后这看起来是个dag路径计数，在这上面跑就行了。

E. Dog and dog

模板 定积分。你需要一些数学功底，或者需要一把wolfram alpha。

F. Picnic Cows

看起来并不是很困难。在值域上dp，然后转移方程是$dp(i)=\min_{j<i-k}dp(j)+(pre_i-pre_j)-(i-j)a_{j+1}$，然后这个看起来就很斜率优化。

G. Pleasant sheep and big big wolf

模板 最小割。

H. Zjnu Stadium

并查集。

I. XX’s puzzle

看起来很有意思。三角剖分中每个三角形都以多边形的一条边作为边，所以等腰三角形要么是一条边连到对面的顶点，要么是相邻两条边。前者只在$n$为奇数的时候出现最多一个，后者看起来很局部。dp一下，把相邻两条边连成的三角形缩起来，直接计算三角剖分方案数，这个好像是一个组合数。如果是$n$奇数就再加上枚举中间那个有还是没有，如果有在哪里，两边拼起来。

J. Data Processing

模板 快速幂。

D15

为什么这么多场¿

A. Cat Jim

直接做。如果$i$堆里面有一个$j$，我们从$i$连边到$j$(允许重边)，那么这个会形成若干个环的并，我们几乎每一步都可以走掉一条边，除了在连通块之间需要额外的一步。

B. Peaceful Negotiation

考虑容斥，我们钦点$k$条边贴着放了，那么把两个人绑起来，然后随便排，方案数是$\binom{n}{k}2^k(2n-k)!$。做完了。

C. Vim

模拟。

D. Group Travel

邮局。

E. Fibonacci

要求$10^k\mid f_n$的$n$。

打表观察一下，$k=8,9$的答案是

1
2
3
75000000 150000000 225000000 300000000 375000000 450000000 525000000 600000000 675000000 750000000 825000000 900000000 975000000 1050000000 1125000000 1200000000 1275000000 1350000000 1425000000 1500000000 1575000000 1650000000 1725000000 1800000000 1875000000 1950000000 2025000000 2100000000
750000000 1500000000。

，看起来很有规律。做就行了。

F. Mine

状压dp。

G. Stock

经典结论是，买一定尽可能多买，卖一定尽可能多卖。dp，设$dp(i)$表示在$i$天卖了股票，最多剩下多少钱。转移枚举这个股票是在哪买的即可。

H. Core

梦 幻 联 动

然而这个居然还是加强版。题意说的是，找一个连通块，使得这个连通块到树上任意点的最大距离最小。noip题说的是找一条链。

显然这个连通块必须包含center，这里的center应该是加权的。然后直接从center出发往各子树扩展，开个堆维护当前的瓶颈就行了。

I. Generator

板子题。

J. Count Cross

直接做。

D16

A. Area2

并=和-交。

如果保证是凸多边形，kdw就秒了，只需要半平面交拍上去就行了。如果不是凸的呢?

注意到$n,m$非常小，所以我们可以考虑强行算出这个交。考虑找到所有两个图形的边的交点，扫描线扫过去，这把平面分成了若干个区域，我们只需要算出每个区域是否在交里面，从里面找一个点算它是否同时在两个多边形里面就行了。复杂度是$O(n^3)$，带小于$\frac{1}{4}$的常数，感觉如果好好剪一剪可以做到$\frac{1}{16}$。

然而感觉上很可以低于这个，但是我对计算几何没什么感觉，所以还是不瞎扯了。

B. Battle

模板 最大权闭合子图。

C. Party

模板 2-sat。nit你在干什么啊¿

D. Play game

直接做。可以让机子帮你插一插。

E. twoNumber

模拟。

F. 病毒侵袭持续中

模板 acam。nit你清醒一点/jk

G. 火拼双扣

模拟。nit你在干什么啊/fn

H. 小t的游戏

显然它肯定会循环。

显然这是一个集合，顺序是没有关系的。先从小到大排个序，这样每次杀掉的都是一个前缀，于是我们可以支持快速的模拟。但是这又有什么用呢?

考虑能不能找点性质。考虑什么样的局面才可能是循环的。最简单的是$1,2,3,…,k$，循环节是$1$。

想象一下这个变化的过程，你发现所有的序列都在向$1,2,3,…,k$逼近，因为当你有$c$堆的时候，你会在位置$c+1$加入一个$c$个石子的堆，那么画到平面上就是$(c+1,c)$。同时因为平均每轮要杀掉一堆，所以它大概就在$x-y=0$这条线上。于是我们大胆猜测，只有不能进一步向$1,2,3,…,k$逼近的局面才可能是循环的。

如果总和是$\frac{1}{2}k(k+1)$，那就输出$1$。

否则，观察一下样例第二组，你发现它大概是，

1
2
3
4
5
6
0 2 3
1 2 2
1 1 3
0 2 3
1 2 2
1 1 3

这样的。它看起来跟$1,2,3$非常接近，但是它的循环节是$3$，仔细观察一下，你可以看到一个1在转圈圈。再试一试2 2。

1
2
3
4
5
6
0 2 2
1 1 2
0 1 3
0 2 2
1 1 2
0 1 3

你还是可以看到有一个1在转圈圈。于是就结束了，如果总和介于$\frac{1}{2}k(k+1),\frac{1}{2}(k+1)(k+2)$之间，那么答案是$k+1$。

I. 最长回文

模板 manacher。模板赛?

D17

A. Arrest

如果是一条链，直接从这头冲到那头。

如果是一个菊花，那么需要在中间留一个人。

于是猜测答案是度数$>2$的点个数$+1$。手玩了一下样例你发现不对。小朋友想一想，这是因为留的那一个人不一定一直站着不动。如果子树已经搜查干净了，那么子树里面站着的老哥们就可以到别的子树继续战斗了。

考虑我们枚举一个根，然后依次自底向上处理根的子树。设$dp(u)$表示$u$子树最少需要多少人手，如果$u$是二度点那么把子树里面最高的老哥提上来就行了，否则我们需要在$u$放一个人。处理完一个儿子，那边的人手还可以拿来用，所以$dp(u)=1+\max\limits_{v\in\mathrm{ch}(u)}dp(v)$。

然后你发现样例还是不对。看起来是说，如果这个$\max$只有一个，那么我们处理完剩下所有子树，可以把$u$下移到这个子树去，此时那个$1$就不用加了。做完了。

B. Counting spanning trees

草，看起来好困难（

不过实际上也不困难吧/jy，考虑一个强力做法，我们直接矩阵树，每个点开一个元，然后我们要拉插$100$元gf。是不是随随便便就做掉了/tuu

考虑利用树的结构，直接dp即可。然后就做完了。但是我们看起来并不满意。

考虑能不能写成gf。刚才那个dp看起来是设$f_n$表示答案，$g_n$要求根的度数是$d-1$而别的点度数是$g$，容易看出$F^\prime=G+G^2+…+G^d=\frac{1-G^{d+1}}{1-G}$，当然也有$G^\prime=F+F^2+…+F^{d-1}=\frac{1-F^d}{1-F}$，边界是$[z^0]F=[z^0]G=1$。然后这是两个方程，直接分治法法塔就彳亍了。没有写过，不知道式子是否正确。

C. Gcd & Lcm game

直接做。算lcm的时候，gcd不一定有逆，不过显然可以把第一项单独拿出来除掉gcd这样的。

D. Intelligence System

mst。

E. Mars Life Tree

火星生活在树上/jy

完全没有看懂题。是说，找到一条边，使得从这条边开始长出这棵树代价最小?当这个做吧。注意到这个代价和谁在长叶子是无关的，于是模拟即可。

F. Multiply game

直接做。

G. Mystery ET

状压dp。

H. ssworld VS DDD

先爆力求出更大的概率，然后直接dp。

如果期望谁赢，好像是可以做到$O(1)$的。

I. Recursive Ants

建出递归树，设$dp(i,j,k)$表示在$i$号点代表的矩形中，从一边第$j$个点进入，另一边第$k$个点离开，是否可行。转移枚举走儿子的顺序，然后卷起来就行了，感觉上复杂度是$O(2^{3n})$。

J. Network

单点修改，链kth。看起来很困难啊/yun

考虑二分答案，然后统计一下rank，这只需要树剖树套树就好了，一共是四个$\log$。

考虑有没有什么正常做法。带修莫队，很难不过。

考虑有没有什么更正常的做法。二分答案肯定要有，然后rank是可差分的，考虑对时间分治，然后对树点分，这就是三个$\log$。

考虑整体二分，要支持单点修改链求和，树剖就是三个$\log$，静态lct就是俩$\log$。俩$\log$就是(算法竞赛范围内的，不知道是不是学界的)下界了，因为链kth是经典树套树。

可是据说爆力就过了啊?这么水的吗/qd

D18

A. WORM

搜。

1e5能不能做啊?

B. Josephus again

具体数学给出了约瑟夫问题的公式，但是那个实在是太离奇了，不是很好用。

考虑一个牛逼递推式，我们有$J(n,k)=(J(n-1,k)+k)\bmod{n}$，含义是我们上来会干掉$k-1$号(从$0$开始编号)而递归到有$n-1$个人的情况，当然需要对编号作变换，接下来第一个人是$k$，于是$J(n-1,k)$相当于给每个人的编号都减去$k$之后的答案，我们再加回来就好了。你可能会疑惑中间不是断了一个吗?有趣的是它被平移到$n-1$位，所以没了。

然后考虑这个如何优化。注意到$k$很小，于是当$n$很大的时候，取膜是很难发生的，可以一口气加上一车。复杂度看起来有可能是$O(k\log_k n)$，但是wiki上写的是$O(k\log n)$，不过我实在是非常怀疑这里是前者。看一眼wiki你发现这个好像已经很优秀了。

C. Go Home

模拟。

D. Necklace

挑战哈密顿。

E. Least common multiple

显然我们分出来的所有数都是互素的，也就是说只可能选若干个素数幂。

显然我们会先选小的。然后可能的素数非常少，爆力即可。

F. Parliament Seat

模拟。

G. A tree game

模板 green hackenbush。

H. Eleven puzzle

搜。状态数看起来是3e9，如果加上一些启发式方法和一些剪枝，速度应该会很吓人。

I. Life Game

矩阵快速幂。

D19

A. The Partition of A Graph

看起来是简单题。如果两条边可以在一组，我们就给它们连一条边，然后要找一般图完美匹配，带花树即可。呃复杂度是啥啊?好像是$O(n^7)$之类的。

居然把我难到了。直接dfs，走到不能再走，就在回溯的时候把每两条边分一组，注意是最深的和次深的一组，而不是最浅的和次浅的一组，这样感觉上完全不会丢解。类似于欧拉路?

B. Round Table Banquet

太拉了，国王请吃饭，每个人只有一道菜（

好像曾经和zyz讨论过这个问题，那是hdu mutc09 D7 C。讨论奇偶性，问题变成相邻的不同，然后可以容斥得到一个简单答案，或者矩阵快速幂优化dp。

C. Defense of the Ancients

先求出左下凸壳(因为有位置限制，非常的好)，然后二分找到交的线段，在上面求一次交点即可。

D. MAX Average Problem

经典题。设前缀和是$s$，那么我们要找一对$i>j$，最大化$\frac{s_i-s_j}{i-j}$。注意到，固定一个$j$的话，相当于把后面所有$i$的$(i,s_i)$画到平面上，要求到$(-j,-s_j)$连线斜率最大的点。单调队列维护凸壳即可。

E. Ant on the graph

矩阵快速幂。先用一个不统计答案的矩阵跑到Tmin，然后用一个统计答案的矩阵跑到Tmax。

F. Another Panda’s Birthday Present

爆力枚举每种情况算概率，这个东西足有$2^{54}$。

然后注意到一个骰子只有红色和蓝色的数量有效，这就只剩下$7^9$。打打表就行了。

这个题应该和前面那个积分题放到一场里面用来吓人（

G. Pagination

模拟。

H. Chromatron

恐怖模拟。

I. Binary Search Tree

看起来我可能没有理解题意。

区间dp。设$dp(i,j,k)$表示区间$[i,j]$构成一棵子树，这棵子树根的父亲的权值是$k$的最小代价。$k$一定是某个点的初始权值(因为可以改成实数)，所以复杂度是$O(n^4)$。如果不可以改成实数，还需要多一个$n$。

J. Stone Game, Why are you always there?

直接dp。

然后09就结束了呢。感觉好多题，但是平均难度很低啊（

每场有一两道牛逼题可能是oi训练比较好的难度。

好像09一年的题就够2.5w字了。要写上古hdu多校全题解，对高中选手来说是不是不太可能啊（

往后跳一跳。下一步做16年。

2016

D1

A. Abandoned country

强行套皮/jy

mst然后换根。只换根不dp，是不是更适合称为up and down?

B. Chess

直接搜sg值。

C. Game

题意是求所有两点之间最短路的平均值，而不是让你找一个点最小化到其它点的最短路平均值。

那是不是简简单单啊!题目给了一个很牛逼的性质，没有两个守卫八连通下相邻，或者在同一行同一列，这说明直接走最短路几乎不可能被阻挡。只有一种可能的情况，也就是比如起点在左上终点在右下，中间每一行都有一个守卫，并且有从左上到右下排成一条斜线，第一个在起点右边，最后一个在终点左边。此时必然需要从一个口绕过去，答案会$+2$，最多也只会$+2$了。

于是我们统计有多少$+2$的。先只考虑起点在左上终点在右下的。直接强行枚举乱算就行了（

D. GCD

每个点往前不停二分。复杂度$O(n\log n\log v)$。

E. Necklace

状压dp。

F. PowMod

显然是两部分。第二部分是 模板 扩欧定理，于是考虑第一部分。

小朋友想一想，为什么$n$无平方因数呢?注意到$\varphi$有一个很好的性质，它不积性是因为$n$中$p$的次数对$\varphi(np)$的值有影响，而只有这个次数是不是$0$这件事有影响。如果$n$中没有$p$，那么$\varphi(np)=\varphi(n)\varphi(p)=(p-1)\varphi(n)$，如果有$p$，那么$\varphi(np)=p\varphi(n)$，这和$p$的次数无关。

于是如果$n\perp i$，那么直接拆开即可。如果$n\not\perp i$，那么我们枚举$\gcd(n,i)$，然后容斥一下。这个容斥是每一维上容斥的笛卡尔积，所以在考虑一个素因数的情况下会比较简单，实际上很多数论中的容斥都有这个性质。经典例子是快速计算任意函数卷$\mu$。

考虑随便找一个$n$的素因数$p$，那么由于$n$无平方因数，有$\varphi(n)=\varphi(p)\varphi(\frac{n}{p})$。此时如果$i\perp p$，那么有$\varphi(in)=\varphi(\frac{in}{p})\varphi(p)$，否则则有$p\mid i$，这样的$i$只有$\frac{m}{p}$个，把它们拿出来单独算。写出来就是

，注意到$p\mid n$，所以$\varphi(inp)=p\varphi(in)$，于是有

就结束了，复杂度是$O(2^{\omega(n)}\sqrt{m})$。加强到1e14出给小朋友/se

G. Rigid Frameworks

我们从小就知道三角形具有稳定性。

一开始猜的结论是，每行每列都有一个就行，但是百度一下看起来并不是这样。一个反例是，$n=m=2$，把主对角线杀了，那么这个居然还可以折，大概就是绕着中间那个点转一转，可以想象一下（

那么我们需要wikipedia一下，看看是不是很有已经存在的理论来描述这个东西。发现真的有，你可以搜索 Structural rigidity。结论是，一个图是刚性的，当且仅当它存在一个Laman子图。而Laman图的定义是，每个点数为$k>1$的子图只有不超过$2k-3$条边，并且整张图有恰好$2n-3$条边。

这个可以直观理解一下，刚性图就是，边是线段，画在平面上只有三个自由度的图，也就是确定了一个点和另一个点与这个点的角度，就确定了整个图画下来长啥样。没有边的图有$2n$个自由度，每加入一条连接两个点的线段，感觉上就可以缩减一个自由度，但是如果两个点之间已经是刚性的了则没有用，于是限制每个子图只能有$2k-3$条边，确保每条边都可以缩减一个自由度。Laman图在这个问题中好像不是很有用，但是自由度的概念非常有用。

还有一个牛逼东西叫刚性拟阵，它指出一个图的所有子图和它们的自由度构成一个拟阵(好像是?)，这说明所有极小刚性图的大小是一样的。所以我们猜测这在加了一些边的网格图上也成立，所以我们考虑极小刚性图是什么样的，也就是什么样的边能缩减一个自由度。

实际上如果你真的看了wikipedia，它提到了网格图自由度的结论，但是如果你没看那就没事了（

考虑网格图的自由度有多少个……你发现看起来有$2+n+m$个，也就是我们确定左下角，这是两个自由度；然后确定左边和下边，每条线段有一个角度，这是$n+m$个自由度。确定了左边和下边的所有点之后，每个点的坐标都确定了。所以说，我们需要放至少$n+m-1$条边，刚才$n=m=2$两条边就搞定了是显然不行的。

考虑什么情况下加入一条边是无效的。你发现这当且仅当它所在的正方形已经固定了，这个是可以推广的，也就是说加入一条边之前，不管图怎么动，这条边的两个端点的距离都不变，那么这条边是无用的。不妨称一对不管怎么动距离都不变的子图为相对固定的，当然这是因为我没有找到一个术语。显然相对固定是传递的。

考虑如果一个正方形所在的行没有加任何边或者列没有加任何边，那么它肯定不是固定的。如果有，那么我们找到它同行的一条边和同列的一条边，如果这两条边相对固定，那么这个正方形应该是固定的，而如果不存在这样的两条边，我们还可以像一开始的讨论中那样弯一弯。

那么如何看两条边是不是相对固定的呢?如果这两条边同行或者同列，那么它们肯定是相对固定的。同时因为相对固定具有传递性，如果存在一条链，使得链中相邻两个点要么同行要么同列，那么链中任意两个点都是相对固定的。除此之外看起来没有别的情况了。

你发现这个看起来是经典套路了。我们给每行每列建一个点，然后每条边连接它所在的行列，那么两条边相对固定，当且仅当它们在一个连通块中。类似地可以推出，如果加入一条边的时候，它的端点在同一个连通块中，那么它就是没有用的，否则它还是有用的。这一套分析看起来还是非常套路，但是看起来也非常优美啊（

然后问题变成连通二分图计数，每条边还有$2$的权值。刚才考虑了往生成树上加边，但是发现加完之后并不是二项式反演，所以考虑一个牛逼dp。

设$dp(i,j)$表示两边有$i,j$个点的答案。注意到连通很是不容易dp，所以我们容斥一下。考虑$1$号点所在的连通块，如果这个连通块不包含所有点，那么就是不连通的，否则就是连通的。我们对它包含的点数进行容斥，现在问题是左边钦点了$i^\prime$个点(包括$1$)，右边钦点了$j^\prime$个点，剩下随意的方案数，看起来就是$\binom{i}{i^\prime-1}\binom{j}{j^\prime}dp(i^\prime,j^\prime)3^{i-i^\prime+j-j^\prime}$，而容斥系数是$(-1)^{i+j-i^\prime-j^\prime}$。然后就结束了。

确实是牛逼题。这就搬给小朋友。

另外，生成树确实是有结论的。完全二分图的生成树个数是$n^{m-1}m^{n-1}$。

H. Shell Necklace

模板 多项式求逆。写一个dp，然后发现它是个卷积，然后用gf描述一下，就是$F=CF+1$，于是$F=\frac{1}{1-C}$，或者这里面可能有些别的东西没有考虑到，不过大概是这个意思。或者你也可以直接看出多项式然后直接得到这个式子?

I. Solid Dominoes Tilings

当然考虑状压dp。问题就是每个竖线上都有一个横着的，每个横线上都有一个竖着的。

设$dp(i,S,T)$表示考虑前$i$行，$S$中的竖线上已经有了骨牌，上一行留给这一行的状态是$T$，或者说$T$表示上一行中放了一个竖着的骨牌的上半部分的位置。预处理所有可能的转移，看起来数量是斐波那契数，这个东西复杂度看起来低于$O((2\sqrt{5}+2)^nn)$，不过还是没太有可能。

考虑换成轮廓线，复杂度变成$O(4^nn^2)$。但是问题是我们需要砍那个$4^n$啊?

容斥。钦点若干竖线可以切开，那么就把这个分成了若干部分，每一部分是独立的，可以跑$n$遍轮廓线dp全都预处理出来，然后只有最大的一遍影响复杂度，最后复杂度是$O(2^nn^2)$。那这么说可以加强到$18$?

J. Subway

树同构/jy

经典做法是，我们找到重心，把重心当成根拎起来，如果有两个就把两种情况都试一下。

对于有根树同构，简单做法是树hash，复杂做法是ahu。

树hash的一个难以hack的经典方法是，每个点的hash值是儿子们的hash值分别乘上第子树大小个素数，然后加起来再$+1$，比较的时候还需要比较子树大小。看起来是说$f(u)=1+\sum\limits_{v\in\mathrm{ch}(u)}p_{\mathrm{size}(v)}f(v)$，然后$\mathrm{hash}(u)=nf(u)+\mathrm{size}(u)$这样的。

然后ahu还是去他的吧（

K. tetrahedron

为什么只有这个题首字母是小写的（

几何题还是去他的吧。

这个东西可以变成到四个面距离平方的方差为$0$，然后方差$\geq 0$，并且这是一堆很光滑的东西，所以只需要上一个退火就行了，我猜测直接梯度下降就行。

这玩意有公式，但是我怎么可能推出这个公式呢（

D2

这同时是ptzsc2016的Day1。

脑子一抽写了翻译(这是在打算开ptz的时候开的，然后开了一场就暂时弃了)。不过实际上写不写差不多?

可以在baekjoon oj提交。不过hdu马上就要修好了?

翻译

A. Acperience

给一个序列$w_i$，你可以选择一个数$\alpha\geq 0$和一个序列$b_i$，要求$b_i=\pm 1$，并且$\sum(w_i-\alpha b_i)^2$最小，只需要输出这个最小值，但是你需要输出有理数。$n\leq 10^5,-10^4\leq v\leq 10^4$，大约$15$组数据。

B. Born Slippy

有根树，点有点权$w_i$，还有一种位运算op=and/or/xor。对于每个点，求从它开始走，每次走到一个祖先，如果从$u$走到$v$，则答案增加$w_u\operatorname{op}w_v$，只需要对于每个点找到这个最大值。$n,v\leq 2^{16}$，多测，$\sum n\leq 10^6$，6s。

C. Call It What You Want

树上加不超过五条边的无权图，求最长简单路。$n\leq 10^4,m\leq n+4$，大约$50$组数据。

D. Differencia

两个序列$a,b$，支持$a$的区间推平，查询区间有多少$i$满足$a_i\geq b_i$，强制在线，操作完全随机生成。$n\leq 10^5,m\leq 3\times 10^6$，14s，多测，大约$10$组数据。

E. Eureka

欧几里得平面上有$n$个点，定义一个点的子集$P$是好的，当且仅当其中存在一对点$u,v$，使得对于任意$w$，都有$\mathrm{dist}(u,v)\geq\frac{\mathrm{dist}(u,v)+\mathrm{dist}(u,w)+\mathrm{dist}(v,w)}{2}$。求有多少个好的子集，膜$10^9+7$。$n\leq 1000,-10^9\leq x,y\leq 10^9$，多测，$\sum n\leq 4\times 10^4$，5s。

F. Fantasia

无向图，点权，删去每一个点(相互独立)之后，求所有连通块点权乘积之和。$n\leq 10^5,m\leq 2\times 10^5$，多测，$\sum n,\sum m\leq 1.5\times 10^6$，5s。

G. Glorious Brilliance

给一张图和一个黑白染色方案，但是这个方案不一定是对的，你每次可以交换相邻两个点的颜色，求最少的交换次数使得它是对的，也就是没有相邻两个点颜色相同，并构造方案，无解输出-1。$n\leq 500$，$200$组数据。

H. Helter Skelter

有一个很长的01串，由$n$个0连续段或者1连续段构成，第一个字符是0，第$i$段长度是$x_i$。有$m$次查询，每次给$a,b$，求是否存在一个子串恰好有$a$个$0$和$b$个$1$。$n\leq 1000,m\leq 5\times 10^5,x_i\leq 10^6$，多测，$200$组数据，$\sum m\leq 2\times 10^6$。

I. It’s All In The Mind

有一个序列$a$，每个数都在$0,…,100$之中，有一些位置是未知的，现在给你已知的所有位置和它们的值，把未知的位置填上$0,…,100$的数，使得序列单调(非严格)递减，不全为$0$，最大化$\frac{a_1+a_2}{\sum a_i}$，只需要输出这个最大值，并且你需要输出有理数。$n\leq 100$，$2000$组数据。

J. Join The Future

给定序列$x,y$，若干个区间和值的二元组$([l_i,r_i],s_i)$，求有多少序列$a$，满足$x_i\leq a_i\leq y_i$，并且$a$在$[l_i,r_i]$的和膜$2$是$s_i$，并构造其中字典序最小的。$n\leq 40,x_i,y_i\leq 10^9$，$110$组数据，5s。

K. Keep On Movin

有$n$种字符，第$i$种有$a_i$个，用它们构造若干个回文串，每个字符都要用完，最大化最短的串的长度，只需要输出这个长度。$n\leq 10^5,a_i\leq 10^4$，多测，大约有$\sum n\leq 3\times 10^6$。

L. La Vie En Rose

有长$m$的模式串$p$和长$n$的文本串$t$，对于$t$的每个长$m$的子串，求它是否与$p$经过一次变换生成的某个串相同。一次变换定义为，选取$p$的若干对相邻位置并交换每一对，并且一个位置不能被换两次，比如abcd可以变换成badc或者acbd这样的。$n\leq 10^5,m\leq 5\times 10^4$，2.5s 64mb。

M. Memento Mori

有一个$n\times m$的矩阵，其中$k$个位置是$1$，别的全是$0$。给一个$1,2,3,4$的排列$p$，求有多少极小子矩形，使得其中恰有四个$1$，并且设这些$1$从上到下(行编号从小到大)的位置是$(r_i,c_i)$，则对于任意$1\leq i<j\leq 4$，有$(p_i-p_j)(c_i-c_j)>0$。$n,m,k\leq 2000$，多测，$250$组数据，大约有$\sum k\leq 6\times 10^4$，2.5s 64mb。

sol

A. Acperience

签到题。首先每个$b$显然是和对应的$w$符号相同，于是我们得到一个$\sum w_i^2-2\alpha\sum w_ib_i+\alpha^2\sum b_i$。然后惊喜发现这是二次函数，求个极值就行了。

感觉适合给普及组做?

B. Born Slippy

$2^{16}=65536$。直接递推(或者你也可能觉得这是dp?)是$n^2$。

考虑什么数据结构可以支持维护一堆$a,b$，给一个$x$，查询$x\operatorname{op}a+b$的$\max$。

对于or，我们不需要这样的数据结构，因为显然增加点不会让答案变劣，转移必然直接到父亲。

对于xor，好像只能想到trie，但是在trie上走看起来比较困难，因为如果一个数$b$很大但是$a$没有这一位，另一个数$b$不够大但是$a$有这一位，我们并不是很好立刻决策。

对于and，好像只能想到法嘛塔，看起来没有什么前途。

我们可能都需要像or那样找点结论。

dwt之言可谓切中了肯綮，打表可知xor也是直接选父亲最优，而zyz指出这是因为sum>=xor。现在只剩下and我们还不会了。

考虑一个点的答案总是不比父亲小，于是转移到祖先看起来是很离奇的事情，除非我们是为了获取巨大的$x\operatorname{and}y$。考虑一个点$x$往上所有的$x\operatorname{and}y$的前缀$\max$。

然而这个东西可能有很多个。and的构造是一条$2^{15}$的长链，下面挂着$2^{15}$个点，上面的权值从上往下依次是$2^{15}-1,2^{15}-2,…$，下面全都是$2^{15}-1$。所以我们失败了。

考虑了很多东西，但是好像都得不到什么，于是我来猜一个结论，从每个点往上找到每一位第一次出现，转移必然在这其中。考虑如何证明，考虑现在要给$x$转移，对于某个$z$，考虑$x\operatorname{and}z$的最高位，如果$z$的这一位不是第一次出现，我们直接选取第一次出现$y$，改为走$x\rightarrow y\rightarrow z$，可以得到两倍的这一位。于是做完了。

这题非常有趣，我很喜欢。这就搬给普及组。

但是我做法好像跟网上不太一样/yun，网上做法都是折半，但是我找了一个写了一发拍了一拍，看起来是对的?

呃可以在baekjoon提交，看起来它确实是对的，并且我手动O2了一下就最优解了。

C. Call It What You Want

考虑树怎么做，就是直径。

考虑我们枚举多出来的五条边有哪些经过了，然后枚举一个经过顺序，然后中间因为是简单路径只能走唯一的路径，边上就往两边dfs，复杂度是$O(5!n)$。

D. Differencia

随机数据?odt冲啊/fn

正经做法是归并树。讲道理归并树应该算是线段树的一种，还是说归并一个序列的线段树是归并树的扩展或者延申?

E. Eureka

这个问题看起来好像并不计算几何。考虑那个式子啥时候会成立，它等价于$\mathrm{dist}(u,v)\geq\mathrm{dist}(u,w)+\mathrm{dist}(v,w)$。

看起来这个式子很离奇啊，因为欧氏距离是满足三角不等式的/yiw，然后这个是反着的?也就是说它们只能相等了，也就是说实际上它算的是整个点集都在一条直线上的方案数。

然后就随便做了，枚举两个点确定一条直线，然后统计直线上随意选点的方案数就彳亍了。记得预处理2的幂。

F. Fantasia

看起来是不是简简单单，只需要分治，分治，分治，然后，并查集查询，就好了。

G. Glorious Brilliance

先看一看是不是二分图，如果不是那就没救了。

然后我们只能想到网络流了。考虑交换01相当于把1移动到0的位置，于是对每个连通块枚举两种染色方案，跑Floyd求最短路，然后猜测所有的1一定可以都走最短路而不相撞，于是km跑最小权完美匹配即可。复杂度是$O(n^3)$。

H. Helter Skelter

直接爆力枚举左右端点所在的段，然后就是两个区间的笛卡尔积，然后就可以得到一些线段和一些矩形，每次是查询一个点在不在这里面，直接数点即可。

但是你发现$200$组数据好像完全没法这么搞，做到低于$n^2$才有可能?

然后想了很久都不成功。上网一查发现$n^2\log$就过了（

$n^2$也是简单的，我们把0,1的个数画到平面上，考虑到可行区域是连续的，于是我们爆力枚举两个分段点，求出这个区域的边界，然后因为它的上下都是单调的，我们只需要求上下两条折线，基排然后单调栈即可。查询在这上面二分即可。

I. It’s All In The Mind

签到题。直接前两个填尽可能大的，后面填尽可能小的。

J. Join The Future

两问看起来不是一件事。

考虑这个相当于一个区间的xor，然后拆成前缀xor，建个图就彳亍了。如果有权值xor是奇数的环那就没救，否则每个连通块，确定了一个，剩下的就都确定了。

然后我们可以做字典序最小了。从前往后贪心，每次选择了一个就把整个连通块都确定了。但是这个并不能做方案数，因为我们考虑的是前缀xor，而前缀之间并不是独立的，换句话说，我们确定了前缀$p$的取值，并不能确定位置$p$的方案数，因为它受到前缀$p-1$的影响。

现在问题转化为，有一张图，每个点可以选0或者1，点$u$选0/1的方案数是$f(u,0/1)$，对于所有黑白染色的方案，求所有点$f$乘积之和。感觉上$f(u,0),f(u,1)$差不超过$1$的性质并没有什么用。

考虑一个强行想法，我们从前往后dp，然后记一下每个连通块编号最小的点有没有确定，如果确定了那么它的值是什么，这是三进制的，然后复杂度就是$O(3^n)$，看起来飞了。

注意到 编号最小的点有没有确定 没有记录的必要，因为我们是从前往后dp。复杂度变成了$O(2^nn)$，看起来还是不是很行。

注意到大小为$1$的连通块没有记录的必要，所以复杂度变成了$O(2^{\frac{n}{2}}n)$，看起来好像差不多了，但是因为有多测，还是不是很行。不过讲道理1e9是有可能冲过的?

然后百度了一下发现确实冲过了。但是我并不是很满足于这个结果。

考虑我们搞另一个复杂度也是$O(2^{\frac{n}{2}}n)$的做法，直接爆力枚举所有大小$>1$的连通块的结果，然后从左往右做一个线性的dp来决策大小是$1$的连通块。这个看起来要更快一些，毕竟空间是线性。

然后这两个做法看起来都不是很能优化，于是我就失败了。反正过了，那还是就过了吧（

K. Keep On Movin

看起来应该挺简单吧（

考虑这是构造回文串，所以有两个a和两个b的效果是一样的，但是有一个a一个b和有两个b的效果是不一样的，于是我们把所有字符尽可能变成a，现在除了a之外所有字符最多有一个。呃虽然我这么说，但是这题字符集不是小写字母（

因为要把所有字符用完，并且每个奇回文串只有一个字符是单着的，所以所有单着的字符我们都得给它一个串，然后剩下的就把所有a平均分配即可，当然优先分给偶回文串。所以这是签到题?

L. La Vie En Rose

看起来这个信息很局部。

考虑如果$n=m$怎么做，我们从左往右爆力扫，然后你惊喜发现这个信息足够局部，以至于我们可以记录上一个间隔换没换来dp。

考虑对于原问题，我们双指针扫长$m$的子串，双栈代替队列来维护一下，也就是枚举中间那个断点是否被选了，然后两边dp。复杂度是线性。

M. Memento Mori

首先我们可以删去没有$1$的行列而不影响答案，这样复杂度只跟$k$相关了。

考虑$(p_i-p_j)(c_i-c_j)>0$说的是啥，看起来这个说的是$[p_i>p_j]=[c_i>c_j]$，然后对于任意$i,j$都满足的话，看起来说的是$c$离散化之后和$p$相同。

这个判定看起来非常不好，于是我们大胆猜测包含四个1的极小子矩形个数只有$O(k^2)$。枚举了几个扫描线方向，你发现我们可以这么做，枚举哪个点贡献了上边界，哪个点贡献了下边界，那么最多只有四个可行的子矩形，于是这样的子矩形确实只有$O(k^2)$个。要找到它们，从下往上扫，维护上边界下面所有点按列排序的结果，然后双指针扫这个结果和这一行的点，再把这一行归并进去，复杂度$O(k^2)$，空间是线性。

D3

好像是sxyz出的?

我们班的团支书(不是OIer)的绰号就是Bo，因为他的名字有一个Bo字（

A. Sqrt Bo

注意到好像超过unsigned int的都无解，于是连高精都不用写。

B. Permutation Bo

拿这个题讲一讲期望的线性性（

根据期望的线性性拆开每个位置。也就是说

中间的概率应该是$\frac{1}{3}$，边上是$\frac{1}{2}$，于是直接做就行了。为什么$n\leq 1000$呢?

C. Life Winner Bo

对每种dp一遍，前缀和优化就行了。应该出到1e9/fn

D. Gambler Bo

这玩意是个lights out游戏，于是我们还是主元法，设出第一行然后递推出最后一行，然后高消最后一行。复杂度是$O(n^3)$。所以出题人拉了，居然没有听说过lights out（

E. Boss Bo

ancient/jy

这个ban掉一些子树的话，每个子树是一个区间，于是我们得到最多$k+1$个区间，然后对于sum我们就差分成前缀然后扫描线静态lct或者树剖BiT(这个是不是经典做法?求点到集合的lca深度和，就是把集合每个点到根的链+1，然后查询那个点到根的链和)，对于max和min看起来要分治多$\log$，但是实际上很有性质，min的话就是往上跳到第一个good node，max的话必然在直径端点取到，可以用合并直径的trick。

sum用静态lct是一个$\log$，min的话是线性，max直接对dfs序分治看起来是$O(n\log n)-O(1)$。总共是一个$\log$。

跟dwt讨论了一下，dwt给出了sum和max的二维数点俩$\log$做法，然后我们一致感觉这个静态lct和合并直径是难以省掉的。

F. Product Bo

原来已经帮你取好对数了（

注意到如果$\binom{l}{m}\geq k$，那么只有前$l$个是有用的。

考虑爆力扩展，我们一次会有$m$种扩展方式，如果$m$很大的话，比如$m>10$，那么$l$就会很小，算一算可以知道$m=10,k=2\times 10^5$的时候$l=21$，直接搜就行了。如果$m$超过了$\frac{2}{n}$，那么我们可以转而找选$n-m$个的第$k$小。不会分析复杂度（

G. Explorer Bo

注意题意是，不能上一次传送之后走过的所有边，而不是只有上一条。要最小化传送次数，然后最小化距离。

如果有$c$个叶子，那么我们每次传送前可以干掉两个叶子，于是需要$\lceil\frac{c}{2}\rceil-1$次。看起来需要讨论奇偶性。

如果有偶数个叶子，那么每一次都需要选两个叶子，否则可以有一次选随便一个点和一个叶子。考虑直接dp，我们选择一个叶子当根，设$dp(u)$表示$u$子树和$u$的父边都被覆盖了的最小代价。但是不一定只扔一条边上去啊?所以我们就失败了。

呃没有失败。猜测可以只扔最多两条边就行了，然后这看起来非常对，因为不会出现一棵子树没有叶子的情况。感觉上选什么点当根都是可以的。

H. Gardener Bo

第一个在bfs序上是三个区间。第二个是相当于子树点权和乘上子树点数，然后减去儿子们的子树点权和乘上子树点数，子树点数不变，点权和容易维护，然后儿子们在bfs序上是一个区间，所以线段树即可。

I. Palindrome Bo

这个问题不知道是不是强于最长回文子序列，感觉应该是不弱的。最长回文子序列可以转化成和反串的lcs，所以可以上经典bitset优化除掉一个$w$。

直接dp是$O(n^3)$的。扫值域，这玩意转移是个单点修改2-side查询max，可以分治扫描线BiT做到$O(n^2\log^2 n)$，看起来不是很有前途。写一下式子吧。

感觉了一下你发现这个东西可能满足四边形不等式，但是再感觉一下，好像它的不等号是反的。

外层从左往右扫$j$，内层扫$i$，你发现对于每个数值只有一个区间可能有效，所以可能的转移的变化量只有$O(n)$，然后如果从右往左扫$i$的话是只增不减的，于是随便维护一下就做完了。

J. Rower Bo

好像是高一上数学课本里的题（

K. Teacher Bo

看起来是找到$i,j,k,l$使得$\vert a_i-a_j\vert+\vert b_i-b_j\vert=\vert a_k-a_l\vert+\vert b_k-b_l\vert$。

考虑在左边的点处统计一对，如果横坐标相同就胡乱钦点一个顺序。现在问题是我们需要什么样的信息才能判断两个集合有没有交，并且这个信息需要可以快速的平移和合并。

只能想到hash。看起来hash并不能判交。

然后另一个简单想法是法法塔求出每个距离有多少对点。想到这个之后问题突然变得简单了，因为一共有$\frac{n(n-1)}{2}$对点，距离都在$2m$以内，所以如果$\frac{n(n-1)}{2}>2m$必然有解，我们只需要保留前面$O(\sqrt{m})$个爆力就行了。

D4

A. Another Meaning

能否解释清楚题意/fn

看起来是说，给你两个串A和B，你可以在A中选择若干个不交的B，求有多少种选择方案。

那这个是不是简简单单啊!kmp求出每个位置是否匹配，然后直接dp，前缀和优化即可。

B. After a Sleepless Night

看起来非常离谱。

考虑先枚举一个点作为根，那么此时所有叶子(不包括根)的值肯定是自己，如果有冲突就完蛋了；剥掉所有叶子，我们统计每个点的子树$\max$，如果它的值已经是子树$\max$，它的值只要比这个小就行，否则它的值也确定了。这样所有点的权值要么已经确定了，要么在一个值域前缀中，可以直接分配过去。

然后实际上我们不需要枚举一个点作为根，因为值最大的点必然构成一条链，而这条链的端点中必然有一个是根。做完了。

C. Bonds

注意到一个极小割总是把图分成两个连通块，否则我们加一条边一定可以减少一个连通块。于是爆力枚举$1$所在的，然后算一算，就是$O(2^nn^2)$。但是这个算出来有1e9，不是很好过。

可以打一个标记然后拿法嘛塔推一下，也就是$f(S)$表示$S$到$V-S$是不是一个极小割，然后对于一条边$u\leftrightarrow v$，我们要求的就是$\sum\limits_{u\in S,v\not\in S}f(S)$。然后这个可以容斥一下，主要问题是算$u\in S,v\in S$的情况，然后这个就是法嘛塔子集后缀和，复杂度是$O(2^nn)$。

D. Filling

直接状压dp，然后有的方式会算四次，有的方式会算两次，有的方式只会算一次，上个burnside钦点一下就行了。

E. Lucky7

容斥，crt。

F. Substring

计算每个字符作为最后一个X的子串数量。

G. Treasure

treasure居然可以有负的价值/jy

然后看了一眼是简单路径啊/jy

考虑我们怎么$n^2$，你发现直接做就是$n^2$。

考虑怎么直接找到一个最牛逼的起点。你发现难度很大。

考虑每个宝藏的贡献，然后你发现它贡献$O(1)$个矩形，也就是起点要在以它为根钥匙所在的点的子树中，终点要在以它为根除了钥匙所在点所在子树以外的点中。然后直接搞就行了。

H. Turn Game

dp of dp。我以前尝试把dp of dp归结于用dfa判定，然后在dfa上走，做这个题的时候我觉得这个不是个dfa，但是这他妈显然是dfa。

考虑怎么解决判定问题。要判定一个情况是否可行，我们可以求出搞出它的最小步数。轮廓线，设$dp(i,j,S,0/1)$表示考虑到$(i,j)$，轮廓线上$S$中的位置被一个行的反转覆盖了，$(i,j)$有/没有被一个列的反转覆盖(这些表示这些反转是否可以延申到未决策的区域)，是否有可能，状态数是$O(2^nnm)$。转移枚举下一个位置是被行还是列覆盖了，然后就可以记搜或者刷表。如果$dp(n,m)\leq k$那就可以。

于是设$dp(i,j,S,0/1,k)$表示上面那个dp中$dp(i,j,S,0/1)=k$的情况有多少种。直接做就行了，复杂度是$O(2^nn^2m^2)$，随便过。

可以看一看我新发的 dp of dp。我觉得写的还可以（强行推销

I. String problem

意思是，一个0~9的数字组成的串，你要选一些字符，一种字符第一次选花费$b_i$，之后每一次花费$a_i$，保证$b_i\geq a_i$。然后同时选两个位置会有一个非负的价值，求价值减去花费的最大值。

最大权闭合子图。要获得一个价值，你需要选择两个位置，要选择一个位置，你需要选择一种字符。选择一种字符的代价是$b_i-a_i$，然后每选择一个字符的代价是$a_i$，然后就跑就行了。复杂度是$O(n^6)$(实际上应该可以分析到更低，并且完全跑不满)。

能否类似于 最大获利 建一个只有$O(n)$个点的图?想一想怎么才能转化成 最大获利，你发现我们给每种字符再建一个点，一种字符向它的出现位置连边，边权是$\infty$。选择一个位置需要支付$a_i+\infty$，然后选择一种字符需要支付$b_i-a_i$。看起来就可以了。这里我们肯定需要一个$\infty$来强制选$b_i-a_i$，但是这个感觉还是有点艺术。

J. The All-purpose Zero

看起来直接dp强行维护就好了。从左往右扫，设$dp(i,j)$表示结尾于前$i$个，结尾的值$<j$的lis，转移考虑新加入一个值会发生什么，如果加入一个$0$那就是向上平移并全局$+1$，如果加入一个$x$那就推平一段，平衡树即可。

然后看起来并不需要这么恶心。考虑存在一个最优解把每个$0$都用了，因为如果没有都用可以把一个换成$0$而不会变劣，这个跟刚才那个dp中加入$0$的情况的正确性是一样的。于是我们先把所有$0$都用了，那么在$0$之间需要选一些东西串起来。然后你发现我们可以求一个不包含$0$的lis，并要求不能把$0$挤出去，也就是说如果lis中两个数之间隔了$k$个$0$，那么两个数的差也要$>k$。给每个数减去前面$0$的个数就行了。

K. Where Amazing Happens

模拟。

L. Bubble Sort

每个数一定是先往右再往左。右边有多少比它小的，它就会先往右移动多少次，然后它会一直往左移动到正确位置。这个是不是随几组观察一下也可以看出来（

D5

A. ATM Mechine

我们取出$x$元之后，就递归到$(k-x,w)$，如果取不出来就递归到$(x-1,w-1)$。

考虑dp，我们枚举在哪问了一次，然后这玩意有决策单调性，也就是说$k$越大，最优决策点也越大，对每个$w$进行分治即可。但是感觉不一定能过啊（

优化一下，注意到如果$w$很小我们可以直接这么做，如果$w$超过了$\log$级别，那么实际上根本不会把$w$用完，只需要降到$\log$级别。所以复杂度只有$O(k\log^2 k)$。

B. Cycle

我们要快速查询一个串的一个前缀的最小表示的开始位置，剩下的就可以hash了。然后这个可以随便sa一下。

但是我不会写sa啊?没关系的，sa就是st的dfs序。

另外kmp可以直接做循环同构判定，方法是直接转着匹配。

有一个牛逼做法。考虑要判定$s,t$是否循环同构，我们拿着$t$在$s$中跑一遍kmp(而不是转着跑)，设匹配到$s$结尾的时候，匹配了的$t$的前缀是$u$，并设$t=u+v$，那么结论是，如果$s,t$循环同构，必有$s=v+u$。证明也很简单，如果匹配不到$s$的结尾，那么它俩显然不循环同构。

所以我们直接做，剩下的部分就是hash一下看看$v$了。

C. Divide the Sequence

考虑dp，注意到每个位置只会从前面第一个可以转移的位置转移，因为如果$i$同时可以从$j,k$转移，那么把$j+1,…,i$拆分成$j+1,…,k$和$k+1,…,i$两段显然更优。然后就从最后开始爆力往前找就行了。

D. How Many Triangles

锐角三角形/jy

三个角都是锐角，看起来就不如恰好一个角不是锐角性质好。考虑我们枚举那个角的顶点，然后再枚举另一个点，就变成半平面数点了。然后就每个点排个极角序，在上面三指针就行了。

然后要优化到$n^2$，看起来需要基排。感觉上这玩意是不是经典的啊（

坐标范围是$v$的话，任意两个点的极角(差的$\frac{\mathrm{atan2}(x,y)}{\pi}$)差不超过$\frac{1}{v}$级别，于是我们只需要比较到$\frac{1}{v}$级别，而$v=n^{O(1)}$。

E. Interesting

考虑我们处理每个位置作为左端点的回文子串的右端点之和，以及每个位置作为右端点的回文子串的左端点之和。

看起来manacher就行了。要支持给一个区间加上一个公差为$\pm 1$的等差数列，这看起来是经典问题，差分一下扫描线扫过去就行了，或者你可能会认为它是一种前缀和。

F. Interval

考虑莫反。

然后这个东西看起来就简简单单了，问题变成计算全部被$d$整除的区间个数。1e5以内最大的因数个数只有少的可怜的128，所以我们可以爆力枚举一个$d$，然后让每个数把它塞到它的因数这样的，这部分只有$O(nd(n))$。

把$d$的倍数记为0，不是的记为1，问题就是求全1区间的个数。每个序列内部的部分是简单的，而序列之间的部分只和这个序列是不是全1，以及左右极长连续1的长度有关。考虑计算某个序列(可能全1)右边极长连续1中一个位置作为跨序列全1区间左端点的次数，我们考虑右端点可能的位置，它可能在任何一个序列的左边极长连续1中，或者在一个全1序列中。如果它在一个序列的左边极长连续1中，那么中间需要拼若干个全1序列(可以不拼)，但是不能拼有0的序列；在一个全1序列中同理。

考虑这个跨序列的答案具体怎么算。我们枚举左右端点是在全1序列还是不在，设有$c$个全1序列，它们的长度和是$s$，非全1序列左边极长连续1长度和是$s_l$，右边是$s_r$，那么以左右端点都在非全1序列为例。我们枚举这么两个端点的方案数是$s_ls_r$，然后需要选择一些全1序列塞到中间，选完之后剩下的随便排，方案数是$\sum_{i=0}^c\binom{c}{i}i!(m-i)!$。剩下的看起来是一样的。

G. K-wolf Number

强行数位dp，记前面四位。

H. Level Up

每个人的工资只有三种可能，也就是改了一次之后中位数移动了一位，变成了100000，或者没有变化。第一种情况是，如果改的在子树中，并且改的数要比原来的中位数小，那么就会移动一位这样的，然后它看起来就是矩形加全局$\max$，先用个数据结构比如静态链分治对顶堆，或者主席树区间kth求每个子树的中位数，然后扫描线BiT即可。

I. Permutation

google生草机直接给我来个反转对数（实际上是逆序对数

$n$居然只有50。考虑我们求每一对逆序对出现多少次。

我们从儿子到父亲连边，表示儿子要在父亲前面。对于这个逆序对，我们从前面的那个到后面的那个连边，表示前面的需要在后面的前面。注意到这个东西和树只差一条边，如果边是无向的，它就是基环树，但是这个并不是有向基环树，它显然不可能成环。另外这个看起来是个拓扑序计数。

考虑这个环的形态，看起来它必然是两条首尾相同的链，不妨称为左边的链和右边的链，那么实际上我们要做的就是把中间的部分归并起来。只考虑环的lca的子树，子树之外的点直接归并一下就行了。设$dp(i,j)$表示两条链分别搞到了$i,j$两个点的方案数，我们枚举下一次加入哪边的点，然后把它的子树归并进来。做完了，复杂度看起来是$O(n^4)$。

todo : 等hdu活了实现一下。

J. Prefix

hash一下，或者拿个trie离散化，然后变成强制在线区间数颜色，主席树即可。

K. Two

让我想起拟阵交（

我们同时在两个串的子序列自动机上跑，设$dp(i,j)$表示在第一个串上跑到$i$，第二个串上跑到$j$的方案数，转移枚举下一个字符进行刷表。复杂度$O(nm\Sigma)$。

L. World is Exploding

这看起来就是强行出题（

考虑如果没有$a\neq b\neq c\neq d$(呃注意这个限制其实是两两不同)，我们求出顺序对和逆序对一乘就好了。如果有，我们容斥，然后在相等的那里统计贡献。总之都是两个BiT就做完了。

D6

A. A Boring Question

所有不单增的都是$0$，于是只需要计算单增的。

然后发现这玩意是把$n$个有标号球分配进$m$个有标号盒子，可以有球不放的方案数，那个枚举就是枚举盒子放的球个数的前缀和序列，然后用组合数选出来每个盒子放多少，于是答案就是$(m+1)^n$，快速幂即可。

但是看了一眼样例，感觉不对啊?

注意到我们是不会尝试选出最右边的盒子有哪些球的，也就是说刚才的转化是错的，实际上我们需要枚举实际上选了多少球，答案是$\sum_{i=0}^n m^n=\frac{1-m^{n+1}}{1-m}$。

B. A Simple Chess

看起来这是个马。

然后如果直接算一个点到另一个点的方案数看起来是简单的，直接求出两种步数然后组合数选一选就行了，注意到模数很小所以可以lucas。然后考虑经典容斥，我们计算有多少经过障碍的路径，然后爆力dp即可。

C. A Simple Nim

打表一下sg值，你发现sg值的序列几乎是1,2,3,…，不过$x\bmod{8}=7,0$的相邻两项互换了。于是我们可以$O(1)$计算它。

D. Bitset Master Magic Number

不要出让人难以理解题意的题啊/yun

这玩意看起来不是很能直接bitset，因为有20组多测。

第一段代码说的是，$b_i$是由$a_{i,j}=1$的$b_j$们and起来再xor上$2^i$得到的。注意到因为$a_i$只有$i$位，那个$\operatorname{xor}2^i$等价于$+2^i$。

第二段代码说的是，每次查询一些$b_j$ or起来的结果。

然后我们就不会了。考虑那个$b$是否有什么组合意义?

什么时候我们会用到一个01矩阵?感觉上只有邻接矩阵和高消的时候。这个看起来并不像是消元，于是考虑前者，你发现它的意思是，不管怎么走到任意一个没有出度的点，都会经过的点。那么查询就是查询哪些点是被给出的点之一必然走到的。

这个看起来就是，把没有出度的点用一个虚点穿起来，然后每个点到这个虚点的支配点。建立支配树，查询的时候建个虚树在上面跑就行了。

一眼看出支配树，然后看反了，想着从没有出度的点走到每个点/yun。实际上因为没有出度的点总是那些，所以我们可以建一个虚点把它们串起来。

Bitset Master是gp of zhejiang的一道点分治题。题面第一句成为了经典 : 在中国，$n^2$可以轻松过1e6。

E. Master Zhu

每个格子都有一个棋子和它同行或者同列，这个就让人想起某个经典套路。给行列建两排点，格子是连接所在行列的边，那么一个格子有一个棋子和它同行或者同列，就相当于它的端点有至少一个被选了一条邻边，于是这就是二分图最小点覆盖。跑即可。

复习一下，最小点覆盖=最小割=最大流=最大匹配。

F. Stabilization

看起来还挺有趣。

差是位独立的，但是差的绝对值不是。所以我们需要把差的绝对值化成差。

注意到$a_i\operatorname{xor}x,a_{i+1}\operatorname{xor}x$的大小关系，只和$x$在$a_i,a_{i+1}$的最高不同位上的值有关。于是问题变得简单起来。

考虑对于一对$a_i,a_{i+1}$，我们求出它们的最高不同位$k$，然后第$k$位是$0$的$x$会得到一个比如$a_i\operatorname{xor}x-a_{i+1}\operatorname{xor}x$的贡献，第$k$位是$1$则反过来。把这个贡献直接拆到每一位，然后直接统计答案，复杂度就是$O(n\log v)$。

G. This world need more Zhu

查询1看起来是简单的，直接离线静态链分治，启发式合并一个桶即可。

查询2看起来是复杂的，不过可以树莫队秒掉。

H. To My Girlfriend

我去，我也想要这样的girlfriend/jy

不过这个题看起来还是挺就这的。

注意到一个选了$t$个物品的方案会贡献$\binom{t}{2}\binom{n-t}{2}=\frac{t(t-1)(n-t)(n-t-1)}{4}$次，然后我们直接拆成一车东西强行dp就行了。

还是具体一点吧。这个式子先乘个$4$最后除掉，拆开得到$(t^2-t)(t^2-(2n+1)t+(n^2-n))=t^4-(2n+2)t^3+(n^2+n+1)t^2+(n^2-n)t$。看起来只需要维护所有方案的$t^4$的和，$t^3$的和，$t^2$的和和$t$的和，转移就二项式定理展开$(t+1)^k$然后硬转移就行了。复杂度$O(ns)$。

这个题也可以直接组合意义，因为那个贡献就是在选了的中钦点两个，不选的中钦点两个的方案数。

I. Up Sky,Mr.Zhu

先跑个manacher，如果我们得到了匹配的位置，一个右半串有贡献当且仅当然后拿着$t$在sam上跑，相当于一个parent树的子树中二维数点。分治扫描线BiT就是俩$\log$了。

但是这个并不能让人满意。注意到$\vert t\vert\leq 10$，我们可以爆力找到所有长度$\leq 10$的子串然后hash，然后就避免sam了。但是这样看起来是$O(10n\log n)$，还是不好过。

考虑使用pam匹配一下这个半串(只有板子题才能用pam的匹配功能?)，然后直接线段树合并endpos就行了。

不过我有可能没有理解题意，不过pam必然可以做这个。

J. Windows 10

往上走显然是一直up，往下走就需要考虑一下了。

注意到up只能up一下，而down看起来是花$k$次down掉$2^k-1$，看起来down非常快。

如果我们什么时候把音量down的比$q$低了，那么就需要一直up。然后有的up可以塞到down的中间去，所以我们枚举down了多少轮，如果down了$k$轮，那么看起来在前$k-1$轮我们会尽可能down而不让音量比$q$低，在第$k$轮则会把音量down的比$q$低的尽可能少(包括少$0$)。模拟即可。

K. Zhu’s Math Problem

一个想法是，猜测它是关于ABCD的多项式，于是可以插一插。但是感觉不是很有可能成功。

注意到这两个式子的区别是把$c,d$交换，也就是说$a$加上其中一个总是比$b$加上另一个更大，也就是说$a$比$b$大足够多。

考虑我们化成$a-b>d-c,a-b\geq c-d$，那么它就等价于$a-b\geq\max(d-c+1,c-d)$，它看起来就像是一个绝对值。考虑我们统计$a-b\geq\vert c-d\vert$，然后减去$a-b=\vert c-d\vert,c>d$。

然后发现了问题，由于有四个限制，这个东西看起来分了不少段，并不容易讨论。还是比较的见鬼。

题解非常的牛逼。考虑数位dp，我们直接对$a+c-b-d,a+d-c-b$的二进制从高到低dp。注意到退位只会退上一位少于$2$，也就是说前面的数值达到了$2$那这个差就必然$>0$；同理，如果前面比$-2$要小，那么这个差必然$<0$。所以设$dp(i,j,k,lim)$表示考虑到第$i$位，这一位往上看两个式子的值分别是$j,k$(如果$>2$则认为是$2$)，每个数有/没有顶着上限。转移枚举四个数下一位选什么，然后算一算就彳亍了。

D7

讲道理，题目名首字母和题号相同还是很爽的（

难度骤增?

A. Ants

这玩意看起来是个内向基环树。

如果两条边在端点之外相交了，那么看起来就很不对。换一下目的地可以得到更小的和，于是必然有一个老哥走错了。

于是我们搞个kdt查一下最近点建出这个内向基环树森林，然后两个点如果相遇，相遇位置是确定的。先判断两个点是不是在环的同一棵子树，如果是那就直接求个lca，如果不是，这个相遇位置就是离环更远的那个点第一次跳到环上的位置。算一下距离，然后看时间是否相等即可。

但是这个做法是有问题的，因为如果是二元环，那么两只蚂蚁只要走到了这个二元环上，总有一个时刻方向相反并且相遇了。进一步注意到，所有的环都是二元环，这个是不是经典结论啊/jk

所以实际上就是判断是不是在一个连通块。加边，加边，加边，然后并查集查询即可。

B. Balls and Boxes

数学题还是却死吧。

C. Colosseo

看起来这个powerful指的是它是一条链，或者说没有环。容易判定这个。

考虑我们相当于要找一个最大的包含T1的子图使得其中没有环。

注意到T2中每个点只有可能放在T1中的最多一个位置，如果可以放在两个位置那就已经形成了一个环。

现在问题是我们要选择哪些点。

结论是，选一个点的序列，使得它在T2中的位置和嵌入T1的位置都是递增的即可，也就是一个lis。容易证明这么做是对的。但是为什么我考虑了半天网络流（

D. Distance

每个数只有$\log$个维度非零，并且总和也只有$\log$。

考虑我们先除再乘，让每个数贡献到所有因数，然后查询的时候枚举因数统计答案。由于有删除，我们需要开一个堆或者时间分治一下，复杂度是$O(qd(v)\log q)$，而$d(10^6)=240$，看起来很是不稳。

然后注意到不需要开堆，我们可以直接开桶。但是还是很慢。可以本机跑一下，1e6以内最大的高合成数是720720，不开O2要跑足足2.3s。不开O2应该接近hduoj速度吧（

注意到修改是$O(d(v))$而查询是$O(d(v)\log v)$，并且跑一下3e5次修改你会发现飞快。考虑我们怎么砍这个$\log$，容易想到搞一个压位，然后就做完了。

E. Elegant Construction

没有出度当且仅当$a_i=0$，$a_i$最大的必然是没有入度的点之一。

考虑一个牛逼构造，我们直接找到一个$a=0$的点，然后每个$a\neq 0$的点都连向它，然后这些点的$a$都$-1$。这样可以尽可能快地把点变成零度点。

F. Find the Period

模板 子串周期查询。

有没有什么乱搞啊!

G. Golden Week

一开始考虑了差分约束，然后发现读错题（

注意到是可能会扔掉一些人的。比如有个老哥只走一条边，但是他出价1e9，那是不是必然给他满上啊（

考虑一个牛逼做法，我们直接dp，设$dp(u,i)$表示$u$到根的链的和是$i$，终点在$u$子树内的链的最大收益。转移枚举到每个儿子的边，看起来是$dp(u,i)=c(u,i)i+\sum\limits_{v\in\mathrm{ch(u)}}\max\limits_{j\geq i}dp(v,j)$，其中$c(u,i)$表示终点在$u$，预算至少是$i$的链的数量。注意到这个$i$必然是一条链的预算，于是我们就$O(nm)$了。

一开始没有想到这个，是因为尝试走一步就计算一条边的贡献了。实际上因为我们不知道一条链到底要不要选，最好的方法是在终点处决策整条链。同时这个题是自底向上的，也就是说选择一条链实际上给出了对上面的一个限制。

H. Hearthstone

dp，设$dp(i,j)$表示你抽了$i$张，其中$j$张是A的概率，那么可以求出最后拿到每个数量的B的概率。然后背包一下用每个数量的B能赢的概率即可。

好像官方做法没有注意到拿到任何一种B的概率是一样的，所以复杂度是指数级的。

I. Ice Walls

走的路径一定是若干线段，并且每一条一定是连接两个特殊点，特殊点可以是墙的端点或者起点和终点。问题变成判断一条线段和多少墙相交，上个板子即可。然后跑不带堆优化的dij，复杂度$O(n^3)$。

据说前面这个可以优化，毕竟$n^3$次线段交不是很好办。可以扫描线BiT，比如我们先考虑点A往上方发射的线段，从下往上扫这些墙和特殊点，每个墙覆盖了一个极角区间，然后相当于一个区间加单点查询，先扫过去得到所有这些东西，把它们离散化再扫一遍用BiT维护。复杂度$O(n^2\log n)$。

J. Joint Stacks

可并堆。最好写的是启发式合并priority_queue，当然skew heap真的牛逼。

然而实际上不需要可并堆。当把B合并到A的时候，可以并不真的合并，而是把它移动到一个A’的前面，然后每次弹A的时候看A和A’的栈顶哪个更晚。

K. Knights

考虑这个一个人打完了之后继续往前走，另一个出局就很不可控。考虑我们猜一个结论，让两个人不要一个走下去一个出局，而是都走下去，但是每个人只剩下50%的出现概率。两个出现概率分别为$p,q$的骑士交战，会变成出现概率分别为$p(1-q)+\frac{pq}{2},q(1-p)+\frac{pq}{2}$的骑士。我们模拟一下，然后$n$跟一个骑士交战之后就把那个骑士删掉，最后$n$的出现概率就是他的胜率。

我不知道这个对不对啊（

upd : 我现在觉得它是不对的。

正常做法是dp。考虑一个人的胜率只和他打的架数有关。$n$会往左冲，收割掉所有遇到的时候还没被打败的人，我们需要求出他收每个人数的概率。

由于每个老哥走的速度是一样的，$n$在往左走和$n$站着不动是一样的，因为反向的站着也会自己过来，同向的去追也追不上，只能等他转向。

考虑设$dp(i,j)$表示前$i$个人中有$j$个人往右飞出去的概率。转移考虑如果第$i$个人上来就往右，他肯定会往右飞出去。如果他上来就往左，那么考虑前$i-1$个人有多少个往右，如果有$k$个，那么就有$\frac{1}{2^{j-k+1}}$的概率被他收走恰好变成$j$个，或者如果$j=1$，他也可能全收了自己撞到墙再回来。现在转移是$O(n)$的，要优化也很简单，对$2^jdp(i,j)$做前缀和即可，不过更牛逼的方法是发现它和$\frac{dp(i,j+1)}{2}$只差一项。

L. Lights

如果两个灯在同一行或者同一列，我们就并查集合并。如果所有点都在一个连通块就行，否则就不行。

D8

草，怎么是学车的题（

学车是数数专长（

G~K的出题人是 中二病也要谈恋爱 的粉丝/jy

A. Ball

一开始考虑了网络流，然后发现这个是个多物品流，看起来不是很行。

注意到因为是重排区间，每个球要从哪到哪是确定的，也就是说颜色为$1$的球，肯定是$a$中第一个换到$b$中第一个，$a$中第二个换到$b$中第二个，如果有交叉那么显然可以不交叉。

然后就可以猜一手，我们每次重排一定是把目标位置靠前的排在前面。模拟即可。想了一年才想到这个/fn

可以出到1e5。

B. color

有 色 图

我一开始以为是数所有的基环树，没想到是给你一棵基环树/qd

考虑这个同构肯定是绕着环转，那么我们就上一个polya，问题是什么样的转是可行的。结论是，每一种同构都是一个旋转复合一个翻转，这里的旋转可以是不旋转，翻转也可以是不翻转。我们跑出每棵子树的hash值，然后我们破环成链正反跑两遍kmp找到所有可行的转。然后就随手polya掉了，正叔的指出具体了一点，前缀和一下，并快速幂即可。

复习一下 : burnside定理指出，不同的染色数等于各置换作用下不动点数的平均值。polya定理指出，一个置换下的不动点数，就是每个置换环随便选一个颜色。

C. color II

如果只求一次，我们可以状压dp。设$dp(i,S)$表示用$i$种颜色已经染了$S$中的点，是否可行。每次选择一个独立集塞进去就行了。复杂度是$O(3^nn)$，但是由于独立集不会很多，所以跑的应该飞快。

然后发现这个dp可以同时把所有子集求出来。于是结束了。

当然可以优化。考虑每一层转移都是一个子集卷积，卷就行了。复杂度$O(2^nn^3)$。

更好的做法是，我们不需要使用子集卷积，可以直接用并卷积，因为把之前的颜色覆盖了只会让方案变劣，而不会把答案算错。复杂度是$O(2^nn^2)$。

D. graph

注意是有标号的。

考虑把森林(带有题目中给的权值)和不包含树的任意图卷起来。后者好说，我们随便加边，取个ln得到连通图，然后减去树，然后取个exp得到不包含树的任意图。问题是怎么算前者。设非空树是$F$，那么我们要算

然后拉个板子爆算复合就行了。当然这个东西并不能让我们满意。

考虑求个导试试。

这个形式看起来很好。把那个复合扔进去，我们得到

，然后这是一个线性微分方程，两边提取系数得到递推式，法法塔算出右边就做完了。复杂度是$O(nk(k+\log n))$。

网上有篇题解好像有一个看起来很像的做法，不过他没有二项式定理硬展，而是直接得到了一个从$A_{k-1}^\prime$到$A_k$的式子，看起来比我这个牛逼多了。可惜他LaTeX挂了一半。

E. permu

搜。然后可以得到一个图，问题是这个图上的对数。

容易感觉到在一般的dag上这个问题是做不了的，所以我们需要一些牛逼性质。

猜一手，如果一个排列的逆序对包含另一个排列，那么它必然可以操作成那另一个。

但是可能的逆序对有36对，我们并不能跑一个法嘛塔。不过这个可以做$n\leq 7$。但是爆力也能做$n\leq 7$啊?

然后就不会了。拉了。

做法非常牛逼。考虑一般的dag不能做，是因为两个点之间的路径可能不唯一。

考虑一个看起来还比较自然的想法，我们每次确定一位，这样方案就唯一了。如果需要把$a_j<a_i$换到$a_i$，如果$j<i$那就没救了，否则我们可以直接换，但是这样做可能会丢解。

考虑怎么做才不会丢解，显然是尽可能把大的放在前面，小的放在后面，不过麻烦的是我们也不知道什么是大的什么是小的。

把$a_j$换到位置$i$的过程是把它顺着某一串东西换过来(此外的交换可以放到后面进行)。然后就可以进行一个结论的猜，并进行一个结论的证。

结论 最优交换方案是，从$i$向右找到所有$>a_j$的前缀$\min$，然后把$a_j$沿着这一串换到$i$。

比如现在有5 4 1 2 3，我们要把3换到第一位，那么从第一位出发所有的前缀min是4 1，于是我们做交换5 4 1 2 3->5 4 3 2 1->5 3 4 2 1->3 5 4 2 1。

证明 如果我们选的不是这个序列，可以尝试证明选的是这个序列加上/删掉一项的情况，你会发现都可以在之后的交换中被这个替代。具体证明略（

这应该算是一道构造题吧（

这就搬给小朋友。

放上我的代码吧。为了搞的好像全是题解的篇幅所以放link了（

这个题被搬到了sdfzoj contest0。

F. physics

先解一下那个微分方程$v(t)v^\prime(t)=c$，这玩意看起来非常简单。

然后我们代入初速度解一下这个$C$就好了。接下来每个球的速度都是一个这样的东西，然后我们就需要理解一下完全弹性碰撞。百度一下，你发现两个质量相等的物体完全弹性碰撞后，速度会交换。然后让你求速度的kth，那这个完全弹性碰撞有啥用（

然后你发现一开始的kth就是最后的kth，所以就算就行了。这什么鬼题（

G. Rikka with Parenthesis

结论比较简单，必然可以只操作不超过两次。方法是考虑匹配之后剩下的东西，必然是一些右括号然后一些左括号，我们把左括号全翻了，然后翻右边一半当右括号就行了，如果你不理解，那么你可以注意一下合法的翻完还是合法的。也有可以只操作一次的，也就是匹配之后只剩下左括号或者只剩下右括号的。

我们可以数不用操作的，它就是卡特兰数；可以数只操作一次的，翻折法搞一搞就好了；剩下的就是操作两次的。

H. Rikka with Sequence

吉老师线段树。开根的时候，如果区间全都一样了那就打一个标记，否则递归下去。

复杂度看起来不是很好分析，我们可以大力猜测它是$O(n\log n\log\log v)$。注意到1和1e9，都加上一个巨大的数并开根，比直接开根，相接近的速度会更快。所以我们设势能是所有相邻两个数变得相同需要的开根次数，那么每次区间加只会改变端点的势能，中间的势能反而会降低。

感谢 CCCCOrz 的教导。

I. Rikka with Subset

先排序。

考虑一个数贡献多少次，你发现如果有$c\geq k$个数比它大，那么这些数里面只能选不超过$k-1$个，剩下的数可以随便选，方案数是$\sum\limits_{j=0}^{\min(c,k-1)}\binom{c}{j}2^{n-c-1}$。答案就是

。后面是组合数行前缀和，看起来很不可算。容易想到法法塔，我们把它写成gf。在前面选$j$个，会贡献到所有的$k>j$，这些看起来就是$\frac{z^{j+1}}{1-z}$。我们得到

这提醒我们先做差分，最后前缀和。问题变成算

这个是不是大家都会算了（，它是$a_i2^{n-i}(i-1)!$和$\frac{1}{i!}$的差卷积，一个差卷积板子拍上去即可。

J. Rikka with Subset II

枚举这个子集直径的中点，从它出发bfs然后容斥一下。

K. Rikka with Parenthesis II

看起来比G简单了不少。从左往右找到第一个右括号，从右往左找到第一个左括号，然后把它俩换一下。

如果G是每次可以反转一个，应该怎么做?

考虑一个经典结论，什么样的右括号必然剩下?你发现把左右括号看成1和-1，前缀和为严格前缀$\min$(并且$<0$)的地方的右括号会剩下。同理，后缀和为严格后缀$\max$(并且$>0$)的地方的左括号会剩下。注意到整个序列的和是一定的，所以前缀和取到$\min$的时候，它的补取到后缀和的$\max$，所以所有前缀和严格前缀$\min$在所有后缀和严格后缀$\max$的左边，这两部分之间看起来很独立。

然后注意到我是智障，因为这个序列是$\pm 1$，所以前缀和的全局$\min$就是前缀和严格前缀$\min$个数，后缀是一样的。答案是后缀和的全局$\max$减去前缀和的全局$\min$，再除以$2$，构造是剩下的一定是))))))))((((((((这样的，我们反转左边的前一半和右边的后一半。

考虑折线。现在要计算$k$的答案$f(k)$，枚举前缀和的全局$\min$的绝对值，设为$a$，那么后缀和的全局$\max$就应该是$k-a$。枚举这个前缀的位置$i$，那么左半边相当于我们从$(0,0)$出发，每一步可以往右上或左上走，走到$(i,a)$，不能碰到$y=a+1$的方案数；右半边是走到$(n-i,k-a)$，不能碰到$y=k-a+1$。

翻折法。如果碰到了$y=a+1$，我们在第一次碰到的点折上去，就和走到$(i,a+2)$的方案建立了双射。走到$i,a$的方案数是$\displaystyle\binom{i}{\frac{i+a}{2}}$，走到$(i,a+2)$是$\displaystyle\binom{i}{\frac{i+a+2}{2}}$，于是答案是这俩减一下。同理可以搞出另一边，于是有

，其中组合数在下指标不是整数的时候值为$0$。然后就$O(n^3)$了。这个东西看起来和爆力dp一个复杂度啊，不过懒得优化了（

D9

A. A Poor King

只有$64^3$种状态，直接模拟。

B. Best Division

trie优化dp。

C. Convex Hull

我们相信不需要求出三维凸包也可以做这个。

考虑枚举两个点，计算它们的连线段和这个面的交点(如果没有那就没事了)，然后对这些点跑二维凸包就行了。

D. Different Sums

构造题/jy

注意到钦点$a_i<3(i+6)$之后，$n=2000$的构造可以用在所有$n\leq 2000$上面，于是我们只需要找到一个这样的$n=2000$的构造。

随。然后发现并随不出来。如果你运气足够好，是可以随出来的吧（

考虑继续钦点$3(i+5)\leq a_i<3(i+6)$，但是搜了一下$n$很小的情况发现无解，于是$n=2000$的时候必然也没有这样的解。

然后想不到任何东西了。正解非常离奇。

我们找到$>n$的最小素数$p$，然后随便找一个$[1,p-1]$之内的数$x$。设$r_i=2p+\frac{1}{2}i(i+1)x\bmod{p}$，构造前缀和$s_i=2ip+r_i$。

接下来证明不存在$i,j,k,l$满足$s_i-s_j=s_k-s_l$。反证法，如果存在这样的$i,j,k,l$，直接代入

。注意到$r_i,r_j,r_k,r_l<p$，所以$\vert r_i-r_j-r_k+r_l\vert<2p$，而前面是$2p$的整数倍，所以必须有$i-j-k+l=0$，于是必然有$r_i-r_j-r_k+r_l=0$。同时，$i-j-k+l=0$指出$i-j=k-l$，于是我们设$i-j=t$，则$j=i+t,l=k+t$。

把这个爆力展开，我们得到

于是我们知道$i=k$，于是$j=l$，于是这个构造是正确的。接下来我们枚举一个$x$，找到使得序列中最大值最小的$x$即可。

太离谱了，这是mo题啊/fn

E. Easy Homework

收录于 fib数列。还是很牛逼的!

F. Flight

答案$\leq 3$。找到直径，然后只有三种策略 : 直接过去，走到一个直径端点再走过去，走到一个直径端点，然后走到另一个，然后走过去。预处理所有点到直径的距离，复杂度$O(n+q)$。

G. Generator

min-max容斥，然后是pgf经典问题，上个kmp或者z algo或者hash把系数爆力预处理出来，复杂度是$O(2^nn^3+n^2\sum l)$。

还是复习一下pgf。我们设$g_i$表示$i$次之后没有结束的概率，$f_{i,j}$表示$i$次之后出现了第$j$个的概率。

做法是，我们有$n+1$个方程。第$n+1$个是$zG=G+\sum F_i+1$，表示每过一轮要么结束了要么没结束。前$n$个中，第$i$个是$\frac{1}{m^l}z^lG=\sum\limits_j\sum\limits_k[a_{i,1,…,k}=a_{j,l-k+1,…,l}]\frac{1}{m^{l-k}}z^{l-k}F_j$，表示我们强行往后加第$i$个串，会让哪个串结束。

H. Honey Tour

矩阵快速幂优化dp。至少我感觉是?

I. Intersection is not allowed!

这个问题过于经典。lgv引理，用组合数爆算路径数。这好像都变成oi-wiki例题了（

J. Jong Hyok and String

这个描述看起来很奇怪。建个多串sam，然后匹配查询串，输出$\mathrm{maxlen}(u)-\mathrm{maxlen}(\mathrm{fa}(u))$。

K. K-th value

15s是啥啊/jk

看起来不是k大k小，而是某种中位数。我没太看懂题，感觉它说的是长度在$l,r$之间而权值的k-中位数最小，然后k-中位数说的是从小到大排序之后$\lfloor\frac{len}{k}\rfloor$位置上的值?

二分答案，然后把大的置为1，小的置为0。如果存在一条路径，满足$(k-1)c_0\geq c_1$，那么这条路径的答案比当前二分的答案还要小。问题是怎么找到它。

分数规划。给0赋权$1$，给1赋权$k-1$，问题是找权值的最大值。这是点分的经典问题，看起来容易做到$O(n\log n)$。总复杂度$O(n\log^2 n)$。

由于这个题$l,r$非常小，可以直接对这个dp，但是它真的会比优秀实现的点分快吗/jy，也就是预处理分治过程中每一层的dfs序这样的。

L. Less Time, More profit

还是看不懂题，我感觉这个商店是只产生一次利润，不然不会impossible/yun

二分时间，然后跑最大权闭合图。

如果产生多次利润，看起来也可以跑最大权闭合图，但是需要建一个分层图，复杂度就上天了。

M. Math is Fun

nonono，math is not fun/fn

一个集合的lcm是不容易直接做的。两个经典做法是，分别考虑每个素因数的贡献，以及对它强上多重集子集反演。后者会得到一个$\prod$，看起来和这题的$\sum$格格不入，所以还是算了。

这个题$n$只有1e2啊?

先把$\subset$换成$\subseteq$。考虑枚举一个$\gcd$，然后反演一下，看起来它会变成

设后面的东西是$f(kd)$，问题是怎么求所有$f$，也就是怎么求一个集合所有子集的$\mathrm{lcm}$的平方和。这个看起来是一个经典问题?反正我没见过（

考虑搞点离奇做法。注意到$\sqrt{v}\approx 31.6$以内恰好有$2,3,5,7,11,13,17,19,23,29,31$一共$11$个素数，它们最大的次数是$9,6,4,3,2,2,2,2,2,2,2$，全都$+1$并乘起来，我们得到$10\times 7\times 5\times 4\times 3\times 3\times 3\times 3\times 3\times 3\times 3=3061800$，设它是$L$。

考虑状压它们然后单独处理很大的素因数，因为它们只可能在$\mathrm{lcm}$中出现一次或者不出现，并且每个数只可能包含最多一个。把数们按包含的这个素因数分组，依次决策每一组，也就是设$dp(i,S,0/1)$表示考虑前$i$个，选了$S$中的小素数，没有/有在当前组选一个数，所有方案选择的大素数的乘积的平方和。一次dp是$O(Ln)$，总复杂度是$O(Lnd(v))$。看起来不像很能过啊?

考虑能不能继续砍一砍。我们开三次根号，现在只剩下四个素数$2,3,5,7$。接下来每个数要么有最多两个中等大小的素因数，要么有一个大素因数和最多一个中等大小的素因数，呃这两种情况都附带一些小素因数。我们先处理有两个相同的中素因数的数，然后按照大素因数给这些数分组，依次决策每一组。这样只需要存每个中素因数有还是没有，而不需要存有几个，状态数降为$10\times 7\times 5\times 4\times 2\times 2\times 2\times 2\times 2\times 2\times 2=179200$。

所以值域很小的数论问题，请记得尝试开根之后爆搜。

D10

finally…

A. Median

二分答案，然后主席树数点。

但是这个不是很好。可以离线下来一起二分所有询问，每轮跑一遍扫描线BiT，常数会更好一些。

B. Hard problem

只需要手算$l=1$。画两个圆，然后积就行了。

正叔说这个不好积，那就simpson/jy

然后正叔说这个是小学数学题。好像真的是（

C. Captain is coding

先枚举要尝试完成哪个集合，假设要完成A，而B可以不完成。

如果一个题比打字更优秀，并且这个题可以做，那么我们就会去做，注意应该优先做A中的。剩下的那些需要做的题我们可以留到最后去做，也就是时间正好的时候再去做。二分答案之后这么贪心即可，复杂度似乎是$O(n\log v)$，所以为什么要开6s?

然而搜到的做法和这个好像不是很一样。不过我觉得它是对的（

D. Death Sequence

模拟。打打表，然后猜一个递推式。

E. Road

模拟。

F. Counting Intersections

离散化一维之后扫描线BiT。或者扫描线set。

G. cjj’s string game

dp，矩阵快速幂。

H. Cube again

爆力枚举所有可能的置换，看起来一共有$24$种，也就是第一个的第一面对上第二个的哪一面，然后第一个的第二面还有四种可能。然后模拟。

I. Stone game

硬算sg值。这玩意有没有什么结论啊?

J. Lucky E

注意是最大值的期望，而不是期望的最大值。

这个好像并不适合min-max容斥。

考虑一个点成为最大值的概率，我们枚举它的值，然后剩下的都要不比这个值大。设$dp(u,i)$表示$u$子树最大值是$i$的概率，转移直接做+,max卷积就行了。然后直接统计答案就行了。

K. Water problem

真的水。模拟。

所以mutc16也结束了。我就先弃这个坑，去看看ptzsc16。

ptz营

可以在Baekjoon oj找到近代的。在我开始写的时候一共有1115道题，非常的好啊!

sc2016

D1

同时是mutc16 D2，所以收录于前面了。

这场是来搞笑的吧（

D2

懒得写翻译了/fn

A. Alone in the Cactus

如果这是一棵树，那么你只可能死在叶子上。我们只需要求出到每个叶子的概率。

现在有了环。我们把环缩成一个点。环与一个点的不同之处在于，计算从它走到各子仙人掌的概率的方式不一样，并且你有可能会走一圈回来撞死在自己进入这个环的地方(但是如果走回来的时候那个点有子树则不会)。建立圆方树然后dp就行了。

看起来可能有很多corner case?当场无人通过。

B. Binary Neural Network

一个直接的想法是，只造一个中间层，直接检查每种情况。

直接的想法是，从每个输入连到中间层的每个点，然后如果这个值不对的话，就给一个巨大的惩罚值。可以给输入造一个反的输入，这样中间层的任务就变成检查给它的是不是全是$0$。造一个恒$1$的老哥给它一个足够的值，然后因为要检查全$0$，如果出现$1$则有一个比恒$1$老哥更大的惩罚值把它的值炸成$0$。最后用一个什么东西把输出极端化就行了。

C. Chess Puzzle

先搬个 挑战哈密顿。

这是一道错题。样例其实是可以走完的。

经典想法是构造一个小的满的，从而把大的取膜成小的，然后小的爆力。但是我们搜了一下，发现可以直接用于取膜的东西好像是构造不出来的。

事实上，答案是，除了2和4都有走完的解。我的方法是，如果$n\bmod{3}=0$，走一个看起来像这样的东西 :

如果可以正反走两遍，就赢麻了。我们可以把下面这两个以某种方式拼起来得到解。

如果你很想知道具体怎么做，下面给出了$n=6$的解。

同时，如果$n\bmod{2}\neq 0$，有一个非常精美的构造，也就是在下两行从左走到右，上两行从右走到左，下两行从左走到右，上两行从右走到左，这样来回几遍居然就走完了。下图给出了$n=5,7$的解。当然有很多类似的构造。

如果$n\bmod{2}=0$，我们可以在走到边上的时候走一个第一张图里面的东西。比如这是$n=8$的构造 :

。看起来还是很有趣啊!

感觉写起来需要很多讨论，所以就没有写（

如果你真的很想解决这道题，请跟着我画的图走一遍。我觉得它可能看起来比较乱，但是还是比较贴心的，至少比标注 这是第几个走到的 要好的多?

D. Dominoes

我刚知道骨牌还有点数（

骨牌的点数就是$[0,6]\times [0,6]$然后去重，一共是$28$张。

用网络流判定能不能放，然后考虑怎么考虑上这个骨牌的因素。想了几个方法你发现这是不行的。

注意到只有 覆盖两个绿格子 和 覆盖恰好一个绿格子 的骨牌数量影响答案，考虑轮廓线dp，然后就结束了。复杂度$O(2^{\sqrt{nm}}(nm)^{2.5})$。

E. Experience is Worth It

注意到我们能打一定会打。于是爆力是$O(n^6)$。

注意到只有26种怪，于是我们可以把一种怪放到一起处理。现在是$O(n^4\Sigma)$。

注意到打不过每种怪的是一段，也就是说我们固定矩形右边的线段，然后往左边看，每种怪最多贡献一个打不过的区间，并且显然随着右边的线段右移，这些区间都在右移。使用53指针，现在是$O(n^3\Sigma^2)$。

注意到我们并不需要$O(\Sigma)$处理移动。把怪按需要的经验排序，那么需要的少的怪肯定先干掉，多的怪后干掉。可以用$\Sigma$个二维前缀和来$O(1)$判断。现在是$O(n^3\Sigma)$，算出来大概是2e8，当然还有二维前缀和的常数，不过感觉可过。

F. Fix the Matrix

看起来是说，把每一行和每一行改一个得到的所有可能放到一起，没有重复的；列是一样的。这么搞的话我们得到$42$个不同的序列，而一共有$64$个，所以看起来这是可能的。

注意到这个说的是，有两行xor的popcnt$\leq 2$，或者两列这样，那就不行。

搜一下就行了。我搜出来解很多，一个可能的答案是

1
2
3
4
5
6
000000
000111
011010
011101
110001
110110

然后就是模拟了。

G. Guess the Data Structure

感谢do_while_true的教导。

维护一个全局xor标记，插入的时候xor上全局xor标记。经过至少一次排序的用一个trie维护，刚插入还没经过排序的每一位开一个前缀和，并记录这个前缀和记录的时候的全局标记。每次排序的时候把后面爆力插入前面。复杂度是俩$\log$，瓶颈在trie的部分要查询区间和。

H. Hovercraft

注意到如果不使用递归，我们只能使用$8\times 12=96$步。但是使用大量的墙拐来拐去，很容易卡出一个210步的高难度动作，于是我们就却死了。

感觉上这个情况是无解的。所以这个问题看起来是要搜啊（

搜就是了。把N扔掉，一共有$\frac{1-5^9}{1-5}+2\frac{1-5^8}{1-5}=683593$种函数(实际上其中还有相同的)，我们枚举这个，然后bfs，每个状态取最短的串。复杂度是$O(5^82^knm)$，算出来大概是1e10。玩个锤子?

当场无人通过，问了切队长和唐队长好像也没有什么牛逼搜法。whq说可以大力剪枝得到吓人常数，不知道正解是什么东西。

I. Izhevsk Training Camp

直接枚举选啥，然后用那个三遍BiT的trick。复杂度是$O(9^2n\log n+9^3)$。

可以加强到30维，$n=1000$?

D3

A. Almost Longest Increasing Subsequence

无从下手。随了几个策略，在1000组下顶多达到0.62。

猜测是论文题，于是翻一翻wiki，果然找到了论文 Optimal Sequential Selection of A Monotone Sequence From a Random Sample。第四节提到一个很好的策略是，如果上一个选的是$t$，现在来了一个$x>t$，两者之间有$d$个数还没出现，剩下的比$t$大的数还有$c$个，那么如果$d\leq\sqrt{2c}$则选择$x$，否则不选。这个东西得到的期望长度是$\sqrt{2n}+o(\sqrt{n})$。

好像这题有巨多数据（

B. Bitwise Queries

吉老师线段树。如果在一位上大家都一样了那就打标记，否则递归下去爆力改。

为什么当场没有人过啊?有个队交了十发/xia

C. Cocktails

有15个队过了，所以我不能不会啊/fn

它说的是搅拌机可以杀掉一个长$k$区间吗/yun，不知道，就按这个做了。又有人subsequence substring不分?

考虑枚举用了$t$次搅拌机，那么除非$tk>n$，否则两次搅拌的区间必然不交，而$tk>n$可以特判。

然后注意到一个罐子是否被搅拌，和上手它需要的时间没有必然关系，因为有可能旁边有一个很大的老哥把它带飞了。

考虑了费用流，发现不行。

考虑dp。设$dp(i,j,k,l)$表示考虑前$i$个，当前这一段搅拌还有$j$个位置结束，前面有$k$个不在搅拌中的位置需要往后换到搅拌中，$l$个在搅拌中的位置需要往后换到不在搅拌的位置。转移考虑当前这个是直接支付，原地不动，还是换到前面，还是往后换。然后就$O(n^4)$了。看起来遇到这种随意交换的问题，如果要dp，那么就大力留线头即可。邻项交换的性质好像不如这个适合dp?

为了优化，我们需要缩减状态数。注意到$k,l$实际上最多只有一个非零，因为如果两个都非零了，那么直接交换其中的就行了，反正只有目标位置是不是被搅了有关系。复杂度降为$O(n^3)$。

实现的时候可以直接用一个值记录，正的表示有若干在搅拌中的位置要换到搅拌外，负的反过来。

D. Downhill

过的最多的题/xia

注意到每一个间隔是独立的。所以尝试样例中的三种方法，从下往上递推即可。

E. Expected LCP

本来以为这是牛逼带项式，但是它不是/fn

考虑min-max容斥，显然这个min比较好算。但是这玩意是一些pair的max，所以我们需要在所有pair的集合上做min-max容斥。考虑一张图，我们钦点了一些pair相当于钦点了一些边，那么要求让这个min恰好是$k$的概率，你发现每个连通块内部的边是没有关系的(但是它需要连通)，只有连通块的数量和大小们有关系。具体地，设$p=\prod\limits_{s}2^{1-s}$表示每个连通块内部在一位上都相同的概率，注意到如果连通块数是$c$，那么$p=2^{c-n}$。接下来，枚举lcp的min，设为$k$，我们得到$\sum\limits_{k=0}^\infty kp^k(1-p)$。通过扰动或者使用pgf，我们可以得到它就是$\frac{p}{1-p}$。现在这个min的期望只和连通块数$c$有关了，可以先跑一个连通图计数的dp，然后拿那个东西来背包，转移就是组合数选出$1$号点所在的连通块。复杂度$O(n^2)$，应该可以法法塔优化到$O(n\log n)$。

F. Finite Walking

当场过了三个队。

感觉就很像线代那一套。观察一下正解长度才1.6k。

注意到我们可以每条边走至少一次，因为只要找到一条回路，不管有没有重边，一直走下去必然循环。

所以每条边，如果它的$a_i$是奇数，那么我们在上面来回走就可以得到所有的可能。如果它的$a_i$是偶数，那么我们来回走是走不出奇数的，需要尝试让它走奇数次，不妨把这两类边称为奇边和偶边。同时，$[0,a_i-1]$中奇数偶数个数相同，所以每组独立的偶边都是给答案直接乘$2$，这样我们就转化成奇偶性了。

此时容易想到经典套路，我们跑个dfs树，然后对于每个非树边确定的环，把它们搞成一个向量表示可以改变这个环的奇偶性(只把偶边考虑进去)，求出这个东西的rank我们就求出了答案。

直接做是没有前途的。考虑每条非树边是覆盖了一些链上的偶边(也许和自己)，树上差分，这样它只改变了最多三个位置，也就是两个端点和它自己。现在这个矩阵非常稀疏，但是直接消元的复杂度看起来仍然不能接受。

注意到偶非树边永远能够贡献一个自由度(因为它不可能被消掉)，所以我们可以把偶非树边全都扔掉，只考虑剩下这些奇非树边。现在每个向量只有两个非零位置。

于是这又是经典套路了。如果奇非树边形成了环，那么就会线性相关，否则必然不会。并查集维护一个基，复杂度$O(n\alpha(n))$。

看了一眼样例，我怎么假飞了?哦，看起来是因为起点和终点可以不同。注意到可能会有本质相同的起点和终点，比如有一个奇非树边$u\leftrightarrow v$，然后我选择树上的$u\leftrightarrow w,w\leftrightarrow v$就是本质相同的，所以对于每条奇非树边，这样的情况应该只保留一种。也就是说，第$i$条贡献了自由度的奇非树边会让本质不同的初始情况减少$n-i-1$个，也就是说如果有$k$条这样的边，那么我们只剩下$\frac{(n-k)(n-k-1)}{2}+k$种可能的初始情况，最后答案乘上这个就彳亍了。

我没有写，但是图是不是可能不连通/xia

G. Guess the Distribution

当场无人通过，并且我不了解概率论。

H. Hash Table

为什么插入需要给第二个参数（

对每个位置维护前后极长连续1长度，然后上个BiT就行了。

I. Immigration

给物体的速度减去peter的速度，然后peter就在原点了。画出物体的轨迹，答案只可能在垂线或者端点处取得，模拟即可。

J. Jumping on a Tree

长剖!给合并之后每个深度建一个点，然后跑scc，复杂度是线性。

但是有没有什么无敌好写做法啊/yun，最短解可是只有1.1k。发现我们并不需要跑scc，直接并查集合并就行了，因为每一层被合并一次之后就会变成一个点，之后的每次合并都是$O(1)$了。

K. King’s Roads

居然没有一眼秒出来/fn

直接Boruvka。一开始排序，每轮双指针扫一扫这个东西，维护在两个不同连通块的$\min$这样的，复杂度是一个$\log$。

D4

同时是hdu mutc16 D8。但是为什么出题学校是不同的（

E当场无人通过，看起来它难度还是不低的。Trinity没切D，输了啊!

D5

A. Dreissig

看起来很奇怪。

ksun48把这个秒了，写了4.3k/xia，但是baekjoon不能看代码/fn

tourist队当场-4/xia

tourist队叫Past Glory，听起来很帅啊（

感觉一下，你比随机牛逼在你有目的，所以可以随几个目标排列，然后直接一个一个尝试去凑?并没有写的兴趣。

我们又考虑了一下，可以尝试进行一个哈密顿的挑战。

B. Mond

密恐慎入，快逃!

注意到这个东西看起来真的就是大约60bit/xia，可能实际上是55bit少一点这样的。

我们可以用一个类似这样的东西来二分 :

，其中蓝的是能探测到的区域。当然你发现最下面一排会出问题，需要上来先问一次最下面一排看看会不会出问题，如果出问题了就改成从上面走。

然后我们可以先在这些条中进行7次二分找到它所在的条，此时横坐标误差不超过2公里。接下来就只需要在这一条的旁边拿一条来二分，这需要21次来找到精确的$x$坐标。接下来只需要在它下面拿个条去二分精确的$y$坐标，这需要27次。一共看起来是56次。

C. Oha

考虑我们是要构造一个acam使得上面长$k$的并且不经过任何终止结点的路径恰好有$n$条。

注意到$k\leq 60$，这看起来是非常明显的提示。考虑$\times 2,+1$的trick，我们要$\times 2$看起来非常简单，但是要$+1$好像不是很简单。

不过没关系的，看起来$\times 2,-1$比较容易。但是问题是这里是ban一个子串，而不是一个前缀，所以前面可能会影响后面，所以我还是失败了。

考虑先$k=2^{\lceil\lg n\rceil}$，然后随一个串尽可能多ban而使得剩下的串个数$\geq n$，可以直接拿牛逼acam dp爆力算出还剩多少。如果差变得很小了，那么直接用长$k$的串去填。感觉这是可以的，但是我不知道啊/jk

没有找到什么精美的构造。

D. Pruefsumme

看起来说的是，你可以对每个位置做一个变换(每个位置的变换可以是不同的)，然后在一个自动机上跑。

注意到 改一个位置会改变结果 基本上是废话。

注意到这个东西可以构造出任意各位的线性组合。

考虑先构造一个$m=10$的做法。我们构造$a_1+3a_2+a_3+3a_4+a_5+3a_6+…$，这个看起来很对。

但是那个系数$3$并不总是适用，当$m=6$的时候可以换用$5$，$m=9$可以用$2,5$。当$m=2$的时候，好像出了问题。

考虑用一个牛逼位运算，这个位运算应该满足改变一个运算数必然会改变结果，满足这个的只有xor和xnor。注意到我们可以对每一位做变换，所以xnor和xor是等价的(xnor好像是相当于最后把结果取反)，所以只需要考虑xor。

直接用xor看起来显然不是对的，因为swap并不会改变xor。

考虑我们用上那个对每一位做变换的操作，注意到这个操作只能是取反或者不取反。讨论一下，你发现swap相邻的必然不会改变全局xor和。于是我们就证明了$m=2$必然无解。

E. Rumpf

为什么ksun48的所有代码都这么长/fn

用期望的线性性拆开每条鱼，考虑凸包包含一条鱼的概率。

考虑凸包不包含一条鱼的概率，我们从鱼找到极角最小的石头，那么剩下的石头需要都在再转180度的范围内。对于一个极小的极角区间，我们可以算出极角最小的石头落在这里的概率，这看起来就是所谓微元法，然后就分成几段大力积分就好了。但是我不会积分啊?

F. Strasse

看起来这跟雀很像啊!如果现在你只等最后一个了，可能的情况有三面，两面，一面。

注意到，取了两个数之后，我们立刻可以得到接下来获胜的概率。

设$f(k,a)$表示还剩$k$轮，手里拿着一个$a$，最优策略下获胜的概率。转移枚举接下来要来什么，如果来了的可以凑成三面那么必然要取，此时概率可以直接算出来；如果是两面或者一面那么可能选择不取，取了可以直接算，不取则转移到$f(k-1,a)$，同时来的这张可以凑成三面，两面，一面的概率都可以$O(1)$算。继续设$g(k)$表示还剩$k$轮，手里啥也没有，最优策略下获胜的概率，一样转移即可。复杂度$O(nk)$。

G. Tabelle

稀疏矩阵高消/fn

这个看起来是构造一个经典的差分。我们进行这么一个差分 :

，绿色的是$(i,j)$，把所有蓝色和粉色的xor起来，其中蓝色的要先取反。这个差分在行，列，斜线取反的意义下都是不变的，除了最边上的很少的元素。把越界的都舍掉就可以了。

此时高消仍然不可行。边上看起来是一个拐的形状，我们从这个拐的两边大力状压dp到中间，看起来状态数是$2^9$之类的，然后在中间硬卷起来，似乎就结束了。看起来会非常难写。

H. Unrumpf

据说是机器学习。

I. Vier

上网搜Petr Contest 14 solution，搜出来全是这个题/xia

注意到排列是随机的/xia，考虑随机一个$a,b,c$，那么我们确定了$d$和$\pi_d$，然后这个东西有$\frac{1}{n}$的概率是对的，期望随$n$次就可以随出答案。/xia

J. Weltall

题意看起来是，求长$n$，有恰好$k$个位置满足$a_i=i$(不妨称为 对了的位置，毕竟这类问题的经典称呼是 错排)的排列$p$中，字典序的kth。

这个$d$是有可能非常大吗/yun，看起来是的，因为两发通过提交分别是pypy和jvav（

考虑逐位确定，如果已经确定了前$i$位，我们要算剩下的还有多少可能，想一想这可以归结到算$f(n,k,t)$表示长$n$，有$k$个位置对了，并且有$t$个数是无用的(也就是在确定前$i$位的过程中，$\leq i$但是前$i$位没放的数，容易发现这些数具体是哪些不重要)的排列数量。

为了算这个，我们可以固定$n,t$，钦点一下，然后二项式反演。式子大概是$f(n,k,t)=\sum\limits_{i=k}^{n-t}(-1)^{i-k}\binom{i}{k}\binom{n-t}{i}(n-i)!$，然后算这个复杂度显然上天了。

考虑能不能dp一下。我们钦点第一个是对还是不对，如果它对了那么就对了，否则它就不对，于是得到$f(n,k,t)=f(n-1,k-1,t)+tf(n-1,k,t-1)+(n-t-1)f(n-1,k,t)$之类的，这样就避免了高精乘高精。复杂度$O(n^4\log n+Tn^3)$。常数看起来非常小，我没有写，但是我怀疑直接过了（

D6

A. Gambling

这形成了$\gcd(n,m)$个圈，对每个圈做前缀和，然后直接求每个人第一次输麻的时间。

B. Colourings

这个题一眼看上去感觉很有趣啊/xia，但是为什么过的这么多?

样例是树/xia

我们直接猜测不可能无解。

不妨认为smart译为聪明，beautiful译为美丽。考虑两个着色的意义。一个着色中，每种颜色是一个独立集，所以它是一个独立集划分。聪明的着色把图划分成若干非平凡独立集，而美丽的着色把图划分成个数比较少的独立集。

容易想起来最小着色是npc的，所以这个题造数据的方式或许可以帮助我们。它看起来应该是，先找两个方式把$1,…,n$划分，这作为两种染色，然后加边，如果加的边端点在任何一种染色中同色那就不加。不过这好像没啥用。

哦这并不是没有用。因为我们刚才断言了不可能无解，考虑一个最极端的情况，所有能加的边都被加上了，此时我们应该怎么做。

考虑此时这个图的结构是什么。每个点有两个颜色，然后如果两个点的两个颜色都不同，就会给它们连一条边。此时问题变得经典起来，把每个点画到平面上，坐标是它两维的颜色，相当于除了和它在同一横线和竖线上的点，别的点都和它不在同一个独立集了，也就是说每个独立集都是一条横线或者竖线(这中间可能被别的线切断，所以我们需要要求一个点只能匹配一条线)。

现在问题变成，平面上有一些点，每个纵坐标至少有两个点，要画若干条横线或者竖线，使得线的数量不超过横坐标的最大值$k$，并且每条线匹配至少两个它经过的点，每个点只匹配一条线。

显然一个横坐标只会有最多一条竖线，一个纵坐标只会有最多一条横线。

诶这是不是已经转成网络流了¿点向它的两个颜色连边，表示它要匹配横线还是竖线，跑一个带下界的可行流即可，这是二分图所以应该挺快的。

考虑能不能进一步转化。从左往右考虑，找到当前横坐标上还没有被任何横线覆盖的点，如果有至少两个，那么我们就画上这条竖线。如果只有一个，那么我们就从这里往右连一条横线。每个横坐标只会产生一条线，于是复杂度是$O(n)$。

但是是不是不需要这么多转化啊/yun，实际上这个做法翻译成不转化的东西，就是枚举美丽的着色中的一种颜色，然后如果它里面元素个数至少是$2$那就把它加入答案，否则我们把唯一的元素和它在聪明的着色中的所有同色点一起加入答案，然后把这些点都删掉。所以我在转化个锤子呢?

C. Counter-manifestation

题面过草（

第一问就是有没有环，直接toposort。剩下的问题就是找到所有环的交。

缩个scc，如果有超过一个大小$>1$的scc，那么所有环必然没有交。只需要考虑那一个大小$>1$的scc。

无向图所有环的问题，经典trick由 最大xor路径 给出，但是关于有向图的所有环的问题，好像真的想不起来什么东西。

先跑一个dfs树。这不如无向图dfs树好用，但是至少显然的一件事是，所有的返祖边覆盖的链必须相交，否则答案是空。我们找到这条链，不妨把它称为候选链，答案只可能出在上面，并且一定是上面的一段区间。

猜了一个有向图基本环的结论，被正叔刺杀了。不过有一个结论是必然正确的，也就是所有的环必然经过一条返祖边。

考虑我们把候选链上最高的点拿出来，从它开始重新跑dfs树，并且在dfs的时候先走这条链，保证它还是一条链。此时除了连向链头的边，所有原来的返祖边都不再是返祖边。于是一个直接的想法是直接随机dfs，这么跑十遍，每一遍把这条链缩短，最后得到答案。看起来不是很好卡，至少我不会。

考虑了一天，然后得到了做法，然后并不想写。这**能有四个队过?太牛逼了。低估了16年ptz营选手的实力。

因为这个图现在强连通了，我们考虑它的dfs树，不妨把从上往下走第一个分叉点(儿子个数$>1$的点)简称为分叉点，那么对于分叉点的每个子树，要么有一条返祖边连到分叉点之上，要么有一条横向边连向别的子树，不然这个子树将不再强连通。同时，必然有一个点，它有一条返祖边连到根。

如果分叉点的至少两个子树有返祖边，那么候选链必然完全在分叉点上方(或者为空)，此时所有的返祖边都要连到分叉点上方。

考虑如果一个环没有前向边，那么它不可能不经过候选链，因为任何环必须经过一条返祖边，而如果它不走横向边，则必然经过候选链，如果走横向边，必须要走进分叉点的子树中，还是需要走候选链。

所以，考虑如果一个环有前向边。走了一条前向边，我们就跨过了候选链的一部分。如果这条前向边的端点都在分叉点上方，那么它的作用就是ban掉了一段，也顶多只能是ban掉了一段。如果它的端点都在分叉点的子树中，那么它没有用。如果它一端在分叉点上方，另一端在分叉点的子树中，为了跨过尽可能多的候选链的部分，我们考虑如何才能走尽可能少的候选链而到达这条前向边的上方，从而接起来形成一个环。

如果我们不走到候选链上，那么就只能靠分叉点的子树间的横向边来回跳，直到有一个点的子树中有一条很高的返祖边。我们定义一个点的梯长表示从它出发走若干横向边和树边，然后走一条返祖边能到达的最高的点。如果求出了这玩意，我们就可以直接判定是否可以不经过候选链就走到我们选的前向边上方从而成环。

要求梯长看起来也不困难，我们只保留分叉点子树中的点，树边和横向边，跑一个dag dp即可，由于返祖边都被删了所以不可能还有环。

否则，我们必须要走到候选链上。走上去之后，我们可以直接往下走到最长的梯子上，直达根，所以我们只希望在分叉点上方往下走的部分尽可能少。定义一个点的梯短表示从它出发走若干横向边和树边，然后走一条返祖边能到达的分叉点上方最低的点。要求这玩意，还是用同一个dag dp即可。

然后是最后的case，如果只有一棵子树有返祖边。此时对于一条起点在候选链上的前向边，如果它的终点也在候选链上，它的效果是ban掉候选链的一个区间；否则，它的效果是ban掉候选链从交叉点往上的一段(也可能候选链完全在交叉点下方)。对于一条终点在候选链上的横向边，它的效果是ban掉候选链从交叉点往下的一段。模拟即可。

然后就做完了，复杂度应该是$O(n)$。

whq指出了一个牛逼做法。

考虑我们先随便找到一个环，然后把它删了，如果还有环那么答案是空，否则答案必然在这个环上。

考虑在这个环上走一圈，把点从$1$到$c$编号，然后把环边删了。如果有一条路径$i\rightarrow j(i<j)$，那么$(i,j)$这个区间都被ban了；如果有路径$i\leftarrow j(i<j)$，那么$[i,j]$这个区间之外都被ban了。第一种情况中，对于每个$i$我们找到编号最大的能到的$j$即可，由于删掉环之后不再有环，可以直接toposort。第二种情况中，对于每个$j$我们求出编号最大的$i$，但是由于要满足$i<j$所以不是很好直接做。一个牛逼做法是，直接按编号从大到小考虑每个点，记搜它能到的编号最大的点，然后把它删掉，并尝试更新连向它的点，看起来这里需要存一个它贡献到了哪些点这样的。每条边只会从没有贡献切到有贡献，然后从有贡献切到没有贡献，总复杂度是线性。

D. Championships

不停地删掉所有度数$<d$的点，然后在剩下的连通块中选择最大的。

E. Neon

简单想法是分治，复杂度是$O(nm^2\log n)$，没有前途。

枚举右端点，然后用个什么东西给左端点批量转移。发现状态相同的左端点转移完全相同，开个桶存有多少个就行了，复杂度$O(nm)$。

F. Robots

有个老哥写了20k过了。没有兴趣。

G. Equation

注意到这个平方和非常小。考虑枚举平方和，然后就得到$n$了，然后判定对不对就行了。

H. Hay

我怎么记得有个区间割草的题（

考虑把所有草按生长速度排序，那么每次割掉的肯定是一个前缀。二分这个前缀即可。

I. Gym

先把时间和器材编号离散化。

考虑一个方案什么情况下是合法的，你发现这当且仅当每种器材的使用到这个时间都有完美匹配。但是这个不好用网络流描述，考虑hall定理。经典结论是，我们要找一个器材使用时间区间的子集使得它邻接的选了的时间减去它的大小最小，我们必然是找所有完全包含于某个区间内的。证明看起来很简单，如果选的这些使用时间区间中间有空的部分，只保留其中一段必然更优；如果整体只有一段，那么必然是把包含在这一段里面的都选上。所以一个方案是合法的，当且仅当对于每种器材，对于每个使用时间的区间，它邻接的选了的时间的数量不比它的大小小。然后这就是若干个区间和的限制。

这个是不是经典问题啊，我怎么想了一年啊（。考虑从左往右贪心，我们肯定希望能往后放就往后放，也就是说直到有一个限制使得，这个位置再不放，即使接下来放满也满足不了了，我们就放一个，而放的这个应该匹配每个器材的右端点最靠左的时间区间。然后就$O(n^3)$了。

我们扫到$i$的时候，把所有还没匹配的时间区间的左端点对$i$取$\max$。为了找到 这个位置再不放，即使接下来放满也满足不了了 的限制，我们假装把后面都放满了，然后找一个以$i$为左端点的区间使得区间长度减去包含在其中的时间区间数量最小，然后我们就往后跳到这个位置并选择这个位置。这个可以爆力扫出来，复杂度是$O(n^2)$，因为只需要扫所有器材的右端点。

现在我们可以尝试上数据结构了。注意到 区间长度 可以拆成端点的差，而左端点固定了，所以要右端点最小。然后我们每次的操作就是删掉一个时间区间，查询一个全局的前缀中的刚才那个值最小的右端点，这里是全局的前缀是因为我们把已经匹配掉的删了。每个颜色开一个动态开点线段树或者平衡树，然后全局开一个堆即可，复杂度$O(n\log n)$。所以为什么是10s?

J. Triangles

枚举直角边来统计，然后要做四次线段数点。怎么线段数点啊?

考虑旋转扫描线，我们沿着当前扫到的线段的方向给所有点排序，然后拿一个set维护即可。有可能出现一条当前线段的垂线上有多个点，那么我们就给set每个点再开一个set维护投影相同的点。总复杂度$O(n\log n)$。

D7

先咕了。本来的计划是做完ptzsc16然后开始每天四场或者五场vp，没想到二月只有28天。

回来了，今天是2022-05-01。

A. Square Function

考虑爆力怎么做。用线性基爆算，也就是从$x+1$开始往后插入，用一个二进制状态表示，问题变成线性基里面能不能xor出一个$x$来。一共有$O(\frac{n}{\log n})$维，使用bitset，算一个的复杂度是$O(\frac{n^3}{w\log^2 n})$，也许可以跑1e4。真是阴间啊（

然后就不会了。oeis一下知道这个叫R. L. Graham序列，在concrete math的习题4.39出现。这个习题指出，这个序列建立了一个正整数到非素数的双射，也就是说如果$y$是素数则恰好有一个答案，否则没有答案。

于是可以从$y$往下找最大的$x$使得存在一个$x,…,y$这样的序列的乘积是完全平方数，然后这个可以跟刚才那个一样做。

为了进一步优化，看起来我们需要一点性质。

注意到超过根号的素因数只有一个，我们在线性基中把它xor掉之后，就再也不会出现超过根号的素因数啦，于是bitset只需要维护不超过根号的素数，这样的素数好像只有$168$个，也就是说三个ull就搞定了。

然后由于$S(x)\leq 2x$，所以我们得到了一个小常数，最后算量大概是$1000000\times 168\times 3$，大约是4e8，看起来很稳。写了一发，直接最优解。可能手写bitset确实比较牛逼。

B. Guess by Remainder

猜测总是只需要一次询问就可以得到答案，也就是猜测总是存在一个数$c$膜$1,…,n$的结果互不相同。随机一些简单的想法之后，可以随到选择$\operatorname{lcm}(1,…,n)-1$，这个数膜所有数都是$-1$，看起来这个题还是让大家比较幸运的。可以猜测它的大小必然满足要求，事实上oeis一下可以知道它的大小是$O(e^{n(1+o(1))})$。

C. Subtract if Greater!

意思是，全局$>x$的减$x$，全局kth。

使用zx2003 关于一个平衡树相关的问题 中提到的技术可以直接做到$O(q\log^2 v)$。考虑能不能更快。

我不会更快了。拉。

D. Eastern Subregional

绷不住了，什么鬼题（

E. K-transform

小模数/xia

考虑在$k$进制下，这个相当于统计多少个$k$进制数的位数加上各位之和$=m$。相当于有序地选若干个物品，每个的大小在$1,…,k$之中，最后总和是$m$的方案数。

但是$m$非常大啊?

考虑容斥，我们钦点若干个物品的大小超过$k$，那么先减去这么多$k$，剩下的就可以隔板了。复杂度$O(k^2)$。所以小模数是为了让你Lucas，但是为什么这么小啊?

F. Suffix Array for Thue-Morse

也就是多次查询第$k$小的后缀。

考虑Thue-Morse序列是通过把0换成01而1换成10得到的，那么其中很可能有些递归性质。打表发现奇数位置上的后缀们的顺序与前一级序列相同，而偶数位置上的后缀们的顺序是前一级序列从中间劈开，两边反过来。进一步观察，它是上一层的右半边$\times 2$，上一层$\times 2-1$，上一层的左半边$\times 2$，三部分拼起来。然后在奇数$k$层的时候，$2^k,2^k-1$两个后缀会比较有趣，$2^k$会跑到中线右边第一个位置，而$2^k-1$的位置看起来很复杂，简单方法是二分出它在哪，或者我们可以打表观察，它是

1
2
3
4
5
6
7
0
1
5
21
85
341
1365

oeis可以知道这个序列是$\frac{4^n-1}{3}$。于是依此分段递归即可。

但是为什么会有这么离奇的性质呢?不知道。

G. XOR Tree

也就是每条边有一个被操作的次数。

链之外的边的具体情况是没有用的，只有它们数量和的奇偶性有用。

如果链上所有边同时被操作奇数次，Alice就赢了。

考虑如果有一条边的重数是偶数，那么Alice操作了这条边之后，Bob可以跟着操作，这样如果Alice第一步之后没有赢，那么她永远也赢不了了。所以如果有至少两条边是偶数，那么Alice必败。

考虑没有偶数的情况，因为所有边必然走完，所以Alice必胜。

考虑有一个偶数的情况，那么Bob希望先把这个偶数填满，Alice希望不要这样，于是Bob的策略就是一直填，Alice的策略就是一直填别的，那么如果这个偶数至少是链总和的一半Alice就赢了，否则Bob就会把它填满，Alice就不可能赢了。

H. Fence

考虑什么样的房子是包不住的，发现和边界相邻的肯定包不住，和包不住的房子八连通的也包不住。这些包不住的房子周围是不能走的点，这些把棋盘划分成若干连通块，每个连通块内能保住的房子必然可以用一条线连起来。

I. Friends and Berries - 2

那个式子等价于$p(u,w)+p(v,w)-p(u,v)\leq 0$。根据勾股定理，我们知道这个说的是$u,v$总是作为钝角边(或直角)，也就是所有点都在它的两点圆内部或边界上。

我们求出最小圆覆盖，那么答案只可能在最小圆覆盖中相对的点上。

J. Oleg and Cola

对每个点开一个前缀和优化建图，然后从$1$跑一遍dij到$2$，然后从$2$跑一遍到$1$，然后枚举进出$2$的边。

K. Process with Constant Sum

不能继续操作的状态必然是，有一些$0$，一些$1$，然后一个大数。

考虑先给每个数膜$2$。

前缀$0$是没有用的，考虑第一段$1$，如果它后面有$0$，那么我们可以把这一段$0$移动到前面来。如果这一段$0$长是偶数，那么啥事没有，否则会有两个$1$合并起来。所以几乎相当于数有多少段长偶数的$0$，使用set维护连续段，BiT数一数，边界特判一下，最后一个也特判一下就行了。感觉很对。

D8

同时是hdu mutc 16 D9。

D9

它说是atcoder problems selection，但是我没有在atc上找到这些题啊/yun

A. Circles

按极角排序，然后爆力处理出边界，猜测它的长度是线性。不会计算几何。

B. Point Pairs

需要知道一般图匹配的tutte定理(tutte-berge公式)图图定理，它是hall定理在一般图上的扩展。

tutte-berge公式指出，一般图最大匹配之外的点数，等于删掉任意点集之后得到的图中，大小为奇数的连通块的数量减去删掉的点数的最大值。tutte定理是它的特例，也就是存在完美匹配当且仅当删掉任意点集之后，不会产生比点集大小更多个奇连通块。

考虑这个可以帮我们做什么。牛逼结论是，对于一个大小为偶数的连通块，它总是存在完美匹配，这是因为任意删掉一个点，图最多分裂成两个连通块，所以删掉$k$个点最多分裂成$k+1$个连通块，由于原来的大小是偶数，这些连通块的大小不可能都是奇数。所以删掉一个点之后，存在完美匹配当且仅当每个连通块大小都是偶数。

于是问题变成找到删掉每个点之后每个连通块的大小。我们只需要给每个点连上下左右第一个点，因为只需要这些边就可以得到正确的连通性，然后对这个建立圆方树直接算即可。

C. House Moving

考虑对于任何一个家庭，把他们往两边人更少的一边移动必然不劣。于是最后的状态必然是一些家庭在极左，另一些在极右。

然后就让我们想起noip2021 方差。考虑肯定是大的家庭在边上，小的在中间，因为对于任何一边，主要的贡献必然在另一边，所以把大的往边上换相当于把数值往边上移动，必然不劣。

写个爆力跑一下样例，样例3的一个最优解是

1
8 8 2 2 2 1 0 1 0 0 0 0 0 0 0 0 0 7 8 8

那个1飞了是因为两边和一样，看起来我们的结论很可能是对的。

考虑dp，设$dp(i,j,k,l,r)$表示前$i$个家庭，左边放了$j$个，他们的人数和是$k$，左边人数乘上位置的和是$l$，右边是$r$(看起来要给位置减去$n-m$)的答案。这样可以做到$O(m^7p^3)$，实在是太牛逼啦!

考虑我们不需要记这个乘上位置的和，因为这个贡献看起来像是$p_ip_j(i-j)=(p_ii)p_j-p_i(p_jj)$这样的，我们在确定$i$的时候计算含有$p_ii$的项即可。于是复杂度瞬间砍掉一个$m^4p^2$变为$O(m^3p)$。

考虑如何砍这最后的一个$m$。注意到我们也不需要记有多少人，于是结束了。

D. Nice Set of Points

看起来我们只能加9e3个点。

考虑分治，从中间取一条竖线劈开，保证左右两边之间都合法。发现在每个y上面放一个点必然可行。然后这个分治是会拿走中间那个点的，所以点数是$n\lceil\lg n\rceil-n$这样的，于是就结束了。

E. Eel and Grid

每个格子是完全相同的，方向违背了这个性质的话看起来就没有前途。

这个题还是有点牛逼了，我可能很缺少感觉。结论是，一个方案可行，当且仅当它有周期$g=\gcd(h,w)$，并且在每个周期内，设它有$d,r$个向下、向右移动，则$\gcd(d,h)=\gcd(r,w)=1$。所以我们直接枚举$d$统计答案。

一个等价的限制是$\gcd(\frac{hd}{g},\frac{w(g-d)}{g})=1$。

不满足的话显然不行，但是我不是很理解为什么满足就行了。

F. Right Angle Painting

哈密顿链/jy

直接从左往右扫，尝试把相邻的接头接起来，如果一段接头的数量是偶数那么有唯一的方法接起来，如果有接头接不起来，说明起点或者终点必然在这里。从另一边再做一遍，可以得到另一个起点或终点。然后再从上往下跑一遍，从下往上跑一遍，我们就得到了起点和终点的位置，再直接跑，跑过去的时候忽略这俩就行了。

G. Rectangle-free Grid

也就是不存在一个$2\times 2$的子矩形全是o。

感觉这是 基于智商的构造。

看起来1700是$2n\lg n$或者$n\sqrt{n}$之类的。可能$n\sqrt{n}$更为接近。

完全不会。我找到的一个做法是，取素数$p$，然后把$p^2\times p^2$的棋盘划分成$p\times p$个$p\times p$的块，然后像下面这样构造，这是$p=5$的情况。

由如下代码生成 :

1
2
3
4
for(int i=0;i<p;i++)
    for(int j=0;j<p;j++)
        for(int x=j,y=0;y<k;k++,x=(x+i+1)%p,y++)
            a[x+i*p][y+j*p]=1;

取$p=13$，然后截取前$150$行和列即可。

好像这个题在一定程度上是fjoi2022 D2B的原题。

收录在了 如果我不知道把一些东西放在哪里，那就放在这里吧。

H. Cups and Beans

考虑计算每个杯子里有一个豆子的sg值，然后xor起来。

sg值是所有后继状态的mex。相当于要每次往后加入一项，然后计算一个后缀mex，可以用线段树维护每个数最右一次出现的位置。

I. Edge Coloring

感谢Qingyu的指导。

覆盖之前的颜色很是不好，因为在覆盖这方面后面的影响前面的，而在路径这方面前面的也影响后面的。时间倒流，枚举路径的长度，然后从终点出发倒着走，第一次走到一条边就需要它的颜色是正确的，然后这条边就可以随便用了。枚举终点出发直接dfs即可，大概是走到要求的状态才可以使用一条边，并且如果走出了一个奇环接下来就必然可行了。

J. Travel in Sugar Country

对经过的顺序状压dp。设$dp(i,j,S)$表示考虑前$i$个商店，那个和是$j$，已经确定了$S$中的位置，复杂度$O(2^knm)$。

那么ptzsc16就结束了。接下来写ptzsc17。

2017

D1

A. Little Q and Big Integers

考虑这个是一个二项卷积，然后要减去带前导零的情况，也就是钦点第一个选0再做一遍。注意到786433是呐塔塔模数，所以法就是了。

B. Classic Quotation

注意到这个期望是直接加的，所以kmp一下，一个前缀和一个后缀和就行了。需要特判$l+1=r$的情况。

C. Counting Divisors

埃筛筛出每个数的分解，然后直接算即可。复杂度$O((r-l)\log\log v)$。

D. Dirt Ratio

模拟。

E. Lazy Running

同余最短路。对于每个膜边权和的值建一个点，然后跑即可。

F. Logical Chain

爆力。在kosaraju中使用$O(\frac{n^2}{w})$的dfs。

G. Matching In Multiplication

考虑如果一个右部点只有一条边，那么它就确定了，它的邻接点也确定了。所以我们可以不停删掉这样的点，直到所有点都有两条边。此时对于一个连通块，它必然是一个环，那么有两种可能，都乘起来就结束了。

H. Phone Call

相当于每次把两条链的并连成完全图，然后查询$1$所在连通块的mst。

kru。我们按费用从小到大加入这些电话线，爆力连通其中的点，然后缩点，使用vector启发式合并来合并邻接点。复杂度$O(n\log n)$。

I. Questionnaire

$m$不能是$1$/jy

我是智障。找到膜$2$下出现更多的那种。

原做法 : 考虑随机化，我们随两个数$a,b$，然后假设它们都在最优解中膜$m$为$k$的部分，然后找到所有的$m$爆力验证这样的。我对着$a\bmod{m}=b\bmod{m}$看了半天，没有想到把它变成$m\mid (a-b)$/xia

然后就结束了。对三次根号以下的爆力跑，复杂度$O(n\frac{\sqrt[3]{v}}{\log v}+(n+\frac{\sqrt{v}}{\log v})\log c)$，其中$c$是关于正确率的常数。

J. Security Check

爆力就是直接设$dp(i,j)$表示左边前$i$个和右边前$j$个最多匹配多少。

考虑如何优化。一个想法是匹配数不小于$n-O(k)$，但是这个看起来应该不对。

考虑转移是$dp(i,j)\rightarrow dp(i+1,j),dp(i,j+1);dp(i,j)+1\rightarrow dp(i+1,j+1)$，第三种转移在$\vert a_i-b_j\vert \leq k$的时候才可能，这样的转移只有$O(nk)$次是不可行的。扫描线扫$i$，用数据结构维护$j$。第一种就是直接移过来，第二种是每个位置跟上一个取$\max$，所以$dp(i,…)$总是单调的，第三种就是把各连续段的分段点向后移动一位。用平衡树维护各分段点，支持全局$+1$，单点修改即可。

一个牛逼做法是，我们只处理没有第三种转移的点。直接不停向前找到极长连续可以匹配的点，然后从前面一个状态转移即可，这个可以二分一下。两个做法复杂度都是$O(nk\log n)$。

K. Time to get up!

模拟。

L. Wavel Sequence

将wavel称为维吾尔。

也就是要计数$a,b$的相等维吾尔子序列个数。dp，设$dp(i,j,0/1)$表示左边到$i$，右边到$j$，这个应该是维吾尔峰/维吾尔谷的方案数，然后转移就是二维偏序，cdq分治即可。复杂度$O(n^2\log n)$。

M. Yuno And Claris

区间把$x$改成$y$，区间kth。

第一分块。

考虑怎么根号$\log$。分块，每一块开一个并查集支持重构，然后整块之间BiT多树倍增。也许可以过哦/jy

考虑怎么砍$\log$。我们需要在根号个数据结构上同时找kth，这看起来很困难。考虑值域分块之后，对于每块开一个序列上块间的前缀和，这样我们每次修改只需要改根号个位置。

考虑怎么砍$\alpha$。发现总合并次数是$O(n+m)$，所以我们可以爆力重构一块。总复杂度$O(n\sqrt{n})$。

• Previous
  电子琴学习笔记
• Next
  开杯题选做