链接：https://ac.nowcoder.com/acm/contest/885/B 来源：牛客网
时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 262144K，其他语言524288K 分数：2500 题目描述
You are given four positive integers x 0 , x 1 , a , b x_0, x_1, a, b x0,x1,a,b. And you know x i = a ⋅ x i − 1 + b ⋅ x i − 2 x_i = a \cdot x_{i-1} + b \cdot x_{i-2} xi=a⋅xi−1+b⋅xi−2 for all i ≥ 2 i \ge 2 i≥2. Given two positive integers n n n, and M O D MOD MOD, please calculate x n x_n xn modulo M O D MOD MOD. Does the problem look simple? Surprise! The value of n n n may have many many digits!
输入描述:
The input contains two lines. The first line contains four integers x 0 , x 1 , a , b x_0, x_1, a, b x0,x1,a,b ( 1 ≤ x 0 , x 1 , a , b ≤ 1 0 9 ) (1 \le x_0, x_1, a, b \le 10^9) (1≤x0,x1,a,b≤109). The second line contains two integers n n n, M O D MOD MOD, 1 ≤ n < 1 0 ( 1 0 6 ) , 1 0 9 < M O D ≤ 2 × 1 0 9 1 \le n < 10^{(10^6)}, 10^9 < MOD \le 2 \times 10^9 1≤n<10(106),109<MOD≤2×109, n has no leading zero).
输出描述:
Print one integer representing the answer.
示例1 输入
1 1 1 1 10 1000000001输出
89说明
The resulting sequence x is Fibonacci sequence. The 11 11 11-th item is 89 89 89.
示例2 输入
1315 521 20185 5452831 9999999999999999999999999999999999999 1000000007输出
914730061题意： 给定递推式 x i = a ⋅ x i − 1 + b ⋅ x i − 2 x_i = a \cdot x_{i-1} + b \cdot x_{i-2} xi=a⋅xi−1+b⋅xi−2和其前两项 x 0 x_0 x0, x 1 x_1 x1，求 x n x_n xn m o d mod mod M O D MOD MOD。 n n n, M O D MOD MOD, 1 ≤ n < 1 0 ( 1 0 6 ) , 1 0 9 < M O D ≤ 2 × 1 0 9 1 \le n < 10^{(10^6)}, 10^9 < MOD \le 2 \times 10^9 1≤n<10(106),109<MOD≤2×109
题解： 很显然我们要用矩阵乘法来做 由于 n n n非常大，那么我们可以按照每一位来计算，设 n [ i ] {n[i]} n[i]为 n n n种的倒数第 i i i个数字,那么这个位置对答案的贡献就是 n [ i ] ∗ ( s t 1 0 i − 1 ) n[i]*(st^{10^{i-1}}) n[i]∗(st10i−1)， s t st st为初始矩阵， s t 1 0 i − 1 st^{10^{i-1}} st10i−1可以用 ( s t 1 0 i − 2 ) 10 ({st^{10^{i-2}}})^{10} (st10i−2)10来计算。那么这样就可以在 O ( l e n ( n ) ) O(len(n)) O(len(n))的时间内算出整个 n n n对答案的贡献即可。
#include<bits/stdc++.h> #define ll long long using namespace std; struct Matrix{ ll a[2][2]; void normal(){ memset(a,0,sizeof(a)); a[0][0]=1;a[1][1]=1; } }gp,bg,et; char n[1000004]; ll l,MOD,x0,x1,a,b; Matrix mul(Matrix A,Matrix B){ Matrix C; memset(C.a,0,sizeof(C.a)); for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ for(int k=0;k<2;k++){ C.a[i][j]+=(A.a[i][k]*B.a[k][j])%MOD; C.a[i][j]%=MOD; } } } return C; } Matrix fp(Matrix x,int y){ if(y==0)return et; if(y&1)return mul(x,fp(x,y-1)); else{ Matrix temp=fp(x,y>>1); return mul(temp,temp); } } int main(){ et.normal(); scanf("%lld%lld%lld%lld",&x0,&x1,&a,&b); scanf("%s%lld",n+1,&MOD); l=strlen(n+1); memset(bg.a,0,sizeof(bg.a)); memset(gp.a,0,sizeof(gp.a)); bg.a[0][0]=x1;bg.a[0][1]=x0; gp.a[0][0]=a;gp.a[0][1]=1; gp.a[1][0]=b; Matrix etm; etm.normal(); for(int i=l;i>=1;i--){ etm=mul(etm,fp(gp,n[i]-'0')); gp=fp(gp,10); } bg=mul(bg,etm); printf("%lld\n",bg.a[0][1]); return 0; }