A: 求近似值
时间限制: 1 s 内存限制: 128 MB
提交 我的状态
题目描述
求⌊(5–√+6–√)2n⌋⌊(5+6)2n⌋%9932017。
例如：n=1，(5–√+6–√)2(5+6)2=21.9544....，⌊(5–√+6–√)2⌋⌊(5+6)2⌋%9932017=21。
输入
第一行输入T，表示n的个数。（1<=T<=200000）
下面T行每行一个数，表示n。（0<=n<=10^18）
输出
按照题意输出答案。
样例输入
3
0
1
2
样例输出
1
21
481题解：就是一个数学题目，将f(n)分解为两个互相关联的函数An和B(n);
通过矩阵求出最终的A(n)和B(n),问题就迎刃而解了；
#include<iostream>
#include<string.h>
#include<algorithm>
#define inf 9932017
#define ll long long
using namespace std;
struct mat{
ll p[2][2];
mat(){
memset(p,0,sizeof(p));
}
};
mat mul(mat A,mat B){
mat C;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
C.p[i][j]+=A.p[i][k]*B.p[k][j]%inf;
return C;
}
mat pow(mat A,ll n){
mat B;
B.p[0][0]=11;
B.p[1][0]=2;
while(n){
if(n&1)
B=mul(A,B);
A=mul(A,A);
n>>=1;
}
return B;
}
int main()
{
int T;
ll n;
scanf("%d",&T);
mat A;
A.p[0][0]=11; A.p[0][1]=60;
A.p[1][0]=2; A.p[1][1]=11;
while(T--)
{
scanf("%lld",&n);
if(!n)
printf("1\n");
else
printf("%lld\n",(2*pow(A,n-1).p[0][0]-1)%inf);//2An-1
}
return 0;
}