[数学推导]对称轴

  • 源自校内模拟赛

    Statement

  • \[(\sum_{i=0}^{p-1}\binom{2i}im^i)\bmod p\]

  • \(1\le m<p\le 10^{14}\) ,\(p\) 为质数

  • 多组数据,数据组数不超过 \(10^4\)

    Solution

  • 神仙题

  • 一个转化:

  • \[\binom{2n}n=\frac 1{(n!)^2}(\prod_{i=1}^n(2i-1))(\prod_{i=1}^n2i)=\frac{2^n}{n!}\prod_{i=1}^n(2i-1)\]

  • 这看上去没什么用

  • 但我们可 (bu) 以 (neng) 想到把 \(\prod\) 里面的每个数都取反后加上 \(p\) 再除以 \(2\)

  • \[ans=\sum_{i=0}^{p-1}\frac{(2m)^i}{i!}\prod_{j=1}^i(2j-1)=\sum_{i=0}^{p-1}\frac{(-4m)^i}{i!}\prod_{j=1}^i(\frac{p+1}2-j)\]

  • \[=\sum_{i=0}^{p-1}(-4m)^i\frac{\prod_{j=1}^i(\lfloor\frac p2\rfloor-j+1)}{i!}=\sum_{i=0}^{\lfloor\frac p2\rfloor}\binom{\lfloor\frac p2\rfloor}i(-4m)^i=(1-4m)^{\lfloor\frac p2\rfloor}\]

  • 于是快速幂套快 (gui) 速乘即可,每组数据 \(O(\log^2p)\)

  • 当然如果你有高超的打表和猜想技巧,这题是可以被打表水过去的

上一篇:bzoj2187: fraction——类欧几里得


下一篇:洛谷P1587 [NOI2016]循环之美