目录
Contest Info
[Practice Link](https://cn.vjudge.net/contest/321878#overview)
| Solved | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 8/11 | O | O | O | O | O | O | O | O | - | - | - |
- O 在比赛中通过
- Ø 赛后通过
- ! 尝试了但是失败了
- - 没有尝试
Solutions
A - ^&^
题意：
要求找一个最小的正整数(C)使得((A oplus C) & (B oplus C))这个式子最小。
思路：
注意是(C)是正整数。
B - array
题意：
有一个排列(a_i)，有两种操作：
- 将(a_x)变成(a_x + 10^7)
- 询问没有在区间([1, r])里面出现过并且(geq k)的最小的数
思路：
- 权值线段树维护(i)出现的下标
- 那么只需要找一个最小的(x)，使得([k, x])这段数出现的下标的最大值(>r)即可。
- 权值线段树上二分即可，复杂度有点玄学。。
C - K-th occurrence
题意：
给定一个字符串(S)，询问一个子串(S[l, r])在原串中第(k)次出现的起始位置
思路：
考虑一个起始位置(i)出现了(S[l, r])，那么有后缀(S_i)以及后缀(S_l)的(lcp)肯定大于等于(r - l + 1)。
那么后缀排序之后，这些起始位置在(Rank[])数组中是连续的一段，二分找到左右界，主席树查询区间第(k)大即可。
D - path
题意：
E - huntian oy
题意：
计算：
[egin{eqnarray*}
f(n,a,b)=sumlimits_{i=1}^n sumlimits_{j=1}^i gcd(i^a-j^a,i^b-j^b)[gcd(i,j)=1] mod (10^9+7)
end{eqnarray*}
]
思路：
当(a > b)且(gcd(a, b) = 1)时，有(gcd(a^n - b^n, a^m - b^m) = a^{gcd(n, m)} - b^{gcd(n, m)})。
那么原式为：
[egin{eqnarray*}
f(n, a, b) &=& sumlimits_{i = 1}^n sumlimits_{j = 1}^i (i - j)[gcd(i, j) = 1] mod (10^9 + 7) \
&=& sumlimits_{i = 1}^n sumlimits_{j = 1}^i i[gcd(i, j) = 1] -j[gcd(i, j) = 1] \
&=& sumlimits_{i = 1}^n ivarphi(i) - frac{ivarphi(i) - [n = 1]}{2} \
&=& frac{sumlimits_{i = 1}^n ivarphi(i) - 1}{2}
end{eqnarray*}
]
令(f(n) = ivarphi(i))，配一个(g = id(n))，有((f * g)(n) = sumlimits_{i ;|; n} i varphi(i) frac{n}{i} = i sumlimits_{d ;|; i} varphi(i) = i^2)
杜教筛即可。
F - Shuffle Card
签到。
G - Windows Of CCPC
签到。