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.
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
Author Zejun Wu (watashi)
Source 2013 Multi-University Training Contest 9
Recommend zhuyuanchen520 | We have carefully selected several similar problems for you: 5185 5184 5181 5180 5177
Statistic | Submit | Discuss | Note Home | Top
很明显也是要用矩阵来求的 an*bn = (an-1 * Ax + Ay) * (bn-1 * Bx + By) 展开以后得到4项 (an-1 * bn-1) * Ax * Bx an-1 * Ax * By bn-1 * Bx * Ay Ay * By 利用这些就可以构造出递推求an * bn的矩阵了 ,但是这里要求和,所以再加一列就行了
得到一个5 * 5的矩阵 AX*BX 0 0 0 AX*BX AX*BY AX 0 0 AX*BY BX*AY 0 BX 0 BX*AY AY*BY AY BY 1 AY*BY 00 0 0 1
注意n是0的话,输出0
/*************************************************************************> File Name: hdu4686.cpp> Author: ALex> Mail: zchao1995@gmail.com> Created Time: 2015年03月12日 星期四 16时21分07秒 ************************************************************************/;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> PLL;const int mod = 1000000007;class MARTIX{public:LL mat[10][10];MARTIX();MARTIX operator * (const MARTIX &b)const;MARTIX& operator = (const MARTIX &b);};MARTIX::MARTIX(){memset (mat, 0, sizeof(mat));}MARTIX MARTIX :: operator * (const MARTIX &b)const{MARTIX ret;for (int i = 0; i < 5; ++i){for (int j = 0; j < 5; ++j){for (int k = 0; k < 5; ++k){ret.mat[i][j] += this -> mat[i][k] * b.mat[k][j];ret.mat[i][j] %= mod;}}}return ret;}MARTIX& MARTIX :: operator = (const MARTIX &b){for (int i = 0; i < 5; ++i){for (int j = 0; j < 5; ++j){this -> mat[i][j] = b.mat[i][j];}}return *this;}MARTIX fastpow(MARTIX ret, LL n){MARTIX ans;for (int i = 0; i < 5; ++i){ans.mat[i][i] = 1;}while (n){if (n & 1){ans = ans * ret;}ret = ret * ret;n >>= 1;}return ans;}void Debug(MARTIX A){for (int i = 0; i < 5; ++i){for (int j = 0; j < 5; ++j){printf(“%lld “, A.mat[i][j]);}printf(“\n”);}}int main (){LL A0, AX, AY, B0, BX, BY, n;while (~scanf(“%lld”, &n)){scanf(“%lld%lld%lld”, &A0, &AX, &AY);scanf(“%lld%lld%lld”, &B0, &BX, &BY);MARTIX A;if (!n){printf(“0\n”);continue;}A.mat[0][0] = A.mat[0][4] = AX * BX % mod;A.mat[1][0] = A.mat[1][4] = AX * BY % mod;A.mat[1][1] = AX;A.mat[2][0] = A.mat[2][4] = BX * AY % mod;A.mat[2][2] = BX;A.mat[3][0] = A.mat[3][4] = AY * BY % mod;A.mat[3][3] = 1;A.mat[3][1] = AY;A.mat[3][2] = BY;A.mat[4][4] = 1;MARTIX ans = fastpow(A, n – 1);//Debug(ans);MARTIX F;F.mat[0][0] = F.mat[0][4] = A0 * B0 % mod;F.mat[0][1] = A0 % mod;F.mat[0][2] = B0 % mod;F.mat[0][3] = 1;F = F * ans;printf(“%lld\n”, F.mat[0][4]);}return 0;}
，击败不等于击倒，跌倒了，爬起来，想一想，为什么跌倒了，
