2020-2021:teams:namespace:素数幂次与p进数问题
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:素数幂次与p进数问题 [2020/08/01 09:26] great_designer [Lucas定理] |
2020-2021:teams:namespace:素数幂次与p进数问题 [2020/08/01 23:12] (当前版本) great_designer [二项式展开的部分和] |
||
|---|---|---|---|
| 行 220: | 行 220: | ||
| =====Lucas定理===== | =====Lucas定理===== | ||
| + | |||
| + | ====定理==== | ||
| <html><span style="color:white">不是Lucario</span></html> | <html><span style="color:white">不是Lucario</span></html> | ||
| 行 236: | 行 238: | ||
| $${(x+1)}^p\equiv x^p+1 \mod p$$ | $${(x+1)}^p\equiv x^p+1 \mod p$$ | ||
| + | |||
| + | ====二项式展开的部分和==== | ||
| + | |||
| + | 给定n、m、x，计算多项式取模意义下的值： | ||
| + | |||
| + | $$\sum_{k=0}^{m} C_n^kx^k$$ | ||
| + | |||
| + | 记带余除法： | ||
| + | |||
| + | $$n=n_1p+n_2$$ | ||
| + | |||
| + | $$m=m_1p+m_2$$ | ||
| + | |||
| + | 将幂和组合数同时用Lucas定理拆开，有： | ||
| + | |||
| + | $$\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_1继续迭代，最终只需预处理若干个C_{n_2}^rx^r即可。 | ||
| + | |||
| =====p进数中的平方元===== | =====p进数中的平方元===== | ||
2020-2021/teams/namespace/素数幂次与p进数问题.1596245174.txt.gz · 最后更改: 2020/08/01 09:26 由 great_designer
