题意：矩阵快速幂求斐波那契数列。
分析：
#include<cstdio> #include<cstring> #include<cctype> #include<cstdlib> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<deque> #include<queue> #include<stack> #include<list> #define fin freopen("in.txt", "r", stdin) #define fout freopen("out.txt", "w", stdout) #define pr(x) cout << #x << " : " << x << " " #define prln(x) cout << #x << " : " << x << endl typedef long long ll; typedef unsigned long long llu; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f; const double pi = acos(-1.0); const double EPS = 1e-6; const int dx[] = {0, 0, -1, 1}; const int dy[] = {-1, 1, 0, 0}; const ll MOD = 1e9; const int MAXN = 1000 + 10; const int MAXT = 10000 + 10; using namespace std; struct Node { ll c[2][2]; Node() { memset(c, 0, sizeof c); } }; Node multi(Node &a, Node &b) { Node ans; for(int i = 0; i < 2; ++i) for(int j = 0; j < 2; ++j) for(int k = 0; k < 2; ++k){ ans.c[i][j] += (a.c[i][k] * b.c[k][j]); ans.c[i][j] %= MOD; } return ans; } ll q_pow(ll cur) { Node a; a.c[0][0] = a.c[0][1] = a.c[1][0] = 1; Node ans; ans.c[0][0] = ans.c[1][1] = 1; while(cur) { if(cur & 1) { ans = multi(ans, a); } a = multi(a, a); cur /= 2; } return ans.c[0][0]; } int main() { int P; scanf("%d", &P); while(P--) { int K; ll Y; scanf("%d%lld", &K, &Y); printf("%d %lld\n", K, q_pow(Y - 1)); } return 0; }