题目大意

  有一个正整数序列 $a_1,\cdots,a_n$，每次操作可以把一个数 $+1$ 或 $-1$，但要使其仍为正数。问至少多少次操作，使得整个序列的 $\gcd$ 不为 $1$。
  $n \le 2 \times 10^5$
  2.5s

题目大意

  一个二分图，设左边的一个点集为 $S$，记它在右边的邻集为 $N(S)$，如果 $|S|>|N(S)|$，则称 $S$ 是 critical 的。
  给定 $n,k$，构造一幅左右各 $n$ 个点的二分图，使得 critical 的点集数量恰好为 $k$。

  $n < 20,\ 0 \le k < 2^n$
  1s

  就感觉年终了又新年了想要说些什么话，补一补漏的这么多游记（x

题目大意

  给定一个长度为 $n$ 的、仅含 a,b 的字符串 $s$，每次可以对 $s$ 做下列操作：

• 在任意位置添加或删除 aa；
• 在任意位置添加或删除 bbb；
• 在任意位置添加或删除 ababab。

  问 $s$ 能变成多少种长度为 $x$ 的字符串，答案模 $998244353$。

  $n \le 3 \times 10^5,\ x \le 10^9$

题目大意

  给定一幅 $n \times m$ 的地图，地图由“.”和“#”构成，“.”表示空地，“#”表示障碍。
  求这个地图沿垂直和水平方向分别 shift 多少，能使空地形成一个连通块。求出所有可能的 shift 方案。

  $n,m \le 200$
  2s

题目大意

  有 $n$ 个人排队准备录视频，轮到第 $i$ 个人的时候，如果他被商家钦定，或者排他前面的至少有 $a_i$ 个人录视频，他就会录视频。问商家至少钦定多少人，使得最终录视频的人数 $\ge m$。
  $m \le n \le 5 \times 10^7$，由于输入过大，仅输入 $a_1$，接下来给出 $k$ 段生成器，每段生成 $c_i$ 个 $a$（保证 $\sum_{i=1}^k c_i=n-1$），每个生成器形如 $a_i=(x a_{i-1}+y) \bmod z$，$z$ 为质数。
  $k \le 10^5$
  4s, 64MB

题目大意

  电影院观众席为 $n \times m$ 的方阵，其中 $k$ 个座位 $(r_1,s_1),\cdots,(r_k,s_k)$ 已经被占。问从剩下的座位中，选择某一行的一个连续段（长度至少为 $1$）的方案数。

  $n,m \leq 10^5,\ \ 1 \le k \le nm$，给定 $r_1,s_1,a_r,b_r,a_s,b_s$，按如下方式生成剩余数据：

$$r_i = (r_{i-1} \cdot a_r + b_r) \bmod n \\ s_i = (s_{i-1} \cdot a_s + b_s) \bmod m$$

  2s

题目大意

  给定一个 $SA$ 数组和一个 $height$ 数组，其中 $height$ 数组的一些位置被抹掉了（用 $-1$ 表示），要求还原一个字典序最小的字符串，保证一定有解。

  $n \leq 5000$

  这学期一口气选了三门 AI 课（AI、模式识别、NLP），初衷就是想深入了解以后能更有底气地说“我不喜欢AI”（x
  然后三门课内容高度重复，每个知识点平均听三遍。。。其中最近发生的重合是，人工智能实验先要写一个 RNN 做关键词提取，然后 NLP 课要用 BiLSTM+CRF 做中文分词，完了之后还要用 LSTM 做语言模型。。。
  于是这位可怜的老 C++ 选手在用 C++ 写完了 KNN、决策树、PLA、逻辑回归、BPNN 之后，不得不在一个月内从 python 语法入门摸爬打滚到机器学习带师（x

  这篇博客大概只是分享和记录，不是教程。我认为学 AI 最好的方式是在学校里上课（有老师带，有同学一起讨论），或者买本书来学。在网上找博客自学是很不靠谱的。

题目大意

  有一棵 $n$ 个结点的树，现有 $m$ 个人位于不同的结点，那么要让他们在同一结点相遇的话会有一个最小总路程。而“$m$个人位于不同结点”共有 $\binom nm$ 种情况，求这 $\binom{n}{m}$ 种情况的最小总路程之和，模 $10^9+7$。

  $m \le n \le 10^6$
  多测，$T \le 1000$，$\sum n \le 2\times 10^6$
  2s

  把那些别人认为显然的而我死也想不出来的东西，都记下来

Task

  做作业的时候遇到了这么个题：

Alice and Bob love each other, so they decide to use a single RSA modulus $N$ for their key pairs. Of course each of them does not know the private key of the other. Mathematically, Alice and Bob have their own key pairs $(e_A,d_A)$ and $(e_B,d_B)$ sharing the same $N$. Demonstrate how Bob can derive the private key of Alice.

  大意是说，Alice 和 Bob 用传统的 RSA 进行交流，但用的是同一个模数 $N$。问 Bob 如何利用这一点来破解 Alice 的私钥。

题目大意

  对于集合 $a$，定义集合 $S(a)$ 表示集合 $a$ 生成的集合，生成方式为通过以下步骤任意多次：

• 初始，$S(a)=a$；
• 若存在 $x,y \in S(a)$，但是 $x\oplus y \not \in S(a)$，将其插入到 $S(a)$ 中。

  现在给定集合 $a,b$，你需要维护一个数据结构，支持以下操作，共 $m$ 次：

• $1\ x$，表示插入 $x$ 到集合 $a$ 中，保证插入之前 $x \not\in a$
• $2\ x$，表示插入 $x$ 到集合 $b$ 中，保证插入之前 $x \not\in b$
• $3\ x$，表示从集合 $a$ 中删除元素 $x$，保证删除之前 $x \in a$
• $4\ x$，表示从集合 $b$ 中删除元素 $x$，保证删除之前 $x \in b$
• $5$，表示询问：输出 $|S(a) \cup S(b)| \bmod 998244353$​，即集合并的元素个数

  
  $|a|,|b| \le 10^5,\ \ m \leq 2\times 10^5$，所有的集合元素 $\in [0,2^{63})$
  多测，时限比较迷。。反正 $O(n \log^2 x)$ 跑不过

题目大意

  给定一幅 $n$ 个点 $m$ 条边的无向连通图，边有边权，定义 $D(i,j)$ 表示从 $i$ 到 $j$ 的所有路径中，次大边权最小是多少（如果路径只有一条边那么次大边权为 $0$）。
  求 $\sum_{i=1}^n \sum_{j=i+1}^n D(i,j)$。

  $n \leq 10^5,\ \ m \leq 150000$，边权互不相同且 $\le 10^9$
  1s

题目大意

  给定 $n$ 个由 N 和 B 组成的字符串 $s_1,\cdots,s_n$，一个字符串可以做如下操作：增加或删去一个 B 我没有骂人、增加或删去一个 N、增加或删去一个 NB、增加或删去一个 BN。定义两个字符串的距离为：对一个字符串做最少多少次操作，可以使两个字符串的 N、B 数量分别相等。
  现给定 $s_1,\cdots,s_n$，求一个也由 N、B 构成的字符串 $t$，使得 $t$ 到 $s_1,\cdots,s_n$ 的最大距离最小。

  $n \leq 3\times 10^5,\ \ \sum|s_i| \leq 5 \times 10^5$
  3s

题目大意

  求

$$\sum_{k=0}^n f(k) \times x^k \times \binom{n}{k} \pmod p$$

  其中 $n,x,p$ 为给定整数，$f(k)$ 为给定多项式 $f(k)=\sum_{i=0}^m a_ik^i$ 。

  $n,x,p,a_i \le 10^9,\ \ m \le \min(n,1000)$
  1s