[数论][二次剩余应用][组合数][等比数列] ZOJ 3774 Power of Fibonacci

主要是利用了斐波那契数列对mod1e9+9时二次剩余的性质。说起来这个性质也是很奇葩，只见过两次应用这个题目的情况，一个是这个题一个是/cf.
二次剩余的定义是 当存在某个x使得x^2 \equiv d(mod p)成立时，称“d是模p的二次剩余”，当对任意不成立时，称“ d是模 p的二次非剩余”
而对于斐波那契数列有更具体的性质：

所以使用这个性质的话就可以把斐波那契数列转换成一个很容易处理的形式\[ F_n \equiv 276601605(691504013^n-308495997^n)(mod 10^9+9) \].设a=276601605,b=691504013,c=308495997 然后对于题目中的要求\[ \sum_{i=1}^{n}{F_i^k} \]把F用这个公式替代后还是没法直接求，考虑二项式展开，由于对于求和项中的每一项他的k是相同的，所以每次的二项式系数都是相同的，我们可以纵向合并，对于每个二项式系数计算\[\sum_{i=1}^{n}{C_k^jw_i} \],其中\[ w_i=b^ic^{k-i} \]。这是一个等比数列，可以有很多种快速求和的方法，我这里用的公式+分母逆元。遍历0-k的每个二项式系数计算该项累加即可。
坑点：
①那个\[ a/b mod m \equiv a mod(bm)/m \]的公式只能用一次不能递推用。。。这里最好的方式是求出来阶乘的逆元然后用组合数公式直接算，O(k)的复杂度。
② 每个地方都要注意精度，这个n太大了。。。全程long long
代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 15;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 9;
const int maxnode = 1e6 + 5;

typedef long long LL;
typedef unsigned long long ULL;

LL C[maxn], bi[maxn], ci[maxn];

long long extend_gcd(long long a, long long b, long long &x, long long &y)
{
    if (a == 0 && b == 0)
        return -1; //无最大公约数
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extend_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

long long mod_reverse(long long a, long long n)
{
    long long x, y;
    long long d = extend_gcd(a, n, x, y);
    if (d == 1)
        return (x % n + n) % n;
    else
        return -1;
}

LL add(LL a, LL b)
{
    if (a > mod)
        a %= mod;
    if (b > mod)
        b %= mod;
    return a+b>mod?a+b-mod:a+b;
}

LL mul(LL a, LL b)
{
    if (a > mod)
        a %= mod;
    if (b > mod)
        b %= mod;
    LL c=a*b;
    return c>mod?c%mod:c;
}

LL qpow(LL a, LL n)
{
    if (a > mod)
        a %= mod;
    LL res = 1;
    while (n)
    {
        if (n & (1LL))
            res = mul(res, a);
        a = mul(a, a);
        n >>= (1LL);
    }
    return res;
}

LL inv[maxn];

int main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0), cout.tie(0);
    int t;
    LL n, k, ap, wi, ans, tmp, a = 276601605, b = 691504013, c = 308495997, fz, fm;
    C[0] = 1, bi[0] = ci[0] = 1;
    for (int i = 1; i < maxn-1; i++)
    {
        bi[i] = mul(bi[i - 1], b), ci[i] = mul(ci[i - 1], c);
        inv[i]= mod_reverse(i,mod);
    }
    scanf("%d", &t);
    while (t--)
    {
        ans = 0;
        scanf("%lld%lld", &n, &k);
        for (int i = 1; i <= k; i++)
            C[i] = mul(C[i - 1] * (k + 1 - i), inv[i]);//error1
        ap = qpow(a, k);
        LL fuck = 0;
        for (int i = 0; i <= k; i++)
        {
            tmp=C[i];
            wi = mul(bi[i], ci[k - i]);
            if (wi == 1)
            {   //error2
                tmp=mul(tmp,n);
            }
            else
            {
                fz = mul(wi, qpow(wi, n) - 1);
                fm=mod_reverse(wi-1,mod);
                tmp=mul(tmp,mul(fm,fz));
            }
            if ((k - i) % 2 == 1)
                tmp = mod - tmp; 
            ans = add(ans, tmp);
        }
        ans = mul(ans, ap);
        printf("%lld\n", (ans % mod + mod) % mod);
    }
    return 0;
}