题目大意

  给定一个长度为 n 的小写字符串，问有多少个子串没有循环节。
  n<=1e5

题目大意

  如果一个序列，长度为偶数，从中间劈开之后左边跟右边是相同的，则称这个序列是好的。例如 {1, 2, 3, 1, 2, 3} 是好的，{1, 2, 3, 1, 2, 4} 是不好的。
  现在要你构造一个序列，满足三个条件：

1. 序列长度 <=200
2. 元素大小 <=100
3. 恰有 n 个子序列是好的。

  $n<=10^{12}$

题目大意

  有三个 $n\times n$ 的矩阵 $A$、$B$、$C$，问 $A\times B$ 是否等于 $C$。
  元素在模 $10^9+7$ 意义下。
  $n \leq 1000$

前言

  江苏，感觉规模比广东小，但是也是很有质量的地方。

  大概是最后一次跑到别人的省选去了。。。
  然后跟省队好像差了 30 分？？

  那么几趟练兵下来，都挂彩了。ZJOI 爆 0，JSOI 进不了队，接下来 GDOI。。。退役？？？

题目大意

  有一棵树，有 $n$ 个点。现在将所有距离为 $2$ 的点对也连一条边。
  给出最终的图，请构造一棵原来的树。

  多组数据，$T \leq 10,\ \ n \leq10^4,\ \ m \leq 10^5$

题目出自北方大学acm多校训练赛第四场

V1（原题）

题目大意

  定义函数 $f(n,0)=1$， $f(n,m)=\sum_{d|n}f(d,m-1) \cdot f(\frac{n}{d},m-1)$
  给定 $n,m$，求 $f(n,m) \bmod 10007$
  多组数据，$T \le 10,\ n \le 10^9,\ m \le 50$

  （这题我想了十几分钟没想出来，然后jasonvictoryan走过来，想了10秒钟，想出了V2解法。。。）

V1（【COCI 2016/2017 #5】Poklon）

题目大意

  给出一个长度为 $n$ 的序列 $a_1…a_n$。
  有 $Q$ 次询问，每次询问序列中的一个区间，有多少个数恰好出现两次。
  $n,Q \leq 5 \times 10^5$

转载自 ZYQN’s Database，但是原文找不到了。

设我们要分解 $n$，$n=n_1n_2(n_1<=n_2)$，我们构造的序列为 $a_i$，$a_i~mod~n_1=b_i$

因为 $a_i$ 可近似看为随机序列，根据生日悖论可以推出其出现循环的期望步数为 $\sqrt n$，$b_i$ 同理。

因为 $n>n_1$，所以在 $b_i$ 循环之后，$a_i$ 有很大可能没有进入循环，此时 $a_i-a_j=(k_in_1+b_i)-(k_jn_1+b_j)=(k_i-k_j)n_1+(b_i-b_j)=(k_i-k_j)n_1$。于是求 gcd 即可求出 $n_1$。

因为 $b_i$ 的循环期望是 $\sqrt n_1$，而 $n_1<=\sqrt n$，所以最后是 $O(n^{\frac{1}{4}})$

题目大意

  有 n 个工人，每个工人的工作时间为 l[i]…r[i]。
  你要把工人分成 p 个组，每个组的贡献是该组工人的 min(r)-max(l)，即工作时间的交集。
  你的分组要保证每组的贡献是正数，且每个人都要有分组。
  求最大总贡献。
  p<=n<=1000（原题是 200）， l, r<=1e6， 保证有解。

题目大意

  你要构造 $n$ 个数，满足 $m$ 个限制，每个限制条件给出两个长度相等的区间，表示这两个区间的数要一样。比如限制是 [1, 3] 和 [3, 5]，那 {1, 2, 1, 2, 1} 就是满足条件的。
  求方案数。
  $n \le 10^5$

题目

  $k \leq n \leq 50$，方案数 $\bmod 998244353$

题目大意

  有一个错误的树状数组，它的修改往前走，询问往后走（find(0) 的时候返回 0）。
  现在有一个初始全 0 的序列，有两种操作：
  1 x y：在区间 [ x, y ] 中等概率随机一个 i，然后 a[i]=(a[i]+1)%2
  2 x y：询问 ( a[x]+…+a[y] )%2
  求这个错误树状数组对于每个询问回答正确的概率。
  n, m<=1e5

题目大意

  给出一个无重边无自环的无向连通图（n 个点 m 条边），问有多少种再往上加边的方案，使得新图是仙人掌。
  多组数据， n<=5e5， $\sum m$<=1e6

前言

  第一次参加外省的省选呢~
  像往届那样，最后一年周游列国，到处打比赛，目的是积（dao）累（chu）经（qu）验（lang）。
  成绩还没发。。。但是。。。只能说幸好不是我们的省选。。。

题目大意

  给出一个长度为 $n$ 的序列。
  有 4 种操作：
  $1\ l\ r\ c$：给 $a_l,\cdots,a_r$ 加上 $c$；（$c$ 可为负）
  $2\ l\ r\ d$：给 $a_l,\cdots,a_r$ 除以 $d$ 下取整；（$\lfloor-0.5\rfloor=1$）
  $3\ l\ r$：求 $a_l,\cdots,a_r$ 的最小值；
  $4\ l\ r$：求 $a_l,\cdots,a_r$ 的和。

  $n, q \leq 10^5$
  $|a| \leq 10^9,\ |c| \leq 10^4,\ 2\leq d\leq 10^9$