2023-2024:teams:al_in_and_back_to_whk:24-nowcoder-3:f
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2023-2024:teams:al_in_and_back_to_whk:24-nowcoder-3:f [2024/07/24 23:51] 11231123 |
2023-2024:teams:al_in_and_back_to_whk:24-nowcoder-3:f [2024/07/24 23:55] (当前版本) 11231123 |
||
|---|---|---|---|
| 行 15: | 行 15: | ||
| 然后就到了关键的地方，我们考虑一个函数 $S(r,s)=\sum_{p \ge s}{C(p,r-p)}$，那么我们要求的实际上就是 $S(r,\lfloor r/2 \rfloor +1)$ 。下面我们来正面推导一下其递推式。 | 然后就到了关键的地方，我们考虑一个函数 $S(r,s)=\sum_{p \ge s}{C(p,r-p)}$，那么我们要求的实际上就是 $S(r,\lfloor r/2 \rfloor +1)$ 。下面我们来正面推导一下其递推式。 | ||
| - | 首先我们利用 $C(p,q)$ 的递推式可以得到第一步展开就是 $S(r,s)=\sum_{p \ge s}{(n-p+1)*C(p-1,r-p)+(m-(r-p)+1)*C(p,(r-p)-1)}$。这个形式其实不太好直接看出来递推式，我们考虑稍微变形一下，将求和中前一部分中的 $p-1=p1$ ，$S(r,s)=\sum_{p \ge s}{(n-p+1)*C(p-1,r-p)+(m-(r-p)+1)*C(p,(r-p)-1)}$ | + | 首先我们利用 $C(p,q)$ 的递推式可以得到第一步展开就是 $S(r,s)=\sum_{p \ge s}{(n-p+1)*C(p-1,r-p)+(m-(r-p)+1)*C(p,(r-p)-1)}$。这个形式其实不太好直接看出来递推式，我们考虑稍微变形一下，将求和中前一部分中的 $p-1=p1$ ，那么就有：$S(r,s)=\sum_{p \ge s}{(n-p)*C(p,r-1-p)+(m-(r-p)+1)*C(p,r-1-p)}+(n-(s-1))*C(s-1,r-s)$。将求和中的两项合并起来就是：$S(r,s)=(n+m-r+1)*S(r-1,s)+(n-s+1)*C(s-1,r-s)$，也就是题解中的式子。 |
| + | |||
| + | 于是我们就可以开始递推了，每次再判断一下当前的下界有没有变大，变大就把多余的那一项减掉就行了。 | ||
2023-2024/teams/al_in_and_back_to_whk/24-nowcoder-3/f.txt · 最后更改: 2024/07/24 23:55 由 11231123
