首页 > 代码库 > HDU4686 Arc of Dream 矩阵快速幂
HDU4686 Arc of Dream 矩阵快速幂
Arc of Dream
Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 4246 Accepted Submission(s): 1332
Problem Description
An Arc of Dream is a curve defined by following function:
where
a0 = A0
ai = ai-1*AX+AY
b0 = B0
bi = bi-1*BX+BY
What is the value of AoD(N) modulo 1,000,000,007?
Input
There are multiple test cases. Process to the End of File.
Each test case contains 7 nonnegative integers as follows:
N
A0 AX AY
B0 BX BY
N is no more than 1018, and all the other integers are no more than 2×109.
Each test case contains 7 nonnegative integers as follows:
N
A0 AX AY
B0 BX BY
N is no more than 1018, and all the other integers are no more than 2×109.
Output
For each test case, output AoD(N) modulo 1,000,000,007.
Sample Input
1
1 2 3
4 5 6
2
1 2 3
4 5 6
3
1 2 3
4 5 6
Sample Output
4
134
1902
题意：已知：
a0 = A0 b0 = B0
ai = ai-1*AX+AY
bi = bi-1*BX+BY
bi = bi-1*BX+BY
Sn = a0b0+a1*b1+...+a(n-1)*b(n-1);
求 Sn
题解：矩阵快速幂求n项和
a[i]*b[i] = (a[i-1]*Ax+Ay)(b[i-1]*Bx+By)
= Ax*Bx*a[i-1]*b[i-1]+Ay*Bx*b[i-1]+Ax*By*a[i-1]+Ay*By
s
[s[n-1],a[n-2]*b[n-2], b[n-2], a[n-2], 1]
A
[1 ,0 ,0 ,0 ,0]
[Ax*Bx ,Ax*Bx ,0 ,0 ,0]
[Ay*Bx ,Ay*Bx ,Bx ,0 ,0]
[Ax*By ,Ax*By ,0 ,Ax ,0]
[Ay*By ,Ay*By ,By ,Ay ,1]//n-1
s
[s[n], a[n-1]*b[n-1], b[n-1], a[n-1], 1]
#include<bits/stdc++.h>#define N 5#define mes(x) memset(x, 0, sizeof(x));#define ll long longconst ll mod = 1e9+7;const int MAX = 0x7ffffff;using namespace std;struct mat { ll a[N][N]; mat() { memset(a, 0, sizeof(a)); } mat operator * (mat b) { mat c; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j]) % mod; return c; }};mat f(mat b, ll m) { mat c; for (int i = 0; i < N; i++) c.a[i][i] = 1; while (m) { if (m & 1) c = c * b; b = b * b; m >>= 1; } return c; }int main(){ ll n, A0,Ax, Ay, Bx,By,B0; mat A, s; while(~scanf("%lld", &n)){ scanf("%lld%lld%lld%lld%lld%lld", &A0, &Ax, &Ay, &B0, &Bx, &By); if(n == 0){ printf("0\n"); continue; } mes(A.a); mes(s.a); s.a[0][0] = s.a[0][1] = (A0%mod*B0%mod)%mod; s.a[0][2] = B0%mod; s.a[0][3] = A0%mod; s.a[0][4] = 1; A.a[0][0] = 1; A.a[1][1] = A.a[1][0] = (Ax%mod*Bx%mod)%mod;A.a[2][2] = Bx%mod; A.a[2][1] = A.a[2][0] = (Ay%mod*Bx%mod)%mod;A.a[3][3] = Ax%mod; A.a[3][1] = A.a[3][0] = (Ax%mod*By%mod)%mod; A.a[4][0] = A.a[4][1] = (Ay%mod*By%mod)%mod; A.a[4][2] = By; A.a[4][3] = Ay; A.a[4][4] = 1; A = f(A,n-1); s = s*A; printf("%lld\n", (mod+s.a[0][0])%mod); } }
HDU4686 Arc of Dream 矩阵快速幂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。