Codeforces Round #596 (Div. 1)

前言

康复训练Day2。wdnmd又双叒叕是赛后1A。

题解

A - p-binary

考虑是否存在使得能被表示成个之和，即二进制表示中的个数小于等于且本身大于等于。暴力枚举就行辣。

B - Power Products

用一个长度为的记录每个数小于的质因子的次数对取模的情况，并根据剩余的最大质因子存放到对应的中，对每个数求一个补集然后查询补集出现次数就好了。

C - Rock Is Push

假设没有石头。
记为在这个位置先向下走走到的方案数，为在这个位置先向右走到的方案数。
那么显然有转移方程还有。
分析发现被推过去的石头并不影响转弯之后的走法，只影响能沿着推石头的方向走多远，即状态转移的范围。
如果下边有个石头，则有，同理，如果右边有个石头，则有。
只有一行或一列或是石头的时候要特判一下。

D - Tree Factory

每次操作能把一部分节点的深度-1，那么肯定是每次操作都尽可能影响多的节点比较好。
考虑按照dfs序来安置节点，贪心地优先安置高度低的子树，回溯的时候把剩余的一整条链往上提。