杭电ACM 多校第一场1005

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6755
核心思想：二次剩余加二项式展开加乘法逆元

#include <iostream>
#include <cstdio> 　　　　 //定义输入／输出函数
#include <stack>　　　　　 //STL 堆栈容器
#include <map>　　　　　　 //STL 映射容器
#include<set>
#include <vector>　　　　　//STL 动态数组容器
#include <string>　　　　　//字符串类
#include <iterator>        //STL迭代器
#include <cstdlib> 　　　　//定义杂项函数及内存分配函数
#include <cstring> 　　　　//字符串处理ed
#include<algorithm>
#include<queue>
#include<cmath>
#include<fstream>
#include<ctime>
using namespace std;
#define ll long long 
#define FOR(ITER,BEGIN,END)  for(int  ITER=BEGIN;ITER<END;ITER++)
#define PER(ITER,TIMES) FOR(ITER,0,TIMES)
#define TIME(TIME_NUMBER) PER(_PETER_MRSCO_ITER_,TIME_NUMBER)
#define close_stdin ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define out_put(l,r,aaaa) {for (int i=l;i<=r;i++){cout<<aaaa[i]<<" ";}cout<<"\n";}
const ll mod = 1e9 + 9;
const ll sq5 = 383008016;
const int maxn = 100005;
ll a, b, d, pwa[maxn], pwb[maxn], iv[maxn];

ll qpow(ll p, signed q)
{
    return (q & 1 ? p : 1) * (q ? qpow(p * p % mod, q >> 1) : 1) % mod;
}

ll inv(ll p)
{
    if (p <= 1e5) return iv[p];
    return qpow(p, mod - 2);
}
void pre_solve() {
    for (int i = 0;i < maxn;i++) { iv[i] = qpow(i, mod - 2); }
    a = (1 + sq5) * inv(2)%mod;
    b = ((1 - sq5 + mod) % mod) * inv(2)%mod;
    //cout << a << " " << b << " " << "\n";
    d = inv(sq5);
    for (int i = 0;i < maxn;i++) { pwa[i] = qpow(a, i); }
    for (int i = 0;i < maxn;i++) { pwb[i] = qpow(b, i); }
}
void solve(){
    ll _C=1,ans=0;
    ll n, c, k;
    cin >> n >> c >> k;
    ll t = pwb[k];
    t = qpow(t, c % (mod - 1));
    ll tt = qpow(t, (n + 1) % (mod - 1));
    ll d1 = qpow(a, c % (mod - 1)), d2 = inv(qpow(b, c % (mod - 1)));
    ll dn1 = qpow(d1, (n + 1) % (mod - 1)), dn2 = qpow(d2, (n + 1) % (mod - 1));
    for (int i = 0;i <= k;i++) {
        if (i) {
            t = t * d1 % mod * d2 % mod;
            tt = tt * dn1 % mod * dn2 % mod;
            _C = _C * (k - i + 1) % mod * inv(i) % mod;
        }
        if (t != 1) {
            ans = (ans + ((k - i) & 1 ? -1 : 1) * _C * (tt - 1 + mod) % mod * inv((t - 1 + mod) % mod) % mod) % mod;
        }
        else {
            ans = (ans + ((k - i) & 1 ? -1 : 1)*_C*(n%mod+1)%mod*t%mod ) % mod;
        }
        ans = (ans + mod) % mod;

    }
    cout << (ans*qpow(d,k)%mod) << "\n";
}
int main() {
    //  presolve();
    close_stdin;
    pre_solve();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}