2020多校Fibonacci Sum

Fibonacci Sum题目难易度:简単(しかし私はしていません)まずデータnを见て、kはすべて10^18时间の复雑度はO(n)がほとんどなくて、マトリックス乗算pass.今問題を解決して、多くの問題解の参考を探しました.この大物の考えが一番はっきりしていると思います.リンクを添付して自分で振り返ってコメントを追加します.

#include 
using namespace std;
const int MAXN = 1e5 + 10;
const long long mod = 1e9 + 9;
long long fac[MAXN], inv[MAXN];
long long fastpow(long long a, long long b) {
    long long ans = 1;
    a %= mod;
    while (b) {
        if (b & 1)ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}
void Init() {
    fac[0] = inv[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fac[i] = fac[i - 1] * i % mod;//    
        inv[i] = fastpow(fac[i], mod - 2);//    
    }
}

long long Solve(long long n, long long c, long long k) {
    long long ans = 0;
    long long A = fastpow(691504013, c % (mod - 1)), B = fastpow(308495997, c % (mod - 1));
    long long a = 1, b = fastpow(B, k), ib = fastpow(B, mod - 2);
    for (int i = 0; i <= k; i++) {
        long long x = a * b % mod;//  ，       
        long long C = fac[k] * inv[i] % mod * inv[k - i] % mod;//   
        long long sum = x * (fastpow(x, n % (mod - 1)) - 1 + mod) % mod * fastpow(x - 1, mod - 2) % mod;//    
        if (x == 1) sum = n % mod;
        if ((k - i) & 1) ans -= sum * C % mod;//      
        else ans += sum * C % mod;
        ans %= mod;
        a = a * A % mod;//            ，         ，         
        b = b * ib % mod;
    }
    long long num = fastpow(383008016ll, mod - 2);
    ans = ans * fastpow(num, k) % mod;//         
    ans = (ans % mod + mod) % mod;
    return ans;
}

int main() {
    int t;
    long long n, k, c;
    Init();
    scanf("%d", &t);
    while (t--) {
        scanf("%lld%lld%lld", &n, &c, &k);
        printf("%lld
", Solve(n, c, k));
    }
    return 0;
}