本文主要是介绍矩阵快速幂取模--cf678d Iterated linear function，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
所有线性变换可由矩阵表示。
#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
struct matrix{
long long m[2][2];
};
long long a,b,n,x;
matrix multiple(matrix a,matrix b)
{
matrix ans;
ans.m[0][0] = 0,ans.m[0][1] = 0,ans.m[1][0] = 0,ans.m[1][1] = 0;
for (int i = 0; i < 2; i ++) {
for (int j = 0; j < 2; j ++) {
for (int k = 0; k < 2; k ++) {
ans.m[i][j] = (ans.m[i][j] % mod + a.m[i][k] %mod * b.m[k][j] % mod) % mod;
}
}
}
return ans;
}
matrix quick(long long n)//求n - 1次幂
{
matrix co;
co.m[0][0] = a + 1,co.m[0][1] = -a,co.m[1][0] = 1,co.m[1][1] = 0;
matrix res;
res.m[0][0] = 1,res.m[0][1] = 0,res.m[1][0] = 0,res.m[1][1] = 1;
n --;
while (n) {
if (n & 1) {
res = multiple(res,co);
}
co = multiple(co, co);
n >>= 1;
}
return res;
}
int main()
{
cin >> a >> b >> n >> x;
quick(n);
long long tmp = (a % mod * x % mod + b) % mod;
if (n == 1) {
cout << tmp << endl;
}
else if(n == 0) cout << x << endl;
else {
matrix res = quick(n);
tmp = tmp % mod * res.m[0][0] % mod ;
tmp = tmp % mod + res.m[0][1] % mod * x % mod + mod;
cout << (tmp % mod + mod ) % mod << endl;
}
return 0;
}
这篇关于矩阵快速幂取模--cf678d Iterated linear function的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
