T1-未出现的人
可以想到，对于 nnn 个人中的每一个，O(m)O(m)O(m) 遍历查找是否在 mmm 个出席者中，这样是 O(nm)O(nm)O(nm) 的，可以通过本题。
当然，也有更好的做法，比如字符串哈希，可以做到线性，这里我使用的是又快又好写的 set。把 mmm 个出席者加入到 set 中，再判断 nnn 个人是否在 set 里，如果不在则输出。
时间复杂度：O((n+m)logm)O((n+m) \log m)O((n+m)logm).
空间复杂度：O(n+m)O(n+m)O(n+m).
Code:
T2-GCD
思考一个问题：已知一个 ggg，那么能否快速判断是否有子序列，让其最大公约数为 ggg？容易想到计算所有 ggg 的倍数的最大公约数 g′g'g′，再判断 g′g'g′ 是否等于 ggg 即可。ggg 可以枚举得到。显然，ai≤5000a_i \leq 5000ai ≤5000，所以 ggg 最多是 500050005000 而且卡不满，这样我们就解决了如何选择子序列。
而且，选择所有 ggg 的倍数作为子序列是最优的（比较简单不再赘述）。此时，子序列的最大公约数应该是 g+1g+1g+1，非子序列中的最大公约数直接计算即可。最后取最大值。
虽然 gcd\gcdgcd 带有一只 log\loglog 有概率超时，但是刚才说了，ggg 是卡不满的，所以不用担心。
时间复杂度：卡不满的 O(n2logn)O(n^2 \log n)O(n2logn).
空间复杂度：O(n)O(n)O(n).
Code:
T3-A + B
我是不会告诉你本来想暴力骗分结果不小心过了的
直觉告诉我们如果较小的数据下没有答案，较大数据中也不太可能有。所以枚举 a,ba,ba,b 到 100010001000 即可。
时间复杂度：O(106log106)O(10^6 \log 10^6)O(106log106).
空间复杂度：O(1)O(1)O(1).
Code:
T4-礼物
首先 O(n2m)O(n^2m)O(n2m) 的暴力转移 DP 非常好写，不再说明。考虑优化 DP。
容易想到，每一次购买是独立的，相互不依赖、不影响。所以可以预处理一下。
预处理出进行一次购买，花费为 iii 时候，小 P 所能拿到的最大价值。这个过程 O(n2)O(n^2)O(n2) 枚举即可。
然后就是朴实无华的完全背包了。
时间复杂度：O(n2+m2)O(n^2+m^2)O(n2+m2).
空间复杂度：O(n+m)O(n+m)O(n+m).
Code:
T5-聊天室
如果开始聊天的时刻 l′l'l′ 确定，那么最早结束时间 r′r'r′ 是多少？显然为 l′+d−1l'+d-1l′+d−1。
那么开始聊天的时刻是什么时候呢？显然是 uiu_iui 或者 ljl_jlj 中的一个。
如果网友上线比 Alice 晚，也就是 lj≥uil_j \geq u_ilj ≥ui 的时候。不难想到按照 rj−ljr_j-l_jrj −lj 从大到小排序，再按照 did_idi 从大到小排序，然后双指针求解。（这样就需要我们离线处理）当我们找到了一个满足条件的区间 [lj,rj][l_j,r_j][lj ,rj ] 的时候，记录 lil_ili ，最后判断 [ui,vi][u_i,v_i][ui ,vi ] 中是否有记录即可。
这个过程暴力做是 O(nm)O(nm)O(nm) 的，可以使用树状数组，将 lil_ili 这个点增加 111，最后查询 [ui,vi][u_i,v_i][ui ,vi ] 范围内的和是否为正数。这样是 O((m+q)logn)O((m+q) \log n)O((m+q)logn) 的。
如果网友上线比 Alice 早，也就是 lj<uil_j<u_ilj <ui 的时候，不难想到按照 ljl_jlj 和 uiu_iui 从小到大排序，也可以双指针求解。如果区间 [lj,rj][l_j,r_j][lj ,rj ] 满足 lj<uil_j<u_ilj <ui ，那么记录 rjr_jrj ，最后判断记录中，rjmax{r_j}_{\max}rj max 是否满足 rjmax≥ui+di−1{r_j}_{\max} \geq u_i+d_i-1rj max ≥ui +di −1 即可。同样地，暴力做是 O(nm)O(nm)O(nm)，我使用的是大根堆优化，时间复杂度是
O((m+q)logm)O((m+q) \log m)O((m+q)logm) 的复杂度。
能想到，如果这两种讨论中，满足任意一种，就是 Yes。这样就做完了。
时间复杂度：O((m+q)logn+(m+q)logm)O((m+q) \log n+(m+q) \log m)O((m+q)logn+(m+q)logm).
空间复杂度：O(n+m+q)O(n+m+q)O(n+m+q).
Code:
T6-BFS
题目是一棵树，还求方案数量，还求任意根的方案数量，这是明显的换根 DP 啊！
过程就是一般的换根 DP 的过程。定义 dpudp_udpu 为对于树根节点为 uuu 的时候，子树大小的乘积。状态转移也不是很难得到，如下：
dpv=dpu×(n−sizev)sizev mod 998244353dp_v=\cfrac{dp_u \times (n-size_v)}{size_v} \bmod 998244353 dpv =sizev dpu ×(n−sizev ) mod998244353
容易发现需要逆元处理。注意到 998244353998244353998244353 是质数，且 sizevsize_vsizev 不可能是其倍数，所以直接运用费马小定理即可。用快速幂实现。
定义 ansians_iansi 为根节点为 iii 的随机 BFS 序数量。发现其刚好为有根树的拓扑序数量。得到结论：ansi=n!dpi mod 998244353ans_i=\cfrac{n!}{dp_i} \bmod 998244353ansi =dpi n! mod998244353.
预处理 n!n!n!，并使用快速幂计算逆元。
时间复杂度：O(nlog998244353)O(n \log 998244353)O(nlog998244353).
空间复杂度：O(n)O(n)O(n).
Code:
