Summer Day 16
今天主要学习了矩阵快速幂的计算以及相关问题的解决方法。题还是挺好写的，矩阵快速幂也挺好理解的，实在不行的话记模板也不错。
求递推序列的第N项
Description:
有一个序列是这样定义的：f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
给出A，B和N，求f(n)的值。
输入
输入3个数：A,B,N。数字之间用空格分割。(-10000 <= A, B <= 10000, 1 <= N <= 10^9)
输出
输出f(n)的值。
输入样例
3 -1 5
输出样例
6
Problem solving:
这道题的意思是给你一个递推公式，求出第n项的值。
如果直接递推的话，1e9的n一定是会超时的。这时候矩阵快速幂大显身手。
只需要构造出来两个矩阵就行，板子题。
Code:
#include<bits/stdc++.h>
using namespace std;
struct node{
int m[5][5];
};
node mm,p;
node mul(node a,node b)
{
node now;
memset(now.m,0,sizeof(now.m));
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
{
for(int k=1;k<=2;k++)
{
now.m[i][j]=((now.m[i][j]+a.m[i][k]*b.m[k][j])+7)%7;
}
}
}
return now;
}
node poww(node a,int b)
{
node ans;
memset(ans.m,0,sizeof(ans.m));
for(int i=1;i<=2;i++) ans.m[i][i]=1;
while(b)
{
if(b&1) ans=mul(ans,a);
b/=2;
a=mul(a,a);
}
return ans;
}
int main()
{
int a,b,k;
cin>>a>>b>>k;
mm.m[1][1]=1,mm.m[2][1]=1;
mm.m[2][2]=0,mm.m[1][2]=0;//构造的一个矩阵
p.m[1][1]=a,p.m[1][2]=b,p.m[2][1]=1,p.m[2][2]=0;//构造的另一个矩阵
if(k==1||k==2)
{
puts("1");
}
else
{
node mid=poww(p,k-2);
mid=mul(mid,mm);
cout<<mid.m[1][1]<<endl;
}
}矩阵快速幂
Description:
给出一个N * N的矩阵，其中的元素均为正整数。求这个矩阵的M次方。由于M次方的计算结果太大，只需要输出每个元素Mod (10^9 + 7）的结果。
输入
第1行：2个数N和M，中间用空格分隔。N为矩阵的大小，M为M次方。(2 <= N <= 100, 1 <= M <= 10^9)
第2 - N + 1行：每行N个数，对应N * N矩阵中的1行。(0 <= N[i] <= 10^9)
输出
共N行，每行N个数，对应M次方Mod (10^9 + 7)的结果。
输入样例
2 3
1 1
1 1
输出样例
4 4
4 4
Problem solving:
这个就是个板子题，直接写就行了。
Code:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e9+7;
typedef long long ll;
struct node{
ll m[105][105];
};
ll n,k;
node mul(node a,node b)
{
node ans;
memset(ans.m,0,sizeof(ans.m));
for(ll i=0;i<n;i++)
{
for(ll j=0;j<n;j++)
{
for(ll k=0;k<n;k++)
{
ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%maxn;//这里已经要先+再取模。坑点
}
}
}
return ans;
}
node poww(node a,ll b)
{
node now;
memset(now.m,0,sizeof(now.m));
for(ll i=0;i<n;i++) now.m[i][i]=1;
while(b)
{
if(b&1) now=mul(now,a);
b/=2;
a=mul(a,a);
}
return now;
}
int main()
{
cin>>n>>k;
node ans;
for(ll i=0;i<n;i++)
for(ll j=0;j<n;j++)
cin>>ans.m[i][j];
ans=poww(ans,k);
for(ll i=0;i<n;i++)
{
for(ll j=0;j<n;j++)
cout<<ans.m[i][j]<<" ";
puts("");
}
}矩阵乘法
Description:
给出2个N * N的矩阵M1和M2，输出2个矩阵相乘后的结果。
输入
第1行：1个数N，表示矩阵的大小(2 <= N <= 100)
第2 - N + 1行，每行N个数，对应M1的1行(0 <= M1[i] <= 1000)
第N + 2 - 2N + 1行，每行N个数，对应M2的1行(0 <= M2[i] <= 1000)
输出
输出共N行，每行N个数，对应M1 * M2的结果的一行。
输入样例
2
1 0
0 1
0 1
1 0
输出样例
0 1
1 0
Problem solving:
考察了矩阵相乘的实现
Code:
#include<bits/stdc++.h>
using namespace std;
struct node{
int m[105][105];
};
node a,b;
int n;
node mul(node a,node b)
{
node ans;
memset(ans.m,0,sizeof(ans.m));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
ans.m[i][j]=ans.m[i][j]+a.m[i][k]*b.m[k][j];//矩阵相乘就是通过这三个for循环实现的
return ans;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>a.m[i][j];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>b.m[i][j];
node ans=mul(a,b);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout<<ans.m[i][j]<<" ";
puts("");
}
}Fibonacci
Description:
菲波那契数列是指这样的数列: 数列的第一个是0和第二个数是1，接下来每个数都等于前面2个数之和。 给出一个正整数a，要求菲波那契数列中第a个数的后四位是多少。
Input
多组数据 -1结束 范围1~10^9
Output
第x项的后4位
Sample Input
0
9
999999999
1000000000
-1
Sample Output
0
34
626
6875
Problem solving:
然后毒瘤题意还是忽略了吧，直接看样例妥了
求斐波那契的第n项。其实就是给了你递推式，构造出来矩阵就行了。要求输出后四位其实就是对10000取模，每次计算出来都取模，就避免了爆精度的问题。
Code:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=10000;
struct node{
int m[3][3];
};
typedef long long ll;
node mm,p;
node mul(node a,node b)
{
node ans;
memset(ans.m,0,sizeof(ans.m));
for(ll i=1;i<=2;i++)
for(ll j=1;j<=2;j++)
for(ll k=1;k<=2;k++)
ans.m[i][j]=((ans.m[i][j]+a.m[i][k]*b.m[k][j])%mod)%mod;
return ans;
}
node poww(node a,ll b)
{
node ans;
memset(ans.m,0,sizeof(ans.m));
for(ll i=1;i<=2;i++) ans.m[i][i]=1;
while(b)
{
if(b&1) ans=mul(ans,a);
a=mul(a,a);
b/=2;
}
return ans;
}
int main()
{
ll n;
p.m[1][1]=1,p.m[1][2]=1,p.m[2][1]=1,p.m[2][2]=0;
mm.m[1][1]=1,mm.m[2][1]=1,mm.m[2][2]=0,mm.m[1][2]=0;
while(cin>>n&&n!=-1)
{
if(n==0)
{
puts("0");
continue;
}
if(n==1||n==2)
{
puts("1");
continue;
}
node mid=poww(p,n-2);
mid=mul(mid,mm);
cout<<mid.m[1][1]<<endl;
}
}Tr A
Description:
A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。
Input
数据的第一行是一个T，表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行，每行有n个数据，每个数据的范围是[0,9]，表示方阵A的内容。
Output
对应每组数据，输出Tr(A^k)%9973。
Sample Input
2
2 2
1 0
0 1
3 99999999
1 2 3
4 5 6
7 8 9
Sample Output
2
2686
Problem solving:
直接运用矩阵快速幂求出最后状态的矩阵，对角线相加就行了
Code:
#include<bits/stdc++.h>
using namespace std;
int n,k;
struct node{
int m[15][15];
};
node now;
node mul(node a,node b)
{
node ans;
memset(ans.m,0,sizeof(ans.m));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<n;k++)
{
ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%9973;
}
}
}
return ans;
}
node poww(node a,int b)
{
node ans;
memset(ans.m,0,sizeof(ans.m));
for(int i=0;i<n;i++) ans.m[i][i]=1;
while(b)
{
if(b&1) ans=mul(ans,a);
a=mul(a,a);
b/=2;
}
return ans;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>k;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cin>>now.m[i][j];
}
node mid=poww(now,k);
int ans=0;
for(int i=0;i<n;i++)
{
ans=(ans+mid.m[i][i])%9973;
}
cout<<ans<<endl;
}
}A Simple Math Problem
Description:
Lele now is thinking about a simple function f(x).
If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .
Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.
Input
The problem contains mutiple test cases.Please process to the end of file.
In each case, there will be two lines.
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9.
Output
For each case, output f(k) % m in one line.
Sample Input
10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0
Sample Output
45
104
Problem solving:
题意就是给你一个递推式求出第n项。
难点就是递推式有点长，但是这个跟斐波那契那个其实是一样的，构造的常数矩阵是
常数矩阵都构造出来了，那么接下来的就是套版子了。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
ll m[15][15];
};
ll k,m;
node now,p;
node mul(node a,node b)
{
node now;
memset(now.m,0,sizeof(now.m));
for(int i=0;i<10;i++)
{
for(int j=0;j<10;j++)
{
for(int k=0;k<10;k++)
{
now.m[i][j]=(a.m[i][k]*b.m[k][j]+now.m[i][j])%m;
}
}
}
return now;
}
node poww(node a,int b)
{
node ans;
memset(ans.m,0,sizeof(ans.m));
for(int i=0;i<10;i++) ans.m[i][i]=1;
while(b)
{
if(b&1) ans=mul(ans,a);
a=mul(a,a);
b/=2;
}
return ans;
}
int main()
{
while(cin>>k>>m)
{
if(k<=9)
{
cout<<k<<endl;
continue;
}
for(int i=0;i<10;i++)
{
cin>>p.m[0][i];
}
for(int i=1;i<10;i++)
{
for(int j=0;j<10;j++)
{
if(i-1==j)
p.m[i][j]=1;
}
}
for(int i=0;i<10;i++) now.m[i][0]=9-i;
node ans=poww(p,k-9);
ans=mul(ans,now);
cout<<ans.m[0][0]<<endl;
}
}Recursive sequence
Description:
Problem solving:
也是给了递推式求第n项的问题，但是这个就比较难了，因为构建常数矩阵的时候会发现一个严肃的问题，n^4与(n+1)^4找关系的时候会很爆炸。
这时候我们就需要化简了。
(n+1)^4=n^4+4*n^3+6*n^2+4*n+1
(n+1)^3=n^3+3*n^2+3*n+1
(n+1)^2=n^2+2*n+1
n+1=n+1
所以我们构建出来的常数矩阵就是
接下来就是计算了，套板子就行，一开始的矩阵是只有第一列有值得。
值分别为b,a,81,27,9,3,1
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a,b;
struct node{
ll m[7][7];
};
const ll mod=2147493647;
node mm,p;
node mul(node a,node b)
{
node now;
memset(now.m,0,sizeof(now.m));
for(ll i=0;i<7;i++)
{
for(ll j=0;j<7;j++)
{
for(ll k=0;k<7;k++)
{
now.m[i][j]=(a.m[i][k]*b.m[k][j]+now.m[i][j])%mod;
}
}
}
return now;
}
node poww(node a,ll b)
{
node ans;
memset(ans.m,0,sizeof(ans.m));
for(ll i=0;i<10;i++) ans.m[i][i]=1;
while(b)
{
if(b&1) ans=mul(ans,a);
a=mul(a,a);
b/=2;
}
return ans;
}
int main()
{
ll t;
cin>>t;
while(t--)
{
cin>>n>>a>>b;
if(n==1)
{
cout<<a<<endl;
continue;
}
if(n==2)
{
cout<<b<<endl;
continue;
}
memset(mm.m,0,sizeof(mm.m));
memset(p.m,0,sizeof(p.m));
mm.m[0][0]=b,mm.m[1][0]=a;
mm.m[2][0]=81,mm.m[3][0]=27,mm.m[4][0]=9,mm.m[5][0]=3,mm.m[6][0]=1;
p.m[0][0]=1,p.m[0][1]=2,p.m[0][2]=1;
p.m[1][0]=1;
p.m[2][2]=1,p.m[2][3]=4,p.m[2][4]=6,p.m[2][5]=4,p.m[2][6]=1;
p.m[3][3]=1,p.m[3][4]=3,p.m[3][5]=3,p.m[3][6]=1;
p.m[4][4]=1,p.m[4][5]=2,p.m[4][6]=1;
p.m[5][5]=1,p.m[5][6]=1;
p.m[6][6]=1;
node mid=poww(p,n-2);
mid=mul(mid,mm);
cout<<mid.m[0][0]<<endl;
}
}
安克创新 Anker公司氛围 61人发布