广二联考题解补全计划：

---

第十七套：
T1：取模性质，倍增
T2: DP优化，状态优化
T3：容斥原理，数位DP

T1:

首先先提一个关于取模的性质，一个数对一个比它小的数取模，大小一定减半，考虑对 $ \frac {n}{2}$ 分治即可。

我们先预处理出来每个数后面第一个比他小的位置，这样形成一个树形结构。

根据前面的性质，有：
\(S_p(x) = \lfloor \dfrac{x}{a_q} \rfloor S_q(a_q-1) + S_q(x \bmod a_q)\)，预处理出 \(S_p(a_p-1)\) 就可以做到只处理log次，每次还需要树上倍增找下一个比他小的，那么两只log即可快速查询

T2：
萌熊原题，写一下思考过程：

1. 因为只关心英雄集合，我们贪心地让所选英雄集合去对抗尽可能小的
   怪兽

2. 于是 \(n^{3}\) 式子很好想，我们枚举集合大小 $k $ ,那么设计 \(f_{i,j}\) 枚举到第i个英雄，赢了j场，转移就不写了

3. 优化前途在于枚举状态，我们发现我们 \(k\) 是必须要枚举的，前面设计的状态如果我们要求英雄输就很不好处理，我们考虑前后两端枚举，前面枚举赢的集合，后面枚举输的集合，最后再拼起来

4. 发现不能直接拼，我们找到这样一个位置 \(a_k < b_p < a_{k+1}\)，这样我们发现前面没赢的都能在后面输，后面没输的都能在前面赢。在这个位置拼起来就行了

T3：

UNR好题

之前学容斥有一个式子是 $ x_i \le b_i \ \ \ 求 \sum x_i=m$ 的方案数，那我们容斥做就好了

这个题是小于等于，那我们新加一个盒子，表示在这个盒子里的我们扔掉。

\[Ans=\sum_{S \in \left \{ 1,...m \right \} } (-1)^{|S|} \binom{n+m-(\sum_{i \in S} b^i-c+1)}{m} \]

设 $ A=n+m+k(c-1) $,把后面那一坨拆拆，得到一个下降幂形式,把它看做多项式：

拆一下系数，有

\[g_{0,0}=1,g_{i,j}=g_{i-1,j} \times (A-i+1) - g_{i-1,j-1} \]

下面你要求后面那一坨 \(b^i\) 的和

设计 \(f_{}\)