多校A层冲刺NOIP2024模拟赛05
T1 好数（number）
签到题
首先 \(O(nV)\) 的背包暴力是显然的，注意到本题只需要合法性，状态只有 \(0/1\)，上 \(bitset\) 优化转移即可。
时间复杂度 \(O(\frac{nV}{w})\)。
T2 SOS字符串（sos）
签到题
计数题难点在不重不漏，而本题则主要是不重。
考虑一种好的计算 sos 贡献的方式，即可以钦定第一次出现时才会产生贡献（ sosos 只计算最左边 \(3\) 个贡献）。
上组合数学显然很麻烦，会分讨很多东西，考虑 \(DP\)。
设计状态 \(f_{i,j,k}\) 表示前 \(i\) 个，已经有 \(j\) 个 sos，结尾情况为 k 时的方案数。由于只有大于等于 \(3\) 个 sos 才有贡献，所以将大于等于 \(3\) 个 sos 压缩到一维（算是一个小 trick ）。
结尾情况钦定好情况，转移大力分讨乘上系数就好了。
时间复杂度呈线性。
可以矩乘优化变为 \(O(wlogn)\)，其中 \(w\) 为一次矩乘的复杂度。
T3 集训营的气球（balloon）
计数题，DP，背包，退背包
注意到 \(c\) 很小，是解题的关键点，考虑容斥去计算恰有 \(1～c-1\) 的方案数，答案即为总方案数减去上述方案总数。
这显然是一个背包问题，直接做一次的复杂度是 \(O(nc)\)，加上询问复杂度就爆炸了。
注意到本题背包的性质，显然转移顺序是没有任何影响的，并且转移具有可逆性。
并且本题是单点修改，所以可以使用退背包。具体的直接逆向减去原点的影响，再重新加入新点的影响。
时间复杂为 \(O(q(c+log))\)，多个 \(log\) 是由于会计算逆元。
T4 连通子树与树的重心（tree）
计数题，DP，树的重心，退背包
不要用题目描述重心的定义去做本题，即使此最大值取到最小的节点被称为整个树的重心，而是考虑更数学的定义，即以树的重心为根时，所有子树的大小都不超过整棵树大小的一半 (size/2)。
首先正常求出重心，对重心个数进行分讨：
若为 \(2\) 个，显然将重心相连的边删去后两个以重心为根的树的 \(size\) 是相等的，直接树上背包分别求出这两个点所在连通块且不包含对方所有 \(size\) 的方案数，答案即为 \(\prod_{i=1}^{n}size_{rt_1,i}size_{rt_2,i}\)。
时间复杂度瓶颈在树上背包为 \(O(n^2)\)。
若为 \(1\) 个，考虑重心的定义所有子树的大小都不超过整棵树大小的一半，并且只有一个重心，记一个点所在连通块总大小为 \(tot\)，限制变为所有子树的大小都不超过 (tot-1)/2，证明考虑当有两个重心的时候 \(tot\) 必定为偶数。这个限制能使用背包解决，具体的记 \(f_{i,j}\) 表示 \(i\) 所在连通块且不包含其父亲时大小为 \(j\) 时的方案数，求出 \(f\) 数组，然后外层枚举重心所在连通块 \(tot\) 的大小，内层枚举重心儿子将上界设置为 \((tot-1)/2\) 再用一个新的数组再跑一遍背包就行。
这样就得到一个 \(O(n^3)\) 的做法，期望得分 50 pts。
考虑容斥优化，同 T3，即计算总方案数减去不合法方案数。注意到一个方案不合法当且仅当子树中存在一个 \(size\) 大于限制，而由于限制是 \((tot-1)/2\) 不满足这个限制的子树只会有一个，考虑枚举不合法子树即可，不合法方案即为
\(\sum_{v\in son_{rt}}\sum_{tot=1}^{n}\sum_{j=(tot-1)/2+1}^{min(size_v,i)}f_{v,j}\ g_{rt,tot-j}\)
其中 \(g\) 是去除去了点 \(v\) 影响对应的 \(f\)，同 T3 一样可以退背包求解 \(g\) 数组。这一部分的时间复杂度即为上述式子，复杂即为 \(O(n^2)\)。
总时间复杂度为 \(O(n^2)\)