题目大意

  给定一幅 $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$，按如下方式生成剩余数据：

  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

题目大意

  求

  其中 $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

题目大意

  Alice 有 $n$ 血，Bob 有 $m$ 血。Alice 和 Bob 轮流攻击对方，Alice 先手，每次攻击如果命中则对方扣 $1$ 点血，否则无事发生。Alice 命中率为 $p$，Bob 命中率为 $q$。若有人血量 $\le 0$ 则死亡，游戏结束。
  求到最后 Alice 的生命值大于 $0$ 的概率，对 $998244353$ 取模。

  $n,m \leq 10^5$
  多测，$T \leq 10^4$，$\sum(n+m) \leq 5 \times 10^6$
  1s

题目大意

  给定一棵 $n$ 个点的目标树，以及 $m$ 棵模板树，每棵模板树有一个单价 $c_i$，数量无限多。这里的树都是无根树。
  现在要用若干模板树拼成目标树（就是用模板去覆盖目标树，使得目标树的每个点恰好被覆盖一次），求最小代价。

  $n \leq 500,\ m \leq 200$，所有模板树的结点数总和 $N \le 500$
  $c_i \leq 10^6$
  1s

题目大意

  一个置换可以看成是有 $a_1$ 个长度为 $1$ 的环 + $a_2$ 个长度为 $2$ 的环 + …… + $a_n$ 个长度为 $n$ 的环，满足 $\sum_{i=1}^n i\cdot a_i=n$ 。
  记 $f(a_1,a_2,\cdots,a_n)$ 表示各种环的数量分别为 $a_1,\cdots,a_n$、长度为 $n$ 的置换的数量，现给定 $n,p$（$p$ 是质数），问有多少种不同的数列 $a_1,\cdots,a_n$，满足 $p \not|\ f(a_1,a_2,\cdots,a_n)$ 。

  $n \leq 10^{18},\ \ 2 \leq p \leq 10^5$
  多测，$T \leq 10^5$，2s

题目大意

  记 $f(n)$ 表示 $\sum_{d|n,\ \gcd(n,\frac nd)=1}d$，给定 $n$，求 $\sum_{i=1}^n f(i) \bmod 10^9+7$。

  $n \le 10^{12}$
  多测，10 组数据，20s，32768K 。