Codeforces Round #181 (Div. 2)

2024-09-06 16:14:22

A. Array

模拟。

B. Coach

模拟。

C. Beautiful Numbers

good number的位和最大不超过\(10^7\)，那么只要枚举a或b的个数，然后最多循环7次判断位和是否是good number。

D. Painting Square

因为新划分的4个小矩形也需要为正方形，所以当前长度n必须为奇数，否则无法继续划分。
\(f(i,j)\)表示长为\(2^i-1\)，操作\(j\)次的方案数。
直接分成4部分比较难，所以可以先考虑分成左右两部分，左右两部分继续考虑分成上下两部分。这样转换后就是比较简单的dp了。
推出转移方程后，可以发现是个卷积形式，继续套用fft优化时间复杂度。

E. Empire Strikes Back

假设我们可以将q的所有质因子以及对应指数求出来，那么可以二分p，每种质因子的指数同样可以求。
而对于ai来说，质因子的指数显然是可以统一处理。

最新文章

热门文章