近期几道ABC的G题总结

ABC476G：数位dp + 分治 + 贪心

先从分治的角度考虑两个区间怎么合并

我们考虑对于一个区间，我们如果从合并的角度来说，只关心每个上升子序列开头和结尾1的数量。所以这本质可以用两个数组来存。$a_i$ 表示开头popcount为 $i$ 有多少个子序列，$b_i$ 代表结尾。中间怎么连不重要。

现在考虑两个区间合并。显然从贪心的角度考虑，我们希望用 $b_{1i}\to a_{2j}$ 尽可能多 ($i<j$)，那直接暴力贪心匹配即可。

我们现在回到原题，考虑数位dp。$f(i,0/1,0/1)$ 表示后 $i$ 位，左右是否抵上下界，得到的 $a,b$ 序列。我们往下枚举这位填0或1，然后继续往下。合并过程不过是先把填1的ab序列整体右移一位，然后按照上述方式合并即可。

由于 $f(i,0,0)$ 不受 $L,R$ 影响，所以可以记忆化，复杂度就对了。

ABC475G：dfs + 质因数

考虑没有 $D$ 的限制我们怎么做。显然直接dfs，枚举每个质因子的指数，而且我们可以很轻松地判断出这个指数一定单调不增。

现在考虑有 $D$ 的限制怎么做。首先如果 $D$ 有一个足够大的质因子（比如大于50），那对我们显然没有影响。否则，我们只需要让 $D$ 至少一个质因子的我们构造的数的指数小于 $D$ 这个质因子的指数。那我们只需要枚举这个质因子的指数即可，然后dfs。而除了这个质因子，剩余的所有质因子继续满足指数单调不增即可。

ABC474G：构造

显然最大值是一直横着走然后不断折返，最小值是一直竖着走不断折返。

我们考虑先按照最大值走。然后我们考虑现在开始反悔。我们试图把最后两列变成竖着走，然后我们计算一下新的值。如果可以，我们就去掉最后两列递归下去。如果不可以，说明我们最后两行必须横着走，我们就去掉最后两行递归下去即可。

ABC473G：DP + 分治NTT

考虑如果一张照片被翻过，然后不是我们要翻的，我们可以转化为我们也把它取走（就是卡片数量也减1），但这次花的代价是2。这个转化显然是等价的。

我们可以再转化一下。由于每张卡片至少吃一次，我们可以先让 $K=K-N$，那样子一次抽中的代价是0，抽不中的代价是1。

然后我们设 $f_{i,j}$ 代表剩 $i$ 张卡片，用 $j$ 步吃完的概率，显然：

$$f_{i,j}=\frac 1 i({f_{i-1,j}}+(i-1)f_{i-1,j-1})$$

把 $\frac 1 i$ 去掉，最后答案乘个 $n!$。剩下的式子从几何角度考虑，就是在 $i$ 个数中抽 $j$ 个数相乘求和。

令 $F_i(x)=1+ix$，那么答案就是 $[x^{K}]\prod_{i=0}^{n}F_i(x)$，分治NTT即可。