<p>有人给了我这个答案,但我不知道怎么做?复杂性O(logn)</p>
<pre><code>#include <stdio.h>
#include <stdlib.h>
#define mod 1000000007
long long int power(long long int,long long int);
void mult(long long int[2][2],long long int[2][2]);
int main()
{
int test;
scanf("%d",&test);
while(test--)
{
int n;
int pp,p;
scanf("%d%d%d",&pp,&p,&n);
long long int A[2][2] = {{1,1},{1,0}};
n = n-1;
long long int B[2][2] = {{1,0},{0,1}};
while(n>0)
{
if(n%2==1)
mult(B,A);
n = n/2;
mult(A,A);
}
long long int result = ((power(pp+1,B[0][1])*power(p+1,B[0][0]))%mod - 1 + mod)%mod;
printf("%lld\n",result);
}
}
long long int power(long long int a,long long int b)
{
long long int result = 1;
while(b>0)
{
if(b%2==1)
result = (result*a)%mod;
a = (a*a)%mod;
b = b/2;
}
return result;
}
void mult(long long int A[2][2],long long int B[2][2])
{
long long int C[2][2];
C[0][0] = A[0][0]*B[0][0] + A[0][1]*B[1][0];
C[0][1] = A[0][0]*B[0][1] + A[0][1]*B[1][1];
C[1][0] = A[1][0]*B[0][0] + A[1][1]*B[1][0];
C[1][1] = A[1][0]*B[0][1] + A[1][1]*B[1][1];
A[0][0] = C[0][0]%(mod-1);
A[0][1] = C[0][1]%(mod-1);
A[1][0] = C[1][0]%(mod-1);
A[1][1] = C[1][1]%(mod-1);
}
</code></pre>