GDKOI 2016

GDKOI 2016

day 1

第一题 魔卡少女

题目描述：维护一个序列，能进行以下两个操作：1、将某一个位置的值改变。2、求区间的连续子串的异或值的和。

solution
因为序列的数的值都小于(2^{10}), 所以维护二进制的每一位的(1)的个数就可以了。用线段树维护即可。

时间复杂度：(O(20nlogn))

第二题 不稳定的传送门

题目描述：一个有(n)个点，(m)条有向边的图，每条边有一个概率（能通过这条边的概率）和一个费用，先从(1)号点走到(n)号点，若选择某一条边通过时，通过失败，则自动返回出发的城市，该边之后不能通过，但无论成功与否，该边的费用依然要花费，求期望花费的最小值。

solution
这题是dp+贪心，从后往前dp。从若现在在第(i)号点进行决策，则可以通过贪心决策边的先后通过顺序。具体贪心方法是如果先通过第(j)条边再通过第(k)条边比先通过第(k)条边再通过第(j)条边优，则先通过(j),再通过(k)。可证明有传递性，所以可以用快排处理。

时间复杂度：(O(nlogn))

第三题 寻宝

题目描述：最大权闭合子图

solution
经典裸题

第四题 地图

题目描述：连通性dp

solution
经典裸题

day2

第一题 染色大战

题目描述：状压dp

solution
经典裸题

第二题 QT 与泰剧

题目描述：求在((T, S])中与(S)模(3)同余的且该数的每一位至少有一个数不是质数的数的个数。

solution
按位dp，只要把前导零，模(3)的余数处理好就没什么问题了。

第三题 项链

题目描述：若一个环状字符串删掉连续的一段后，连起来后是对称的（对称轴可穿过字符），称为项链，求项链的最长长度。

solution
如果一个字符串是项链，则这个字符串由两个回文串组成。先把字符串复制一遍。用manacher算出以每个字符为中心的回文串长度。然后枚举第一个回文串的右端，然后求以这右端为左端的回文串的最大值（两个回文串的长度的和不能大于原串），这可以用线段树或树状数组维护。

时间复杂度：(O(4nlogn))

第四题 小学生数学题

题目描述：给出(p,k,n)，求((sum_{i=1}^n i^{-1})) (mod) (p^k)，保证有解。

solution
其实就是要求从(1)到(n)的逆元的和模(p^k)的值。由于(p)的倍数没有逆元，所以要分开算。设

[H(n)=(sum_{i=1}^n i^{-1}) mod (p^k) ]

[H^*(n)=(sum_{i=1, p mid i}^n i^{-1}) mod (p^k) ]

则

[H(n)=H(n/p)/p + H^*(n) ]

[ecause [H(n/p)/p]mod(p^k)=[H(n/p)] mod (p^{k+1})/p ]

[ herefore H(n)=[H(n/p) mod (p^{k+1})]/p+H^*(n) ]

等式右边的第一项可以递归计算。
问题在于如何求(H^*(n))
设(i=ap+b),(i^{-1}=xp+y( mod (p^k)))
则

[(ap+b)(xp+y)=1 mod (p^k) ]

[(ax+bpx+ayp+byp^2)=1 mod (p^k) ]

若(x=a^{-1} mod (p^k))
则

[(bx+ay+byp)=0 mod (p^{k-1}) ]

[(a+bp)y =(-bx) mod (p^{k-1}) ]

设((a+bp)z=1 mod (p^{k-1}))
则

[y=(-bxz) mod (P^{k-1}) ]

(ecause z 存在 herefore x可取)
则

[(a+bp)^{-1}=x[1+(-bxp)+(-bxp)^2+……+(-bxp)^{k-1}] ]

枚举(a)，问题转化为求右式和，可用矩阵乘法+二项式定理

时间复杂度：(O(pk^3logn*log_pn))