HPU 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;
    }
}