6275.小L的数列

input:seq.in output:seq.out

Time Limits: 1500 ms Memory Limits: 524288 KB

Description

Input

一行两个整数n和k。

之后1行k个正整数b1…bk。

之后1行k个正整数f1…fk。

Output

输出一个整数表示fn

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
【样例输入1】

5 4

1 2 3 4

4 3 2 1

【样例输入2】

100000 4

1 2 3 4

12 23 34 45

Sample Output

1
2
3
4
5
6
7
【样例输出1】

27648

样例输出2】

33508797

Data Constraint

对于30%的数据,n≤10000.

对于另外20%的数据,bi=1,n≤1000000.

对于另外20%的数据,f[1]…f[k-1]=1.

对于另外20%的数据,k≤30.

对于100%的数据,1≤k≤200,1≤n≤40000000,1≤bi,fi≤998244352.

Hint

样例解释:122333444*4=27648

Code

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
#include <bits/stdc++.h>
#define mod 998244353
#define ll long long
ll n, k;
ll b[205], f[1000005];
ll A[205][205];
ll B[205][205];
ll C[205][205];

void cf () {
memset (C, 0, sizeof (C));
for (ll i = 1;i <= k;i++) {
for (ll j = 1;j <= k;j++) {
for (ll l = 1;l <= k;l++) {
C[i][j] += A[l][j] * B[i][l];
C[i][j] %= (mod - 1);
}
}
}
for (ll i = 1;i <= k;i++) {
for (ll j = 1;j <= k;j++) {
B[i][j] = C[i][j];
}
}
return;
}
void pf () {
memset (C, 0, sizeof (C));
for (ll i = 1;i <= k;i++) {
for (ll j = 1;j <= k;j++) {
for (ll l = 1;l <= k;l++) {
C[i][j] += A[l][j] * A[i][l];
C[i][j] %= (mod - 1);
}
}
}
for (ll i = 1;i <= k;i++) {
for (ll j = 1;j <= k;j++) {
A[i][j] = C[i][j];
}
}
return;
}
void ksm (ll y) {
while (y) {
if (y % 2 != 0) {
cf ();
}
pf ();
y >>= 1;
}
return;
}
ll ksm2 (ll x, ll y) {
ll sum = 1;
while (y) {
if (y % 2 > 0) {
sum *= x;
sum %= mod;
}
x *= x;
x %= mod;
y >>= 1;
}
return sum;
}
int main () {
freopen ("seq.in", "r", stdin);
freopen ("seq.out", "w", stdout);
scanf ("%lld %lld", &n, &k);
for (ll i = 1;i <= k;i++) {
scanf ("%lld", &b[i]);
}
for (ll i = 1;i <= k;i++) {
scanf ("%lld", &f[i]);
}
if (n * k <= 100000000) {
for (ll i = k + 1;i <= n;i++) {
f[i] = 1;
for (ll j = 1;j <= k;j++) {
f[i] *= ksm2 (f[i - j], b[j]);
f[i] %= mod;
}
}
printf ("%lld", f[n]);
return 0;
}
memset (A, 0, sizeof (A));
for (ll i = 1;i <= k;i++) {
A[1][i] = b[i];
B[1][i] = b[i];
}
for (ll i = 2;i <= k;i++) {
A[i][i - 1] = 1;
B[i][i - 1] = 1;
}
ksm (n - k - 1);
ll ans = 1;
for (ll i = 1;i <= k;i++) {
ans *= ksm2 (f[k - i + 1], B[1][i]);
ans %= mod;
}
printf ("%lld", ans);
return 0;
}
暗影 微信

微信