====== 2020/01/01 -- 2020/02/02 周报 ======

===== 团队训练 =====

无

===== Marvolo =====

==== 专题 ====

无

==== 比赛 ====

[[https://codeforces.com/contest/1401|Codeforces Round #665 (Div. 2)]]

==== 题目 ====

见本周推荐

===== Kevin =====

==== 专题 ====

==== 比赛 ====

==== 题目 ====

===== TownYan =====

==== 专题 ====

无

==== 比赛 ====

无

==== 题目 ====

见本周推荐

===== 本周推荐 =====

==== Marvolo ====

Codeforces:

[[https://codeforces.com/contest/1401/problem/E|Divide Square]]

题意:

给出一个边长为$1e6$的正方形,在这个正方形内部有一些线段,每一个线段都和坐标轴中的一个平行,且一定和正方形的某条边相交.求这些线段将正方形内部划分为了几个部分.

tag:线段树,计数

题解:

应该算是结论题吧.依次将这些线段添加到正方形内部,如果和之前的线段有$x$个交点,那么答案增加$x$;如果这条线段和正方形的两条边都相交,那么答案再加1.

comment:

比赛的时候没有想到通过数交点的方式来计数,这个思路挺神奇的.

==== Kevin ====

[[http://poj.org/problem?id=2778]]

**题意**

串都是由字母 $\text{A, T, C, G}$ 组成的。
给 $m\in[1, 10]$ 个串，每个长度 $\in [1, 10]$。
给一个长度 $n\in[0, 2\times 10^9]$，求所有长度为 $n$ 的串中，有多少个可能的串，其不包含任意一个之前给的 $m$ 个串。
答案对 $10000$ 取模。

**题解**

看到 $n$ 这么大，先考虑 $m$ 个串。在 $m$ 个串的 $\text{trie}$ 上考虑构造长度 $n$ 的串。因为是一个子串都不能出现，所以相当于在考虑了 $\text{fail}$ 的、有环的 $\text{trie}$ 图上随便游走，但不能经过某些特殊的点。

那么问题转化为求路径数。刚好 $\text{trie}$ 图的节点数 $=\Sigma len_i\le 100$ 很小，那么邻接矩阵快速幂即可。复杂度 $\text{O}(~(\Sigma len_i)^3 \log{n}~)$


==== TownYan ====

[[https://atcoder.jp/contests/abc171/tasks/abc171_e]]

**题意**

有一个长为n(n为偶数)的非负整数序列a[i]，生成另一个序列b[i]，生成方法是b[i]=a[1]^a[2]^...^a[i-1]^a[i+1]^...^a[n]。给定序列b[i]，问a[i]。

**comment**

直接对着样例蒙了一下a[i]=b[1]^b[2]^...^b[i-1]^b[i+1]^...^b[n]好像是对的，然后想证明的时候发现为什么要确保n是偶数。

**题解**

将b[1]到b[n]全部异或起来，发现值相当于a[1]到a[n]全部异或了(n-1)=1（mod 2）次，说明a和b的异或和应该是一样的。所以按蒙的方式算一次就行了。