矩陣計算

矩陣加減法

要求兩個矩陣的行和列相等，兩個矩陣對應的位置相加減即可

矩陣乘法

1. 一個數 \(k\) 乘矩陣 \(A\)，把 \(k\) 乘以矩陣的各個元素，記為 \(kA\)

2. 兩個矩陣 \(A\) 與 \(B\) 相乘，要求 \(A\) 的列數等于 \(B\) 的行數， \(A\) 尺寸為 \(m*n\)，\(B\) 尺寸為 \(n*u\)，乘積 \(C\) 的尺寸為 \(m*u\)，計算公式為 \(C[i,j]=\sum^n_{k=1}A[i][k]*B[k][j]\)

相當于是固定 \(A\) 的一行，\(B\) 的一列，并把對應的數乘起來再全部加起來作為 \(C[i][j]\) 的答案

矩陣乘法不滿足交換律 \(AB\neq BA\) 因為要滿足要求 \(A\) 的列數等于 \(B\) 的行數這一限制，而反過來就不一定能滿足了

矩陣乘法滿足結合律 \((AB)C=A(BC)\) 和分配律 \((A+B)C=AC+BC\)，這個手玩一下就好了

T1:

快速冪，板子

T2：

做這種題應該先把遞推式子列出來，然后再根據公式列出矩陣，然后往里套就行了

T3：

ybt題解錯誤

首先這一部分是正確的

然后我們考慮這種形式很矩陣快速冪,就相當于是矩陣 \(A^k=A^{k-1}*A\)

然后A初始化的話就是我們原來的鄰接矩陣，自爆的話就將每一個點朝0號節點連一條邊，停留的話就將這個點和自己連一條邊

for(int i=1;i<=m;i++){
    scanf("%d%d",&u,&v);
    b.m[u][v]=1;b.m[v][u]=1;
}
for(int i=1;i<=n;i++)  b.m[i][0]=1;
for(int i=0;i<=n;i++)  b.m[i][i]=1;//這里為什么從0開始，因為我們要把每一秒自爆的方案數留到最后第t秒的時候

最后答案即為

for(int i=0;i<=n;i++){
    num+=b.m[1][i];
    num%=mod;
}

2025.1.27補檔：

我試圖解釋一下以上思路是怎么想到的

我最開始設的dp狀態是在第 j 秒走到 i 點的方案數設為 \(dp[i][j]\)

我們會發現這樣的轉移必定會與邊與邊之間的關系有關，這樣我們就不得不做 t 次轉移，然而這樣是承受不起的

所以我們想到了另一種方案，鄰接矩陣，然后就會發現鄰接矩陣轉移的方式和矩陣乘法一摸一樣，并且每一次轉移乘的矩陣都是相同的，所以可以使用矩陣快速冪加速

T4：

T5：

廣義矩陣乘法：

只要滿足這些性質的都可以進行廣義矩陣乘法

然后要先離散化一下，只有200個點可用

T6:

跟狹義斐波那契額數列一樣，都是一個套路推出來 \(A\) 矩陣，注意因為給的是 \(a1,a2\) 兩項，所以要乘 \(n-2\) 次方

T7:

找規律？dp？

在嘗試了好多次dp后我放棄了

然后發現其實是找規律題

我們看題解就行了，講的聽清楚的

具體思路就是對行和列相等的情況分開計算，最后再容斥掉都相等的情況就行了

T8:

首先每個數是獨立的，所以我們只用考慮每一個數只要不在所有k個s中出現即可，方案數 \(2^k-1\) 然后因為有n個數，所以是 \((2^k-1)^n\) 種方案

因為n,k都非常之大，所以我們只能用字符串讀入，然后又不想寫高精，怎么辦呢，我寫了一個10進制的快速冪，就過了，非常簡單

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=70,mod=1e9+7;
int lg[N];
char n[N],k[N];
int quickpow(int x,char *g){
    int len=strlen(g+1),ans=1;
    // printf("%lld\n",len);
    lg[0]=x;
    for(int i=1;i<=63;i++){
        lg[i]=1;
        for(int j=1;j<=10;j++){
            lg[i]=lg[i]*lg[i-1]%mod;
        }
    }
    for(int i=len;i>=1;i--){
        for(int j=1;j<=g[i]-'0';j++){
            // printf("%lld\n",j);
            ans=ans*lg[len-i]%mod;
        }
    }
    return ans;
}
signed main(){
    cin>>n+1>>k+1;
    int cnt=quickpow(2,k);
    printf("%lld",quickpow((cnt-1+mod)%mod,n));
}

T9:

推式子太巧妙了?。。?/p>

經典轉化技巧 \(C^k_n=C^{n-k}_n\)

想到這個式子就完成了

具體推導過程看題解

注意因為輸入時 \(n,s,d\) 都大于 \(1e9\) 所以在做乘法時應先將兩邊都取模