本文共 3252 字,大约阅读时间需要 10 分钟。
题目链接:
题目描述:
给你5个数 :n,x,y,a,b(1<=n,x,y,z,b<=1e12)
f(1)=x,f(2)=y,f(i)=f(i-1)*f(i-2)*a^b(i>3)
让你求f(n)%1e9+7的值
题解:
f(1)=x;
f(2)=y; f(3)=x*y*a^b; f(4)=x*y*a^b*y*a^b=x*y^2*a^2b f(5)=x*y^2*a^2b*x*y*a^b*a^b=x^2*y^3*a^4b f(6)=x^2*y^3*a^4b*x*y^2*a^2b=x^3*y^5*a^6b 设c为常数 c x y 1 0 1 0 2 0 0 1 3 1 1 1 4 2 1 2 5 4 2 3 6 6 3 5 c: i<3:fb2(1)=fb2(2)=0; i>=3:fb2(i)=fb2(i-1)+fb2(i-1)+1; //注意不能化成fb2(i)=fb2(i-1)*fb2(i-2)*a^b; //因为这样不能用常量矩阵来维护,因为矩阵乘法的每一项的结果是相加的。 ans1=a^(b*fb2(i)),相当于只维护幂次和 1 1 1 fb2(i-1) fb2(i) 1 0 0 * fb2(i-2) = fb2(i-1) 0 0 1 1 1 设t为3*3的矩阵{ {1,1,1},{1,0,0},{0,0,1}}; 设ai为3*1的矩阵{fb2(i),fb2(i-1),1} 则a1={fb2(2),fb2(1),1} ai=a(i-1)*t a2=a1*t a3=a2*t=a1*t^2 =>ai=a1*t^(i-1) => fb2(2) fb2(i) t^(i-1) * fb2(1) = fb2(i-1) 1 1 如果要求fb2(n) 利用矩阵快速幂求出t^(n-1) fb2(n)=t^(n-1)的第一行*a1的第一列(即矩阵{0,0,1}) 则c对答案的贡献为 ans1=a^(b*fb2(n))(可以用快速幂求)x:
i<3:fb1(1)=1, fb1(2)=0; i>=3:fb1(i)=fb1(i-1)+fb1(i-2); 1 1 fb1(i-1) fb1(i) 1 0 * fb1(i-2) = fb1(i-1) 设t为2*2的矩阵{ {1,1},{1,0}} 设ai为2*1的矩阵{fb1(i),fb1(i-1)} 则a1为2*1的矩阵{fb1(2),fb1(1)} ai=a(i-1)*t; a2=a1*t a3=a2*t=a1*t*t=a1*t^2 a4=a3*t=a1*t*t*t=a*t^3; 根据递推式可得 ai=a1*t^(i-1); 即 t^(i-1) fb1(2) fb1(i) * fb1(1) = fb1(i-1). 故fb1(n)=t^(n-1)的第一行*a1(即矩阵{0,1}) 因此对答案的贡献是 ans2=x^fb1(n); y: i<3:fb1(1)=0,fb1(2)=1; i>=3:fb1(i)=fb1(i-1)+fb1(i-2); 推导过程和上面类似,只不过初始值变了 可以自己再推一遍。 最后答案就是ans1*ans2%mod*ans3%mod trick: 1.因为x和y的递推都是斐波那契数列,只不过初始值变了,而且x比y多了一位,所以我们可以放在一起考虑。 2.a^b对上面的指数取模时不能直接取,需要用到费马小定理 定理内容:如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p) 3.根据上面的定理所以我们需要特判a是p的倍数的情况以及x,y是p的倍数的情况。
代码实现:
#pragma GCC optimize(2)#include#include #include #include #include #include #include #include
转载地址:http://nufmz.baihongyu.com/