[toc]

由于各种原因，记录可能不是很全

9.14

P4245 【模板】任意模数多项式乘法

P4491 [HAOI2018]染色

二项式反演 + NTT

9.15

P5339 [TJOI2019]唱、跳、rap和篮球

二项式反演 + 暴力卷积
由于数据范围比较小，写得也很暴力，把4个EGF暴力乘起来即可

9.20

P4921 [MtOI2018]情侣？给我烧了！

P4931 [MtOI2018]情侣？给我烧了！（加强版）

神奇的递推

P4389 付公主的背包

传说中的名题，生成函数取 ln 的一个套路

9.21

CF438E The Child and Binary Tree

不戳的生成函数题

P4705 玩游戏

生成函数 + 推式子题，注意分配空间，用到了C++的new和delete来动态申请和释放内存

Edu CF 136 Div.2

A,B

签到，没什么好说的

C-Card Game

好具有迷惑性，明明O(n)就可以出解的
可以大概推出来每次每个人都出点数最大的牌是最优的

$$
f(n) = C(n-1, n/2) + C(n-4, n/2 – 1)[n >= 6] + f(n – 4)
$$

D-Reset K Edges

如果选择一个深度为d的结点，那么操作后以该节点为根的子树的所有结点的深度都会-(d-1)
容易想到二分答案，推一下可以发现，对于一个深度为d且超出lim的结点，为了使它满足条件，当且仅当由它到深度为d-lim+1的祖先的路径上有至少一个结点被操作
优先考虑深度大的进行操作，每次都操作该结点的深度为d-lim+1的祖先，这样是最优的

2022 年上海市大学生程序设计竞赛

I-It Takes Two of Two

i题调了1年qaq
29行处，max(k-4, 0)，不是max(k-2,，0)，因为这个调了一晚上，还手算n=4的样例
f[i][j][k]表示还有i个节点的度为1或2，j个节点的度为1，k个节点的度为1且连接度为1的点

ICPC 2021 昆明

题意：有 $n$ 个珠子排成一排，每次有一定 $p_i$ 概率选中第 $i$ 个，当 $m \to \infty$ 时，求第 $m$ 次操作的期望代价

ICPC 2021 澳门

D.Shortest Path Fast Algorithm

ICPC 2020 南京

题目质量高，当时感觉还不卷，我们6题快速竟然金了

ICPC 2021 EC-Final 西安

打铁了，被博弈大讨论薄纱，差一点点就出了

ICPC 2020 上海

贡献基本只有签到，剩下全靠队友

C. Sum of Log

有点技巧的数位DP，枚举最高位1的位置，把时间复杂度降到一个log

B. Mine Sweeper II

结论是正图和反图的数字之和是相等的，所以答案要么为A的正图，要么为A的反图