图灵杯-第四届“图灵杯”NEUQ-ACM 程序设计竞赛-F-一道简单的递推题

92 阅读 0 评论 61 点赞

我是靠谱客的博主轻松故事，这篇文章主要介绍图灵杯-第四届“图灵杯”NEUQ-ACM 程序设计竞赛-F-一道简单的递推题，现在分享给大家，希望可以做个参考。

ACM模版

描述

题解

典型的矩阵快速幂问题，官方题解说需要用到滚动优化，是为了减少拷贝的次数……这里可以使用引用来减少拷贝，并且注意 long long，最开始输错了 0，不按套路出牌，竟然不是九个零，是十个！！！这里提供两个代码，都是矩阵快速幂，模版不同而已~~~

做这个题也让我发现了自己的一个知识漏洞，对引用认识不到位，同时也发现了自己模版中的缺陷，今天好好改了改，希望可以进一步完善她！

代码

One：

复制代码

//AC 代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define mod(x) ((x) % MOD)
using namespace std;
typedef long long ll;
/*
*
矩阵快速幂 n*n矩阵的x次幂
*/
const int MAXN = 111;
const int MOD = 1e9 + 7;
int n;
struct mat
{
int m[MAXN][MAXN];
//
矩阵乘法
mat operator * (mat &b) const
{
mat ret;
memset(ret.m, 0, sizeof(ret.m));
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
if (m[i][k])
{
for (int j = 1; j <= n; j++)
{
ret.m[i][j] = mod(ret.m[i][j] + (ll)m[i][k] * b.m[k][j]);
}
}
}
}
return ret;
}
void init_unit()
{
for (int i = 1; i <= n; i++)
{
m[i][i] = 1;
}
}
mat operator ^ (ll p) const
{
mat ret;
ret.init_unit();
mat a;
memcpy(a.m, m, sizeof(m));
while (p)
{
if (p & 1)
{
ret = ret * a;
}
p >>= 1;
a = a * a;
}
return ret;
}
} tmp; //
单元矩阵
ll k, F[MAXN];
int main()
{
scanf("%d%lld", &n, &k);
for (int i = 1; i <= n; i++)
{
scanf("%lld", F + i);
}
for (int i = 1; i < n; i++)
{
tmp.m[i][i + 1] = 1;
}
for (int j = 1; j <= n; j++)
{
scanf("%d", &tmp.m[n][n - j + 1]);
}
tmp = tmp ^ (k - n);
long long ans = 0;
for (int j = 1; j <= n; j++)
{
ans = mod(ans + tmp.m[n][j] * F[j]);
}
printf("%lldn", ans);
return 0;
}

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
//AC 代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define mod(x) ((x) % MOD)
using namespace std;
typedef long long ll;
/*
*
矩阵快速幂 n*n矩阵的x次幂
*/
const int MAXN = 111;
const int MOD = 1e9 + 7;
int n;
struct mat
{
int m[MAXN][MAXN];
//
矩阵乘法
mat operator * (mat &b) const
{
mat ret;
memset(ret.m, 0, sizeof(ret.m));
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
if (m[i][k])
{
for (int j = 1; j <= n; j++)
{
ret.m[i][j] = mod(ret.m[i][j] + (ll)m[i][k] * b.m[k][j]);
}
}
}
}
return ret;
}
void init_unit()
{
for (int i = 1; i <= n; i++)
{
m[i][i] = 1;
}
}
mat operator ^ (ll p) const
{
mat ret;
ret.init_unit();
mat a;
memcpy(a.m, m, sizeof(m));
while (p)
{
if (p & 1)
{
ret = ret * a;
}
p >>= 1;
a = a * a;
}
return ret;
}
} tmp; //
单元矩阵
ll k, F[MAXN];
int main()
{
scanf("%d%lld", &n, &k);
for (int i = 1; i <= n; i++)
{
scanf("%lld", F + i);
}
for (int i = 1; i < n; i++)
{
tmp.m[i][i + 1] = 1;
}
for (int j = 1; j <= n; j++)
{
scanf("%d", &tmp.m[n][n - j + 1]);
}
tmp = tmp ^ (k - n);
long long ans = 0;
for (int j = 1; j <= n; j++)
{
ans = mod(ans + tmp.m[n][j] * F[j]);
}
printf("%lldn", ans);
return 0;
}

Two：

复制代码

//
AC 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#define mod(x) ((x) % MOD)
using namespace std;
typedef long long ll;
/*
*
矩阵快速幂 n * n矩阵的x次幂
*/
const int MAXN = 111;
const int MOD = 1e9 + 7;
int n;
struct mat
{
int m[MAXN][MAXN];
} unit, a; //
单元矩阵
//
矩阵乘法
mat operator * (mat a, mat &b)
{
mat ret;
memset(ret.m, 0, sizeof(ret.m));
for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
if (a.m[i][k])
{
for (int j = 0; j < n; j++)
{
ret.m[i][j] = mod(ret.m[i][j] + (ll)a.m[i][k] * b.m[k][j]);
}
}
}
}
return ret;
}
void init_unit()
{
for (int i = 0; i < MAXN; i++)
{
unit.m[i][i] = 1;
}
return ;
}
mat pow_mat(mat &a, ll n)
{
mat ret = unit;
while (n)
{
if (n & 1)
{
ret = ret * a;
}
n >>= 1;
a = a * a;
}
return ret;
}
ll k, F[MAXN];
int main()
{
init_unit();
scanf("%d%lld", &n, &k);
for (int i = 0; i < n; i++)
{
scanf("%lld", F + i);
}
for (int i = 0; i < n - 1; i++)
{
a.m[i][i + 1] = 1;
}
for (int j = 0; j < n; j++)
{
scanf("%d", &a.m[n - 1][n - j - 1]);
}
if (k <= n)
{
printf("%lldn", mod(F[k - 1]));
return 0;
}
a = pow_mat(a, k - n);
//
a矩阵的x次幂
long long ans = 0;
for (int j = 0; j < n; j++)
{
ans = mod(ans + a.m[n - 1][j] * F[j]);
}
printf("%lldn", ans);
return 0;
}

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
//
AC 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#define mod(x) ((x) % MOD)
using namespace std;
typedef long long ll;
/*
*
矩阵快速幂 n * n矩阵的x次幂
*/
const int MAXN = 111;
const int MOD = 1e9 + 7;
int n;
struct mat
{
int m[MAXN][MAXN];
} unit, a; //
单元矩阵
//
矩阵乘法
mat operator * (mat a, mat &b)
{
mat ret;
memset(ret.m, 0, sizeof(ret.m));
for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
if (a.m[i][k])
{
for (int j = 0; j < n; j++)
{
ret.m[i][j] = mod(ret.m[i][j] + (ll)a.m[i][k] * b.m[k][j]);
}
}
}
}
return ret;
}
void init_unit()
{
for (int i = 0; i < MAXN; i++)
{
unit.m[i][i] = 1;
}
return ;
}
mat pow_mat(mat &a, ll n)
{
mat ret = unit;
while (n)
{
if (n & 1)
{
ret = ret * a;
}
n >>= 1;
a = a * a;
}
return ret;
}
ll k, F[MAXN];
int main()
{
init_unit();
scanf("%d%lld", &n, &k);
for (int i = 0; i < n; i++)
{
scanf("%lld", F + i);
}
for (int i = 0; i < n - 1; i++)
{
a.m[i][i + 1] = 1;
}
for (int j = 0; j < n; j++)
{
scanf("%d", &a.m[n - 1][n - j - 1]);
}
if (k <= n)
{
printf("%lldn", mod(F[k - 1]));
return 0;
}
a = pow_mat(a, k - n);
//
a矩阵的x次幂
long long ans = 0;
for (int j = 0; j < n; j++)
{
ans = mod(ans + a.m[n - 1][j] * F[j]);
}
printf("%lldn", ans);
return 0;
}