lightoj1131

maksyuki 发表于 oj 分类，标签: 数值-矩阵快速幂取模

27 8月 2015

1131 - Just Two Functions

Find f_n % M and g_n % M. (% stands for the modulo operation.)Let f_n = a₁ * f_n-1 + b₁ * f_n-2 + c₁ * g_n-3g_n = a₂ * g_n-1 + b₂ * g_n-2 + c₂ * f_n-3

Input

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with a blank line. Next line contains three integers a₁ b₁ c₁ (0 ≤ a₁, b₁, c₁ < 25000). Next line contains three integers a₂ b₂ c₂ (0 ≤ a₂, b₂, c₂ < 25000). Next line contains three integers f₀ f₁ f₂ (0 ≤ f₀, f₁, f₂ < 25000). Next line contains three integers g₀ g₁ g₂ (0 ≤ g₀, g₁, g₂ < 25000). The next line contains an integer M (1 ≤ M < 25000).

Next line contains an integer q (1 ≤ q ≤ 100) denoting the number of queries. Next line contains q space separated integers denoting n. Each of these integers is non-negative and less than 2³¹.

Output

For each case, print the case number in a line. Then for each query, you have to print one line containing f_n % M and g_n % M.

Sample Input

Output for Sample Input

21 1 00 0 00 1 1

0 0 0

20000

1 2 3 4 5 6 7 8 9 10

1 1 1

2 2 2

20000

2 4 6 8 10

Case 1:1 01 02 03 0

5 0

8 0

13 0

21 0

34 0

55 0

Case 2:

2 2

10 10

34 34

114 114

386 386

题目类型：矩阵快速幂取模

算法分析：由于两个递推式之间不是独立的，所以需要将两个递推式用一个矩阵乘幂表示！！！之后直接上模板即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
//const int MOD = 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 6;

long long n = 6;//表示方阵的尺寸，必须恰好为运算的大小

long long MOD;
//申请变量
struct Mat
{
    long long mat[maxn][maxn];
};


//重载Mat乘法运算
Mat operator * (Mat a, Mat b)
{
    Mat c;
    memset (c.mat, 0, sizeof (c.mat));
    for (long long k = 0; k < n; k++)
    {
        for (long long i = 0; i < n; i++)
        {
            if (a.mat[i][k] == 0) continue;

            for (long long j = 0; j < n; j++)
            {
                if (b.mat[k][j] == 0) continue;

                c.mat[i][j] = (c.mat[i][j] + ((a.mat[i][k] % MOD) * (b.mat[k][j] % MOD) % MOD)) % MOD;
            }
        }
    }
return c;
}

//重载Mat乘幂运算
Mat operator ^ (Mat a, long long k)
{
    Mat c;
    for (long long i = 0; i < n; i++)
        for(long long j = 0; j < n; j++)
        c.mat[i][j] = (i == j);

    while (k)
    {
        if(k & 1)
            c = c * a;

        a = a * a;
        k >>= 1;
    }

return c;
}

int main()
{
//	ifstream cin ("aaa.txt");
//	freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    cin >> t;

    while(t--)
	{
        cout << "Case " << flag++ << ":" << endl;
        long long a1, b1, c1, a2, b2, c2, f0, f1, f2, g0, g1, g2;

        cin >> a1 >> b1 >> c1 >> a2 >> b2 >> c2 >> f0 >> f1 >> f2 >> g0 >> g1 >> g2 >> MOD;

		Mat aa, a0;
        aa.mat[0][0] = a1, aa.mat[0][1] = b1, aa.mat[0][2] = 0, aa.mat[0][3] = 0, aa.mat[0][4] = 0, aa.mat[0][5] = c1;
        aa.mat[1][0] = 1, aa.mat[1][1] = 0, aa.mat[1][2] = 0, aa.mat[1][3] = 0, aa.mat[1][4] = 0, aa.mat[1][5] = 0;
        aa.mat[2][0] = 0, aa.mat[2][1] = 1, aa.mat[2][2] = 0, aa.mat[2][3] = 0, aa.mat[2][4] = 0, aa.mat[2][5] = 0;
		aa.mat[3][0] = 0, aa.mat[3][1] = 0, aa.mat[3][2] = c2, aa.mat[3][3] = a2, aa.mat[3][4] = b2,  aa.mat[3][5] = 0;
		aa.mat[4][0] = 0, aa.mat[4][1] = 0, aa.mat[4][2] = 0, aa.mat[4][3] = 1, aa.mat[4][4] = 0, aa.mat[4][5] = 0;
		aa.mat[5][0] = 0, aa.mat[5][1] = 0, aa.mat[5][2] = 0, aa.mat[5][3] = 0, aa.mat[5][4] = 1, aa.mat[5][5] = 0;

		a0.mat[0][0] = f2, a0.mat[1][0] = f1, a0.mat[2][0] = f0, a0.mat[3][0] = g2, a0.mat[4][0] = g1, a0.mat[5][0] = g0;

        int q;
        cin >> q;

		long long tt;
		Mat res;
        for (int i = 1; i <= q; i++)
		{
			cin >> tt;
//			cout << tt << endl;

            if (tt == 0)
				cout << f0 % MOD << " " << g0 % MOD << endl;

			else if (tt == 1)
				cout << f1 % MOD << " " << g1 % MOD << endl;

			else if (tt == 2)
				cout << f2 % MOD << " " << g2 % MOD << endl;

			else
			{
				res = aa ^ (tt - 2);
				res = res * a0;
				cout << res.mat[0][0] % MOD << " " << res.mat[3][0] % MOD << endl;
			}
		}
	}
return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

//const int MOD = 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 6;

long long n = 6;//表示方阵的尺寸，必须恰好为运算的大小

long long MOD;

//申请变量

struct Mat

{

long long mat[maxn][maxn];

};

//重载Mat乘法运算

Mat operator * (Mat a, Mat b)

{

Mat c;

memset (c.mat, 0, sizeof (c.mat));

for (long long k = 0; k < n; k++)

{

for (long long i = 0; i < n; i++)

{

if (a.mat[i][k] == 0) continue;

for (long long j = 0; j < n; j++)

{

if (b.mat[k][j] == 0) continue;

c.mat[i][j] = (c.mat[i][j] + ((a.mat[i][k] % MOD) * (b.mat[k][j] % MOD) % MOD)) % MOD;

}

return c;

}

//重载Mat乘幂运算

Mat operator ^ (Mat a, long long k)

{

Mat c;

for (long long i = 0; i < n; i++)

for(long long j = 0; j < n; j++)

c.mat[i][j] = (i == j);

while (k)

{

if(k & 1)

c = c * a;

a = a * a;

k >>= 1;

}

return c;

}

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

cin >> t;

while(t--)

{

cout << "Case " << flag++ << ":" << endl;

long long a1, b1, c1, a2, b2, c2, f0, f1, f2, g0, g1, g2;

cin >> a1 >> b1 >> c1 >> a2 >> b2 >> c2 >> f0 >> f1 >> f2 >> g0 >> g1 >> g2 >> MOD;

Mat aa, a0;

aa.mat[0][0] = a1, aa.mat[0][1] = b1, aa.mat[0][2] = 0, aa.mat[0][3] = 0, aa.mat[0][4] = 0, aa.mat[0][5] = c1;

aa.mat[1][0] = 1, aa.mat[1][1] = 0, aa.mat[1][2] = 0, aa.mat[1][3] = 0, aa.mat[1][4] = 0, aa.mat[1][5] = 0;

aa.mat[2][0] = 0, aa.mat[2][1] = 1, aa.mat[2][2] = 0, aa.mat[2][3] = 0, aa.mat[2][4] = 0, aa.mat[2][5] = 0;

aa.mat[3][0] = 0, aa.mat[3][1] = 0, aa.mat[3][2] = c2, aa.mat[3][3] = a2, aa.mat[3][4] = b2, aa.mat[3][5] = 0;

aa.mat[4][0] = 0, aa.mat[4][1] = 0, aa.mat[4][2] = 0, aa.mat[4][3] = 1, aa.mat[4][4] = 0, aa.mat[4][5] = 0;

aa.mat[5][0] = 0, aa.mat[5][1] = 0, aa.mat[5][2] = 0, aa.mat[5][3] = 0, aa.mat[5][4] = 1, aa.mat[5][5] = 0;

a0.mat[0][0] = f2, a0.mat[1][0] = f1, a0.mat[2][0] = f0, a0.mat[3][0] = g2, a0.mat[4][0] = g1, a0.mat[5][0] = g0;

int q;

cin >> q;

long long tt;

Mat res;

for (int i = 1; i <= q; i++)

{

cin >> tt;

// cout << tt << endl;

if (tt == 0)

cout << f0 % MOD << " " << g0 % MOD << endl;

else if (tt == 1)

cout << f1 % MOD << " " << g1 % MOD << endl;

else if (tt == 2)

cout << f2 % MOD << " " << g2 % MOD << endl;

else

{

res = aa ^ (tt - 2);

res = res * a0;

cout << res.mat[0][0] % MOD << " " << res.mat[3][0] % MOD << endl;

}

return 0;

}

lightoj1129

lightoj1140

超客的水墨烟雨

lightoj1131

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论

2024年12月
一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31