1131 - Just Two Functions

  

PDF (English)

Statistics

Forum

Time Limit: 2 second(s)

Memory Limit: 32 MB

Let

fn = a1 * fn-1 + b1 * fn-2 + c1 * gn-3

gn = a2 * gn-1 + b2 * gn-2 + c2 * fn-3

Find fn % M and gn % M. (% stands for the modulo operation.)

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 a1 b1 c1 (0 ≤ a1, b1, c1 < 25000). Next line contains three integers a2 b2 c2 (0 ≤ a2, b2, c2 < 25000). Next line contains three integers f0 f1 f2(0 ≤ f0, f1, f2 < 25000). Next line contains three integers g0 g1 g2 (0 ≤ g0, g1, g2 < 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 231.

Output

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

Sample Input

Output for Sample Input

2

1 1 0

0 0 0

0 1 1

0 0 0

20000

10

1 2 3 4 5 6 7 8 9 10

1 1 1

1 1 1

2 2 2

2 2 2

20000

5

2 4 6 8 10

Case 1:

1 0

1 0

2 0

3 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

---

PROBLEM SETTER: JANE ALAM JAN

思路：矩阵快速幂；

比较简单，矩阵也比较好推。

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 using namespace std;
10 typedef long long LL;
11 char str[100];
12 char ask[100];
13 LL ans[200];
14 int M;
15 typedef struct pp
16 {
17 LL m[10][10];
18 pp()
19 {
20 memset(m,0,sizeof(m));
21 }
22 } maxtr;
23 LL xishu[10];
24 LL xisu[10];
25 LL f[10];
26 LL g[10];
27 maxtr E()
28 {
29 maxtr ac;
30 int i,j;
31 for(i=0; i<10; i++) 32 { 33 for(j=0; j<10; j++) 34 { 35 if(i==j) 36 { 37 ac.m[i][j]=1; 38 } 39 else ac.m[i][j]=0; 40 } 41 } 42 return ac; 43 } 44 void Init(maxtr *p) 45 { 46 int i,j,k; 47 memset(p->m,0,sizeof(p->m));
48 p->m[0][0]=xishu[0];
49 p->m[0][1]=xishu[1];
50 p->m[0][5]=xishu[2];
51 p->m[1][0]=1;
52 p->m[2][1]=1;
53 p->m[3][2]=xisu[2];
54 p->m[3][3]=xisu[0];
55 p->m[3][4]=xisu[1];
56 p->m[4][3]=1;
57 p->m[5][4]=1;
58 }
59 maxtr quick(maxtr C,LL m)
60 {
61 maxtr ak=E();
62 int s;
63 int i,j;
64 while(m)
65 {
66 if(m&1)
67 {
68 maxtr vv;
69 memset(vv.m,0,sizeof(vv.m));
70 for(i=0; i<=5; i++)
71 {
72 for(j=0; j<=5; j++)
73 {
74 for(s=0; s<=5; s++)
75 {
76 vv.m[i][j]=(vv.m[i][j]+C.m[i][s]*ak.m[s][j]%M)%M;
77 }
78 }
79 }
80 ak=vv;
81 }
82 maxtr vv;memset(vv.m,0,sizeof(vv.m));
83 for(i=0; i<=5; i++)
84 {
85 for(j=0; j<=5; j++)
86 {
87 for(s=0; s<=5; s++)
88 {
89 vv.m[i][j]=(vv.m[i][j]+C.m[i][s]*C.m[s][j]%M)%M;
90 }
91 }
92 }
93 C=vv;
94 m/=2;
95 }
96 return ak;
97 }
98 int main(void)
99 {
100 LL i,j,k;
101 scanf("%lld",&k);
102 LL s;
103 for(s=1; s<=k; s++)
104 {
105 for(i=0; i<3; i++)
106 {
107 scanf("%lld",&xishu[i]);
108 }
109 for(i=0; i<3; i++)
110 {
111 scanf("%lld",&xisu[i]);
112 }
113 for(i=0; i<3; i++)
114 {
115 scanf("%lld",&f[i]);
116 }
117 for(i=0; i<3; i++)
118 {
119 scanf("%lld",&g[i]);
120 }
121 scanf("%d",&M);
122 int cnt=0;
123 scanf("%d",&cnt);
124 for(i=0; i<cnt; i++)
125 {
126 scanf("%lld",&ans[i]);
127 }
128 printf("Case %d:\n",s);
129 for(i=0; i<cnt; i++)
130 {
131 if(ans[i]<2)
132 {
133 printf("%lld %lld\n",f[ans[i]]%M,g[ans[i]]%M);
134 }
135 else
136 {
137 maxtr ac;
138 memset(ac.m,0,sizeof(ac.m));
139 Init(&ac);
140 maxtr ak=quick(ac,ans[i]-2);
141 LL ak1=ak.m[0][0]*f[2]%M+ak.m[0][1]*f[1]%M+ak.m[0][5]*g[0]%M+ak.m[0][2]*f[0]%M+ak.m[0][3]*g[2]%M+ak.m[0][4]*g[1]%M;
142 ak1%=M;
143 LL ak2=ak.m[3][2]*f[0]%M+ak.m[3][3]*g[2]%M+ak.m[3][4]*g[1]%M+ak.m[3][0]*f[2]%M+ak.m[3][1]*f[1]%M+ak.m[3][5]*g[0]%M;
144 ak2%=M;
145 printf("%lld %lld\n",ak1,ak2);
146 }
147 }
148 }return 0;
149 }