2020-2021:teams:namespace:素数幂次与p进数问题
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:namespace:素数幂次与p进数问题 [2020/08/01 10:13] great_designer [Lucas定理] |
2020-2021:teams:namespace:素数幂次与p进数问题 [2020/08/01 23:12] (当前版本) great_designer [二项式展开的部分和] |
||
|---|---|---|---|
| 行 241: | 行 241: | ||
| ====二项式展开的部分和==== | ====二项式展开的部分和==== | ||
| - | 给定n、m、b，计算多项式的值： | + | 给定n、m、x，计算多项式取模意义下的值： |
| - | $$\sum_{b=0}^{m} C_n^bx^b$$ | + | $$\sum_{k=0}^{m} C_n^kx^k$$ |
| 记带余除法： | 记带余除法： | ||
| 行 253: | 行 253: | ||
| 将幂和组合数同时用Lucas定理拆开，有： | 将幂和组合数同时用Lucas定理拆开，有： | ||
| - | $$\sum_{b=0}^{m} C_n^bx^b=\sum_{t=0}^{m_1-1}C_{n_1}^tx^t\sum_{r=0}^{p-1}C_{n_2}^rx^r+C_{n_1}^{m_1}x^{m_1}\sum_{r=0}^{m_2}C_{n_2}^rx^r$$ | + | $$\sum_{k=0}^{m} C_n^kx^k\equiv\sum_{t=0}^{m_1-1}C_{n_1}^tx^t\sum_{r=0}^{p-1}C_{n_2}^rx^r+C_{n_1}^{m_1}x^{m_1}\sum_{r=0}^{m_2}C_{n_2}^rx^r={(1+x)}^{n_2}\sum_{t=0}^{m_1-1}C_{n_1}^tx^t+C_{n_1}^{m_1}x^{m_1}\sum_{r=0}^{m_2}C_{n_2}^rx^r\mod p$$ |
| - | 由于n是固定的，只需预处理若干个C_r^{n_2}x^r即可。 | + | 可以对新的n_1继续迭代，最终只需预处理若干个C_{n_2}^rx^r即可。 |
2020-2021/teams/namespace/素数幂次与p进数问题.1596247994.txt.gz · 最后更改: 2020/08/01 10:13 由 great_designer
