hdu4686 Arc of Dream ——构造矩阵+快速幂

August 20, 2013

link: http://acm.hdu.edu.cn/showproblem.php?pid=4686

构造出来的矩阵是这样的：根据题目的ai * bi = ……，可以发现矩阵1 * 矩阵3 = 矩阵2。然后就是矩阵快速幂了。

1	ai	bi	ai*bi	Si
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0

1	ai+1	bi+1	ai+1*bi+1	Si+1
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0

1	AY	BY	AY*BY	AY*BY
0	AX	0	AX*BY	AX*BY
0	0	BX	AY*BX	AY*BX
0	0	0	AX*BX	AX*BX
0	0	0	0	1

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <functional>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cassert>
#include <ctime>
#include <iterator>
const int INF = 0x3f3f3f3f;
const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
using namespace std;
#define LL __int64
#define MOD 1000000007
typedef struct
{
    LL m[5][5];
}mat;
mat X, Y;
LL n, a0, ax, ay, b0, bx, by;
mat multi(mat a, mat b)
{
    mat c; int j, i, k;
    for (i = 0; i < 5; ++i)
    {
        for (j = 0; j < 5; ++j)
        {
            c.m[i][j] = 0;
            for (k = 0; k < 5; ++k)
            {
                c.m[i][j] += a.m[i][k] * b.m[k][j]%MOD;
            }
            c.m[i][j] %= MOD;
        }
    }
    return c;
}
mat power(LL k)
{
    mat ans = X, p = Y;
    while (k)
    {
        if(k&1) ans = multi(ans, p);
        k /= 2; p = multi(p, p);
    }
    return ans;
}
int main(void)
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin );
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    while (cin>>n>>a0>>ax>>ay>>b0>>bx>>by)
    {
        if(!n) {cout<<"0"<<endl; continue;}
        memset(X.m, 0, sizeof(X.m));
        memset(Y.m, 0, sizeof(Y.m));
        X.m[0][0] = 1, X.m[0][1] = a0%MOD, X.m[0][2] = b0%MOD,
        X.m[0][3] = a0*b0%MOD, X.m[0][4] = a0*b0%MOD;
        Y.m[0][0] = 1, Y.m[0][1] = ay%MOD, Y.m[0][2] = by%MOD,
        Y.m[0][3] = ay*by%MOD, Y.m[0][4] = ay*by%MOD, Y.m[1][1] = ax%MOD,
        Y.m[1][3] = ax*by%MOD, Y.m[1][4] = ax*by%MOD, Y.m[2][2] = bx%MOD,
        Y.m[2][3] = ay*bx%MOD, Y.m[2][4] = ay*bx%MOD, Y.m[3][3] = ax*bx%MOD,
        Y.m[3][4] = ax*bx%MOD, Y.m[4][4] = 1;
        mat ans = power(n-1);
        LL touch = ans.m[0][4];
        cout << touch <<endl;
    }
    return 0;
}

注意 n==0 的时候特判呐~

走吧，小胖！

Read more