generator 1

Posted on | In , , ,

题目链接

题意

计算一个递推式的第n项，n是一个大数。

思路

很容易想到矩阵快速幂，但是为了避免一个把这个大数分解成二进制的过程，我们使用十进制的快速幂。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod;
struct matrix
{
    ll a[2][2];
    void init()
    {
        a[0][0] = 0;
        a[1][0] = 0;
        a[1][1] = 0;
        a[0][1] = 0;
    }
    inline ll* operator [] (int i)
    {
        return a[i];
    }
};
 
inline matrix mult(matrix a, matrix b)
{
    matrix ans;
    ans.init();
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                ans[i][j] = (ans[i][j] + a[i][k] * b[k][j] % mod) % mod;
    return ans;
}
char s[1000005];
 
inline matrix Pow_q(matrix a, ll b)
{
    matrix ans;
    ans.init();
    ans[0][0] = 1;
    ans[1][1] = 1;
    while (b)
    {
        if (b & 1)
            ans = mult(ans, a);
        a = mult(a, a);
        b >>= 1;
    }
    return ans;
}
/* 
matrix Pow(matrix a)
{
    int len = strlen(s);
    matrix ans;
    ans.init();
    ans[0][0] = 1;
    ans[1][1] = 1;
    for (int i = len - 1; i >= 0; i--)
    {
		if (s[i] != '0')
		{
        	//dbg(s[i] - '0');
        	ans = mult(ans, Pow_q(a, s[i] - '0'));
		}
        a = Pow_q(a, 10);
    }
    //dbg(ans[0][0], ans[0][1], ans[1][0], ans[1][1]);
    return ans;
}
 */
matrix base[15];
int main()
{
    ll x0, x1, a, b;
    scanf("%lld%lld%lld%lld", &x0, &x1, &a, &b);
    ll n;
    scanf("%s%lld", s, &mod);
    int len = strlen(s);
    if (len == 1 && s[0] == '0')
    {
        printf("%lld\n", x0);
        return 0;
    }
    if (len == 1 && s[0] == '1')
    {
        printf("%lld\n", x1);
        return 0;
    }
    s[len - 1]--;
    int i;
    for (i = len - 1; i >= 0; i--)
        if (s[i] < '0')
            s[i] = '9', s[i - 1]--;
        else
            break;
    if (s[0] == '0')
    {
        for (int i = 0; i < len - 1; i++)
            s[i] = s[i + 1];
        s[len - 1] = 0;
    }
	//puts(s);
	matrix lcy;
    lcy[0][0] = a;
    lcy[0][1] = b;
    lcy[1][0] = 1ll;
    lcy[1][1] = 0;
	len = strlen(s);
    matrix ans;
    ans.init();
    ans[0][0] = 1;
    ans[1][1] = 1;
	base[0].init();
	base[0][0][0] = 1;
	base[0][1][1] = 1;
	for (int i = 1; i <= 9; i++)
		base[i] = mult(base[i - 1], lcy);
    for (int i = 0; i < len; i++)
    {
		ans = Pow_q(ans, 10);
		if (s[i] != '0')
		{
        	//dbg(s[i] - '0');
        	ans = mult(ans, base[s[i] - '0']);
		}
    }
    ll ret = x1 * ans[0][0] % mod + x0 * ans[0][1] % mod;
    ret %= mod;
    printf("%lld\n", ret);
    return 0;
}

0%