2023-2024:teams:al_in_and_back_to_whk:24-nowcoder-2:j
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2023-2024:teams:al_in_and_back_to_whk:24-nowcoder-2:j [2024/07/19 19:25] 11231123 [题解] |
2023-2024:teams:al_in_and_back_to_whk:24-nowcoder-2:j [2024/07/19 19:28] (当前版本) 11231123 [题解] |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| $f(N)=\sum_{i=0}^{N/2}{\binom{N}{2i}*(2i-1)!!*a^{N-2i}}=\sum_{i=0}^{N/2}{\binom{N/MOD}{2i/MOD}*\binom{n}{2i\%MOD}*(2i-1)!!*a^{N-2i}}$ 。这个时候我们先简单看看现在这个式子，首先可以看出来如果 $2i-1 \ge MOD$ 那么就没有意义了。然后就是如果 $2i-1 < MOD$ 那么相当于 $2i \le MOD-1$，于是有 $\binom{N/MOD}{2i/MOD}=\binom{k}{0}=1$ 。最后我们可以发现要想让 $\binom{n}{2i\%MOD}$ 不是 $0$ ，那么一定有 $2i \le n$ 。所以我们可以得到一个很重要的东西就是 $f(n+k*MOD)=a^{k*MOD}*f(n)=a^{k}*f(n)$ 。 | $f(N)=\sum_{i=0}^{N/2}{\binom{N}{2i}*(2i-1)!!*a^{N-2i}}=\sum_{i=0}^{N/2}{\binom{N/MOD}{2i/MOD}*\binom{n}{2i\%MOD}*(2i-1)!!*a^{N-2i}}$ 。这个时候我们先简单看看现在这个式子，首先可以看出来如果 $2i-1 \ge MOD$ 那么就没有意义了。然后就是如果 $2i-1 < MOD$ 那么相当于 $2i \le MOD-1$，于是有 $\binom{N/MOD}{2i/MOD}=\binom{k}{0}=1$ 。最后我们可以发现要想让 $\binom{n}{2i\%MOD}$ 不是 $0$ ，那么一定有 $2i \le n$ 。所以我们可以得到一个很重要的东西就是 $f(n+k*MOD)=a^{k*MOD}*f(n)=a^{k}*f(n)$ 。 | ||
| + | 所以我们就相当于是只需要跑完模数范围内的递推就可以了，就是说在3s要跑1e9的递推，在加上循环展开后就通过了这个题。 | ||
2023-2024/teams/al_in_and_back_to_whk/24-nowcoder-2/j.txt · 最后更改: 2024/07/19 19:28 由 11231123
