CVBB ACM Team

分类：数学，二次剩余。

题意：给定 $N,C,k$ 求 $F_0^k+F_{C}^k+F_{2C}^k+\cdots+F_{NC}^k(mod 10^9+9)$，其中 $F$ 为斐波那契数列。$N,C\le10^{18},k\le10^5$

题解：斐波那契数列通项公式 $F_i=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^i-(\frac{1-\sqrt{5}}{2})^i)$ ，且 $5$ 是 $10^9+9$的二次剩余，因此我们可以预处理出来 $x=\frac{1}{\sqrt{5}},a=\frac{1+\sqrt{5}}{2},b=\frac{1-\sqrt{5}}{2}$，对于所求的式子可以通过二项式展开来求 $$S=x^k\sum_{i=0}^{k}(-1)^{(k-i)}C(k,i)\sum_{j=0}^{N}a^{jci}b^{jc(k-i)}$$ 对于后面的求和显然可以通过等比数列求和公式计算，因此我们只需枚举 $i=0\sim k$ 即可，注意特判公比为 $1$ 的情况。

comment：利用了斐波那契数列的通项公式以及二次剩余，以及特殊情况的考虑。

分类：

题意：

题解：

comment：

分类：

题意：

题解：

comment：

2020.07.21 Codeforces Round #658(Div. 1)

无