当前位置：首页 > article >正文

矩阵快速幂

article 2024/11/15 15:08:59

喜欢用董晓老师的板子

1303. 斐波那契前 n 项和

大家都知道 Fibonacci 数列吧，f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2。

现在问题很简单，输入 nn 和 mm，求 fnfn 的前 nn 项和 SnmodmSnmodm。

输入格式

共一行，包含两个整数 nn 和 mm。

输出格式

输出前 nn 项和 SnmodmSnmodm 的值。

数据范围

1≤n≤20000000001≤n≤2000000000,
1≤m≤10000000101≤m≤1000000010

输入样例：

5 1000

输出样例：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct matrix{
    ll c[5][5];
    matrix(){memset(c,0,sizeof c);}
}A,res;
ll n,m;
matrix operator*(matrix&a,matrix&b)
{
    matrix t;
    for(int i=1;i<=3;i++)
    for(int j=1;j<=3;j++)
    for(int k=1;k<=3;k++)
    t.c[i][j]=(t.c[i][j]+a.c[i][k]*b.c[k][j])%m;
    return t;
}
void quickpow(int k)
{
    A.c[1][2]=A.c[2][1]=A.c[2][2]=A.c[2][3]=A.c[3][3]=1;
    res.c[1][1]=res.c[1][2]=res.c[1][3]=1;
    while(k)
    {
        if(k&1)res=res*A;
        A=A*A;
        k>>=1;
    }
}
int main()
{
    cin>>n>>m;
    if(n==1){
        cout<<1%m;
        return 0;
    }
    quickpow(n-1);
    cout<<res.c[1][3];
    return 0;
}

1217. 垒骰子

赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。

经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！

我们先来规范一下骰子：11 的对面是 44，22 的对面是 55，33 的对面是 66。

假设有 mm 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。

atm想计算一下有多少种不同的可能的垒骰子方式。

两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。

由于方案数可能过多，请输出模 109+7109+7 的结果。

输入格式

第一行包含两个整数 n,mn,m，分别表示骰子的数目和排斥的组数。

接下来 mm 行，每行两个整数 a,ba,b，表示 aa 和 bb 数字不能紧贴在一起。

输出格式

共一个数，表示答案模 109+7109+7 的结果。

数据范围

1≤n≤1091≤n≤109,
1≤m≤361≤m≤36,
1≤a,b≤61≤a,b≤6

输入样例：

2 1
1 2

输出样例：

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
typedef long long ll;
int n,m;
struct matrix{
    ll c[7][7];
     matrix (){memset(c,0,sizeof c);}
} A,res;
matrix operator*(matrix&a,matrix&b)
{
    matrix t;
    for(int i=1;i<=6;i++)
    for(int j=1;j<=6;j++)
    for(int k=1;k<=6;k++)
    t.c[i][j]=(t.c[i][j]+a.c[i][k]*b.c[k][j])%MOD;
    return t;
}
int get(int x)
{
    if (x > 3) return x - 3;
    return x + 3;
}
void quickpow(int k)
{
    for(int i=1;i<=6;i++)res.c[1][i]=4;
    while(k)
    {
        if(k&1)res=res*A;
        A=A*A;
        k>>=1;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=6;i++)
    for(int j=1;j<=6;j++)
    A.c[i][j]=4;
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        A.c[x][get(y)]=0;
        A.c[y][get(x)]=0;
    }
    quickpow(n-1);
    int ans=0;
    for(int i=1;i<=6;i++)ans=(ans+res.c[1][i])%MOD;
    cout<<ans;
    return 0;
}

4406. 积木画

小明最近迷上了积木画，有这么两种类型的积木，分别为 II 型（大小为 22 个单位面积）和 LL 型（大小为 33 个单位面积）：

QQ截图20220410144642.png

同时，小明有一块面积大小为 2×N2×N 的画布，画布由 2×N2×N 个 1×11×1 区域构成。

小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？

积木可以任意旋转，且画布的方向固定。

输入格式

输入一个整数 NN，表示画布大小。

输出格式

输出一个整数表示答案。

由于答案可能很大，所以输出其对 10000000071000000007 取模后的值。

数据范围

1≤N≤1071≤N≤107。

输入样例：

输出样例：

样例解释

五种情况如下图所示，颜色只是为了标识不同的积木：

QQ截图20220410144846.png

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
struct martrix {
    ll c[5][5];
    martrix (){memset(c,0,sizeof c);}
}A,res;
ll n,m;
martrix operator*(martrix &a,martrix &b)
{
    martrix t;
    for(int i=1;i<=3;i++)
    for(int j=1;j<=3;j++)
    for(int k=1;k<=3;k++)
    t.c[i][j]=(t.c[i][j]+a.c[i][k]*b.c[k][j])%MOD;
    return t;
}
void quickpow(int k)
{
    res.c[1][1]=1,res.c[1][2]=2,res.c[1][3]=1;
    A.c[1][1]=1,A.c[1][2]=2,A.c[1][3]=1;
    A.c[2][1]=0,A.c[2][2]=1,A.c[2][3]=1;
    A.c[3][1]=1,A.c[3][2]=0,A.c[3][3]=0;
    while(k){
        if(k&1)res=res*A;
        A=A*A;
        k>>=1;
    }
}
int main()
{
    int n;
    cin>>n;
    quickpow(n-1);
    cout<<res.c[1][1]%MOD;
    return 0;
}

查看全文

http://www.kler.cn/a/318251.html