\(\operatorname{Update\;on\;2025.9.26}\)
ABC422F
dp题。
考虑费用提前计算，设 \(f_{i,j}\) 表示当前在点 \(i\)，还需要走 \(j\) 步的最小花费。
复杂度 \(O(n(n+m))\)。
ABC422E
随机化，我们随机地从中选择两个点计算最多有 \(\frac{3}{4}\) 的概率失败。
于是直接随机 \(T\) 次，成功概率大概为 \(100\%-(\frac{3}{4})^T\)，取 \(T\) 为 \(20\) 时失败概率就比较低了。
复杂度 \(O(Tn)\)。
ARC205D
树形dp+贪心
设 \(f_x\) 表示以 \(x\) 为根的子树内最多匹配的对数。
首先考虑一个点 \(x\)，如果重儿子 \(son_x\) 的子树大小小于等于所有 \(x\) 儿子子树大小之和的一半，说明存在一种方案使得匹配对数为 \(\lfloor\frac{siz_x-1}{2}\rfloor\)。
否则我们可以优先匹配 \(son_x\) 子树，接着让其他所有子树与重儿子匹配。
如果重儿子子树大小不够匹配了，那么必然存在一种方案使得可以匹配到最大匹配数 \(\lfloor\frac{siz_x-1}{2}\rfloor\)。
答案为 \(f_1\)。复杂度线性。
ARC205E
考虑类似根号地平衡复杂度。
设 \(f_{i,j}\) 表示二进制下后 \(10\) 为 \(j\)，前 \(10\) 位是 \(i\) 的子集的所有数字的乘积。
加入第 \(k\) 个数时，枚举 \(a_k\) 的前 \(10\) 位的超集。
查询时枚举 \(a_k\) 后 \(10\) 位的子集。
复杂度 \(O(n\sqrt V)\)。
Code Trick：枚举子集和超集
for(int T=0;T!=S;T=((T^S)-1)&S^S) //从小到大枚举子集
for(int T=S;T!=0;T=(T-1)&S) //从大到小枚举子集
for(int T=S;T!=U;T=(T+1)|S) //从小到大枚举超集
for(int T=U;T!=S;T=((T^S)-1)&(U^S)^S) //从大到小枚举超集
ARC205B
\(\operatorname{Ad-hoc}\)
注意到一个点连的黑边数量奇偶性不变。
可以证明，必定存在一种方案使得一个点达到奇偶性最大。
因为如果不行，则存在至少一个点有两个以上连接的白边，操作这两个白边相连的边一定会让答案增加，归纳可证。
于是可以直接找出哪些点与 \(n-1\) 奇偶性不同，并钦定让那些白边互相共享，这样保证了白边个数尽量小。
可以证明奇偶性不同的点为偶数个，所以答案为 \(C_{n}^{2}-\frac{X}{2}\)，其中 \(X\) 为与 \(n-1\) 奇偶性不同的点个数。
复杂度 \(O(n+m)\)。
ABC423F
容斥。
设 \(f_S\) 表示 至少 满足 \(S\) 中限制的年份数，显然有 \(f_S=\left\lfloor\frac{Y}{\displaystyle\operatorname{lcm}_{i\in S} a_i}\right\rfloor\)。
假设 \(J\in K,J\ne K\)，则恰好满足 \(K\) 集合限制的年份数会被恰好满足 \(J\) 集合限制的年份数重复统计共计 \(C_{|K|}^{|J|}\) 次。
考虑容斥。
假设需要消掉方案数满足 \(m+k\) 个限制，考虑构造合适的容斥系数。
打表发现，其中一个容斥系数为 \(C_{m+k}^m\)。
证明：
证毕。
main() {cin>>n>>m>>Y;FOR(i,1,n) a[i]=llread();FOR(i,0,n) C[i][0]=1;FOR(i,1,n) FOR(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1]);LL ans=0;FOR(S,1,(1<<n)-1) {LL lm=1;int sz=__builtin_popcount(S);if(sz<m) continue;FOR(i,1,n) {if(S>>(i-1)&1) {if(1.*lm/gcd(lm,a[i])>1.*Y/a[i]) {lm=-1;break;}lm=lm/gcd(lm,a[i])*a[i];}}if(lm==-1) continue;if((sz-m)&1) ans-=C[sz][m]*(LL)(Y/lm);else ans+=C[sz][m]*(LL)(Y/lm);}cout<<ans<<"\n";return 0;
}
ABC424G
神秘 dp 题。
考虑限制的形式：\(\forall s\subseteq S,\displaystyle\sum_{i=1}^n\min(a_i,|s|)\ge \sum_{k\in s}b_k\)。
发现只需要按照 \(b\) 从大到小排序即可弱化为 \(\forall j\in[1,|S|],\displaystyle\sum_{i=1}^n\min(a_i,j)\ge \sum_{k=1}^j b_k\)。
设 \(f_{i,j,k}\) 表示考虑到第 \(i\) 场歌会，选择了 \(j\) 场，且选择的歌会的 \(b_i\) 之和为 \(k\) 的最大兴奋度。
复杂度 \(O(nm^3)\)。