传送门:https://ac.nowcoder.com/acm/contest/885/B
题意:给出,由公式 求出
思路:没学过矩阵快速幂。题解说是矩阵快速幂,之后就学了一遍。(可以先去学一下矩阵快速幂)
构造。然后就可以套板子写了,不过要注意把二进制改成十进制(这里也让我对对快速幂取模有了更好的理解)
注释见代码了
#include<bits/stdc++.h>
using namespace std;
struct node
{
long long c[2][2];
};
long long x0, x1, a, b;
long long mod;
char s[1000010];
//矩阵快速幂模板
node solve(node x, node y)
{
node ans;
for(int i = 0; i < 2; i++)
{
for(int j = 0; j < 2; j++)
{
ans.c[i][j] = 0;
for(int k = 0; k < 2; k++)
{
ans.c[i][j] = (ans.c[i][j] + x.c[i][k] * y.c[k][j]) % mod;
}
}
}
return ans;
}
int main()
{
scanf("%lld %lld %lld %lld", &x0, &x1, &a, &b);
scanf("%s", s);
scanf("%lld", &mod);
node ans;//储存答案
ans.c[0][0] = ans.c[1][1] = 1;
ans.c[0][1] = ans.c[1][0] = 0;
node x;
x.c[0][0] = a;
x.c[0][1] = b;
x.c[1][0] = 1;
x.c[1][1] = 0;
int len = strlen(s) - 1;
node temp;
for(int i = len; i >= 0; i--)
{
int num = s[i] - '0';
//这里相当于对10取模了
//二进制是对2取模 对2取模后为t for(int i=0;i<t;i++) ans = solve(ans, x);
//即为 if(num&1) ans = solve(ans, x);
for(int i = 0; i < num; i++)
{
ans = solve(ans, x);
}
temp.c[0][0] = temp.c[1][1] = 1;
temp.c[0][1] = temp.c[1][0] = 0;
//二进制的话 只要翻一倍 十进制当然要翻十倍
for(int i = 1; i <= 10; i++)
{
temp = solve(x, temp);
}
x = temp;
}
//输出答案了
long long sum = (ans.c[1][0] * x1 % mod + ans.c[1][1] * x0 % mod) % mod;
printf("%lld
", sum );
}