数论基础二

数论基础二————关于矩阵快速幂
其实今天还是懒得写…但是flag已经立下来了是吧…写吧
祖传配图:
今天看UMR!虽说这几天看小埋没怎么学习,但是小埋超喜欢的啊

关于矩阵快速幂:

得先介绍下矩阵乘法:

就是矩阵乘法必须在一个行数等于另一个的列数时才能乘,打个比方:图中的A是一个23的矩阵,而B是个32的矩阵
那么最后乘的结果就是一个22的矩阵,倒不是说就是小的乘小的
这是因为是A
B而不是BA,因为AB与BA是不相同的,这里的BA是一个3*3的矩阵了
并且矩阵相乘的结果就是:
比如C[0][0],就等于A矩阵的第一行与B矩阵的第一列相对乘在相加,……

那我们在看下矩阵乘法的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct matrix {
int n, m;
int a[100][100];
};
// A.m == B.n
matrix matrix_mul(matrix A, matrix B) {
matrix C;
C.n = A.n;
C.m = B.m;
for (int i = 0; i < A.n; ++i) {
for (int j = 0; j < B.m; ++j) {
C.a[i][j] = 0;
for (int k = 0; k < A.m; ++k) {
C.a[i][j] += A.a[i][k] * B.a[k][j];
}
}
}
return C;
}

对了,还得说下状态转移矩阵
关于这个,就4在实际问题中。。。。说不清,看官方介绍吧:(不知道计蒜客这个算不算官方啊

它上面本来有个图乱七八糟看不懂,大概就是让你找一个矩阵,来满足上图的等式,至于怎么找?

我咋知道…慢慢找呗,那么好找,矩阵快速幂和1+1有啥区别?

计蒜客在题为“矩阵二分快速幂优化DP”的标题下,有这样一段话:

老实说不懂啥了,反正代码用呗…哎,感觉自己好随意啊,艹,气人

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
int n; // 所有矩阵都是 n * n 的矩阵
struct matrix {
int a[100][100];
};
matrix matrix_mul(matrix A, matrix B, int mod) {
// 2 个矩阵相乘
matrix C;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
C.a[i][j] = 0;
for (int k = 0; k < n; ++k) {
C.a[i][j] += A.a[i][k] * B.a[k][j] % mod;
C.a[i][j] %= mod;
}
}
}
return C;
}
matrix unit() {
// 返回一个单位矩阵
matrix res;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) {
res.a[i][j] = 1;
} else {
res.a[i][j] = 0;
}
}
}
return res;
}
matrix matrix_pow(matrix A, int n, int mod) {
// 快速求矩阵 A 的 n 次方
matrix res = unit(), temp = A;
for (; n; n /= 2) {
if (n & 1) {
res = matrix_mul(res, temp, mod);
}
temp = matrix_mul(temp, temp, mod);
}
return res;
}

大概代码就是这样子了。恩 看几道题来

计蒜客习题:Fib数列问题之二
问题描述
用 fib(n) 表示斐波那契数列的第 n项,现在要求你求 fib(n) mod m。fib(1)=1,fib(2)=1。
输入格式
输入 2 个整数 n(1≤n≤10^18 ),m(2≤m≤100000000)。
输出格式
输出 fib(n) 对 m 取模的值。
样例输入
100000000 100000000
样例输出
60546875

这个题…怎么说最明显的矩阵快速幂,因为之前学矩阵快速幂,学长就是拿FIB数列讲的啊hhhhh

AC 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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct mat{
int a[100][100];
};
mat mul(mat A,mat B,ll mod){
mat C;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
C.a[i][j]=0;
for(int k=0;k<2;k++){
C.a[i][j]+=A.a[i][k]*B.a[k][j]%mod;
C.a[i][j]%=mod;
}
}
}
return C;
}
mat unit()
{
mat res;
for(int i=0;i<2;i++){

for(int j=0;j<2;j++)
{
if(i==j)res.a[i][j]=1;
else res.a[i][j]=0;
}
}
return res;
}
mat pow(mat A,ll y,ll mod)
{

mat res=unit(),temp=A;
for(;y;y/=2){
if(y&1){
res=mul(res,temp,mod);
}
temp=mul(temp,temp,mod);
}
return temp;
}
int main()

{
ios::sync_with_stdio(false);
ll n,m;
cin>>n>>m;
mat A;
A.a[0][0]=1;A.a[0][1]=1;A.a[1][0]=1;A.a[1][1]=0;
A=pow(A,n,m);
cout<<A.a[1][0]<<endl;
return 0;
}

问题二:(有点改变得了

计蒜客习题:蒜头君倒水
问题描述
蒜头君倒了 2 杯热水在杯子里面,第一杯里面有 a 毫升,第二杯里面有 b 毫升。水太热了,蒜头君决定通过轮流倒水的方式来让水冷下来。每次倒水蒜头君把第一杯的 x%的水倒入第二杯,把第二杯的 y% 的水倒入第一杯(蒜头君有奇特的方法,能让这一过程是同是发生的,没有先后之分),蒜头君一直重复倒水,求倒了 k 次以后 2个杯子的水的容量。
输入格式
第 1 行输入 2 个正整数 a,b(0≤a,b≤10^8)
第 2 行输入 2 个正整数 x,y(0≤x,y≤100),
第 3 行输入一个整数 k(1≤k≤10^9)
输出格式
输入 2 个浮点数,用空格隔开,分表表示第一杯水和第二杯水的容量(毫升),输出结果误差在10^−2以内都可以接受。
样例输入
10 10
50 50
10000
样例输出
10.00 10.00

掏心窝子说,要不是这题在矩阵快速幂那我大概会这么做:
TLE 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
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
double a,b,x,y,k;
cin>>a>>b>>x>>y>>k;
double xx,yy;
xx=x*0.01;
yy=y*0.01;
while(k--){
double temp=a;
a=a-(xx*a)+(yy*b);
b=b-(yy*b)+(xx*temp);
}
printf("%.2f ",a);
printf("%.2f\n",b);
return 0;
}
```c
如我所说 TLE了,嘿嘿,其实我做的时候就知道会时间超限了,毕竟k是1e9
不BB了
AC CODE :
```c
#include <bits/stdc++.h>
using namespace std;
long long a,b,n;
double x,y;
struct mat
{
double aa[3][3];
};
mat p,wyh;
mat mul(mat A,mat B)
{
mat C;
for(int i=0;i<2;i++)
{ for(int j=0;j<2;j++)
{
C.aa[i][j]=0;
for(int k=0;k<2;k++)
{
C.aa[i][j]+=A.aa[i][k]*B.aa[k][j];
}
}
}
return C;
}
mat mpow(mat A,long long n)
{
mat res,temp=A;

for(int i=0;i<2;i++)
{ for(int j=0;j<2;j++)
{
if(i==j)res.aa[i][j]=1.00;
else res.aa[i][j]=0.00;
}
}
for(;n;n/=2){
if(n&1){
res=mul(res,temp);
}
temp=mul(temp,temp);
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin>>a>>b>>x>>y>>n;
p.aa[0][0]=1-x/100;
p.aa[0][1]=y/100;
p.aa[1][0]=x/100;
p.aa[1][1]=1-y/100;
wyh.aa[0][0]=a;
wyh.aa[1][0]=b;
mat res=mpow(p,n);
mat ans=mul(res,wyh);
cout<< fixed << setprecision(10) <<ans.aa[0][0]<<" "<<ans.aa[1][0]<<endl;
return 0;
}

贼沙雕,一开始我以为两位小数输出,交了好几次,后来发现是…输出结果误差在10^−2以内都可以接受。
CTM???然后改了还错,心态都没了,一番查错之后,发现在mpow函数中的temp=mul(temp,temp);写成了res=mul(temp,temp);
看来自己还是不够细心,回宿舍再看看挑战吧….就酱,

对了,肿肿?在看吗?晚安

coswindy

-------------本文结束感谢您的阅读-------------