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

矩阵系列题解

news 来源：原创 2025/9/13 11:51:47

1.洛谷 P1962 斐波那契数列

题意

大家都知道，斐波那契数列是满足如下性质的一个数列：

$F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.$

请你求出 $F_n \bmod 10^9 + 7$ 的值。

$1\le n < 2^{63}$ 。

思路

$\begin{bmatrix} F_{i-1} & F_{i} \end{bmatrix} =\begin{bmatrix} F_{i-2} &F_{i-1} \end{bmatrix}\cdot \begin{bmatrix} 0 & 1\\ 1 & 1 \end{bmatrix}$

2.SMOJ 数列1

题意

有一个数列：

$f_n = \left\{\begin{aligned} 0 \ (n \le 2) \\ 7f_{n-1}+6f_{n-2}+4\times 3^n \ (n\ge 3) \end{aligned}\right.$

请你求出 $f_n \bmod 10^9 + 7$ 的值。

$3\le n \le 10^9$ 。

思路

$\begin{bmatrix} f_{i-1} & f_i &4\times3^{i+1}\end{bmatrix}=\begin{bmatrix} f_{i-2} & f_{i-1} & 4\times 3^i\end{bmatrix}\cdot \begin{bmatrix} 0 & 6 & 0\\ 1 & 7 & 0\\ 0 & 1 & 3 \end{bmatrix}$

3.SMOJ 数列2

题意

有一个数列：

$f_n = \left\{\begin{aligned} 0 \ (n \le 2) \\ 7f_{n-1}+6f_{n-2}+4\times 3^n+5n \ (n\ge 3) \end{aligned}\right.$

请你求出 $f_n \bmod 10^9 + 7$ 的值。

思路

$\begin{bmatrix} f_{i-1} & f_i & 4\times 3^{i+1} & 5(i+1) & 5 \end{bmatrix}= \begin{bmatrix} f_{i-2} & f_{i-1} & 4\times 3^i & 5i & 5 \end{bmatrix}\cdot\begin{bmatrix} 0 & 6 & 0 & 1 & 0\\ 1 & 7 & 0 & 1 & 0\\ 0 & 1 & 3 & 1 & 0\\ 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}$

4.SMOJ 幸运数

题意

小明认为只有数字 $4$ 和 $7$ 是幸运数字，其他数字都不是。如果一个整数的每个数字都是幸运数字，那么该整数就是幸运整数。

给出一个数组 $numbers_{1...n}$ 。

一个长度为 $L$ 的幸运数列 $A_{0...L-1}$ 必须同时满足：

$\forall i\in[0,L)$ ， $A_i$ 必须是幸运整数。
$\forall i\in[0,L)$ ， $A_i$ 的最后一个数字必须等于 $A [i + 1]$ 的第一个数字。
$\forall i\in[0,L)$ ，至少存在一个下标 $j$ 满足 $A_i=numbers_j$ 。

输出有多少个不同的长度为L的幸运序列，答案模 $1234567891$ 。

对于两个长度都是L的幸运序列 $A_{0...L- 1}$ 和 $B_{0...L - 1}$ ，他们被认为是不同序列的条件是： $\exist i,A_i\neq B_i$ 。

$1\le n\le 50,1\le numbers_i\le 10^9,1\le L\le 10^9$

思路

对所有幸运数分类：

$4$ 头 $4$ 尾
$4$ 头 $7$ 尾
$7$ 头 $4$ 尾
$7$ 头 $7$ 尾

用一个桶 $c n t$ 记个数。

令 $f_{i,type}$ 表示前 $i$ 个幸运数组成的序列中，序列最后一个数种类为 $type\in [1,4]$ 的方案数。

那么容易写出转移式子：

$f_{i,1}=f_{i-1,1}\cdot cnt_1+f_{i-1,3}\cdot cnt_1$

$f_{i,2}=f_{i-1,1}\cdot cnt_2+f_{i-1,3}\cdot cnt_2$

$f_{i,3}=f_{i-1,2}\cdot cnt_3+f_{i-1,4}\cdot cnt_3$

$f_{i,4}=f_{i-1,2}\cdot cnt_4+f_{i-1,4}\cdot cnt_4$

只需做 $L$ 次 dp 即可，但是 $L$ 最大去到 $10^9$ ，显然会炸。由于操作单调，因此考虑矩阵快速幂优化：

$\begin{bmatrix} f_{i,1} & f_{i,2} & f_{i,3} & f_{i,4} \end{bmatrix}=\begin{bmatrix} f_{i-1,1} & f_{i-1,2} & f_{i-1,3} & f_{i-1,4} \end{bmatrix}\cdot\begin{bmatrix} cnt_1 & cnt_2 & 0 & 0\\ 0 & 0 & cnt_3 & cnt_4\\ cnt_1 & cnt_2 & 0 & 0\\ 0 & 0 & cnt_3 & cnt_3 \end{bmatrix}$

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=102,mod=1234567891;
struct matrix
{ll row,col;ll data[N][N];matrix(ll r,ll c,ll isI){row=r;col=c;memset(data,0,sizeof(data));if(isI){for(int i=1;i<=row;i++)data[i][i]=1;}}
};
matrix operator * (const matrix &a,const matrix &b)
{matrix c(a.row,b.col,0);for(int i=1;i<=a.row;i++)for(int j=1;j<=b.col;j++)for(int k=1;k<=a.col;k++)c.data[i][j]=(c.data[i][j]+a.data[i][k]*b.data[k][j]%mod+mod)%mod;return c; 
}
matrix qpow_matrix(matrix a,ll k)
{matrix ret(a.row,a.col,1);while(k){if(k&1)ret=ret*a;a=a*a;k>>=1;}return ret;
}
ll n,m,a[N];
ll f[N][5],cnt[5];
ll type(string x)
{ll sx=x.size();x='*'+x;for(int i=1;i<=sx;i++)if(x[i]!='4'&&x[i]!='7')return 0;if(x[1]=='4'&&x[sx]=='4')return 1;else if(x[1]=='4'&&x[sx]=='7')return 2;else if(x[1]=='7'&&x[sx]=='4')return 3;else return 4;
}
vector<string>luk[N];
int main()
{scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++){string a;cin>>a;ll t=type(a);if(!t)continue;bool flag=1;for(auto x:luk[t]){if(x==a){flag=0;break;}}if(flag)luk[t].push_back(a),cnt[t]++;}matrix A(1,4,0);matrix B(4,4,0);for(int i=1;i<=n;i++)A.data[1][i]=cnt[i];B.data[1][1]=B.data[3][1]=cnt[1];B.data[1][2]=B.data[3][2]=cnt[2];B.data[2][3]=B.data[4][3]=cnt[3];B.data[2][4]=B.data[4][4]=cnt[4];A=A*qpow_matrix(B,m-1);ll ans=0;for(int i=1;i<=4;i++)ans=(ans+A.data[1][i])%mod;printf("%lld",ans);return 0;
}

5.SMOJ 序列/CF691E Xor-sequences

题意

给定一个数集 $A$ ，现在你需要构造一个长度为 $m$ 的序列 $B$ ，序列 $B$ 的元素从数集 $A$ 中任意挑选，要求 $B$ 中任意相邻的两个数字的异或值二进制表示中 $1$ 的个数是 $3$ 的倍数，请问 $B$ 的有多少种合法的构造方案？两种方案不同当且仅当存在 $b_i$ 在 $A$ 中的位置不同。

$1\le n\le 100,1\le m\le 10^{18},0\le a_i\le 10^{18}$

思路

设 $f_{i,j}$ 表示选择了 $i$ 个数，最后一个数是 $a_j$ 的方案数（注意数列可以乱序），那么有：
$f_{i,j}=\sum_{k=1}^{n}f_{i-1,k}\cdot\ A_{i,j}$

其中 $A_{i,j}$ 表示：
$A_{i,j}=\left [a_j\bigoplus a_k \bmod3=0\right ]$

中括号为艾弗森括号，不难发现 $A$ 以对角线对称。

对于每个 $(i, j)$ ，都要遍历 $k\in[1,n]$ 来逐一比对一遍是否有 $a_j\bigoplus a_k \bmod3=0$ 。如此过程，实则与矩阵乘法的运算过程比较相似（这还是比较注意力惊人了，除非你对矩阵无比的熟悉）那么不妨使用矩阵快速幂优化了。最终答案就是：
$ans=\sum data(A^{n-1})$

$d a t a (M)$ 表示一个矩阵 $M$ 内所有元素。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=102,mod=1e9+7;
struct matrix
{ll row,col;ll data[N][N];matrix(ll r,ll c,ll isI){row=r;col=c;memset(data,0,sizeof(data));if(isI){for(int i=1;i<=row;i++)data[i][i]=1;}}
};
matrix operator * (const matrix &a,const matrix &b)
{matrix c(a.row,b.col,0);for(int i=1;i<=a.row;i++)for(int j=1;j<=b.col;j++)for(int k=1;k<=a.col;k++)c.data[i][j]=(c.data[i][j]+a.data[i][k]*b.data[k][j]%mod+mod)%mod;return c; 
}
matrix qpow_matrix(matrix a,ll k)
{matrix ret(a.row,a.col,1);while(k){if(k&1)ret=ret*a;a=a*a;k>>=1;}return ret;
}
ll n,m,a[N];
ll popcnt(ll x)
{ll ret=0;while(x){if(x&1)ret++;x>>=1;}return ret;
}
int main()
{scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);matrix A(n,n,0);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)A.data[i][j]=(popcnt(a[i]^a[j])%3==0);A=qpow_matrix(A,m-1);ll ans=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans=(ans+A.data[i][j])%mod;printf("%lld",ans);return 0;
}

6.SMOJ 黑板与数字/CF621E Wet Shark and Blocks

（本篇较口胡，见谅）

题意

有 $b$ 个黑板，从左往右排成一行。

第 $1$ 个黑板从左往右写有 $n$ 个数字，每个数字是 $1$ 至 $9$ 范围内的数字。

把第 $1$ 个黑板的所有数字复制一份，写到第 $2$ 个黑板。

把第 $1$ 个黑板的所有数字复制一份，写到第 $3$ 个黑板。

把第 $1$ 个黑板的所有数字复制一份，写到第 $b$ 个黑板。

从这 $b$ 个黑板中，各取一个数字，构成一个 $b$ 位数，要使得这个 $b$ 位数模 $x$ 的结果是 $k$ ，求方案数（同一个黑板内取相同的数字算不同方案，因为位置不同），答案模 $10^9+7$ 。

思路

令 $f_{i,j}$ 表示选了 $i$ 个格子，模 $x$ 余数为 $j$ ，那么有转移式子：
$f_{i,10j+k \bmod x}=f_{i-1,j}+num(k)$

其中 $n u m (k)$ 表示： $num(k)=\sum_{i=1}^n [a_i\bmod x=k]$

再枚举每一位，去到了 $\Theta(bx)$ ；但是如此操作，像上几篇题解一样，与矩阵乘法相类似，因此可以考虑矩阵快速幂优化到 $\Theta(\log_2b)$

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=111,mod=1e9+7;
ll n,b,k,x,a,yx[N];
struct matrix
{ll row,col;//行和列ll data[N][N];matrix(ll r,ll c,ll isI){row=r;col=c;memset(data,0,sizeof(data));if(isI){for(int i=0;i<row;i++)data[i][i]=1;}}
};
matrix operator * (const matrix &a,const matrix &b)
{matrix c(a.row,b.col,0);for(int i=0;i<a.row;i++)for(int j=0;j<b.col;j++)for(int k=0;k<a.col;k++)c.data[i][j]=(c.data[i][j]+a.data[i][k]*b.data[k][j]%mod+mod)%mod;return c;
}
matrix qpow_matrix(matrix a,ll k)
{matrix res(a.row,a.col,1);while(k){if(k&1)res=res*a;a=a*a;k>>=1;}return res;
}
int main()
{scanf("%lld%lld%lld%lld",&n,&b,&k,&x);for(int i=1;i<=n;i++){scanf("%lld",&a);yx[a%x]++;}matrix A(1,x,0);for(int i=0;i<x;i++)A.data[0][i]=yx[i];matrix B(x,x,0);for(int i=0;i<x;i++){for(int j=0;j<x;j++){ll r=(i*10+j)%x;B.data[i][r]+=yx[j];}}A=A*qpow_matrix(B,b-1);printf("%lld",A.data[0][k]);return 0;
}