矩阵系列 题解

1.洛谷 P1962 斐波那契数列

题意

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

$$F_n=\{\begin{array}{r}1(n\le 2)\\ F_{n-1}+F_{n-2}(n\ge 3)\end{array}$$

请你求出 $F_n\mathrm{mod}10^9+7$ 的值。

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

思路

$$\left[\begin{array}{cc}{F}_{i-1}& F_i\end{array}\right]=\left[\begin{array}{cc}{F}_{i-2}& F_{i-1}\end{array}\right]\cdot \left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]$$

2.SMOJ 数列1

题意

有一个数列：

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

请你求出 $f_n\mathrm{mod}10^9+7$ 的值。

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

思路

$$\left[\begin{array}{ccc}{f}_{i-1}& f_i& 4\times 3^{i+1}\end{array}\right]=\left[\begin{array}{ccc}{f}_{i-2}& f_{i-1}& 4\times 3^i\end{array}\right]\cdot \left[\begin{array}{ccc}0& 6& 0\\ 1& 7& 0\\ 0& 1& 3\end{array}\right]$$

3.SMOJ 数列2

题意

有一个数列：

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

请你求出 $f_n\mathrm{mod}10^9+7$ 的值。

思路

$$\left[\begin{array}{ccccc}{f}_{i-1}& f_i& 4\times 3^{i+1}& 5(i+1)& 5\end{array}\right]=\left[\begin{array}{ccccc}{f}_{i-2}& f_{i-1}& 4\times 3^i& 5i& 5\end{array}\right]\cdot \left[\begin{array}{ccccc}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{array}\right]$$

4.SMOJ 幸运数

题意

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

给出一个数组 $number{s}_{\mathrm{1...}n}$。

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

1. $\forall i\in [0,L)$，$A_i$ 必须是幸运整数。

2. $\forall i\in [0,L)$，$A_i$ 的最后一个数字必须等于 $A[i+1]$ 的第一个数字。

3. $\forall i\in [0,L)$，至少存在一个下标 $j$ 满足 $A_i=number{s}_j$。

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

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

$1\le n\le 50,1\le number{s}_i\le 10^9,1\le L\le 10^9$

思路

对所有幸运数分类：

1. $4$ 头 $4$ 尾
2. $4$ 头 $7$ 尾
3. $7$ 头 $4$ 尾
4. $7$ 头 $7$ 尾

用一个桶 $cnt$ 记个数。

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

那么容易写出转移式子：

$$f_{i,1}=f_{i-1,1}\cdot cn{t}_1+f_{i-1,3}\cdot cn{t}_1$$

$$f_{i,2}=f_{i-1,1}\cdot cn{t}_2+f_{i-1,3}\cdot cn{t}_2$$

$$f_{i,3}=f_{i-1,2}\cdot cn{t}_3+f_{i-1,4}\cdot cn{t}_3$$

$$f_{i,4}=f_{i-1,2}\cdot cn{t}_4+f_{i-1,4}\cdot cn{t}_4$$

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

$$\left[\begin{array}{cccc}{f}_{i,1}& f_{i,2}& f_{i,3}& f_{i,4}\end{array}\right]=\left[\begin{array}{cccc}{f}_{i-1,1}& f_{i-1,2}& f_{i-1,3}& f_{i-1,4}\end{array}\right]\cdot \left[\begin{array}{cccc}cn{t}_1& cn{t}_2& 0& 0\\ 0& 0& cn{t}_3& cn{t}_4\\ cn{t}_1& cn{t}_2& 0& 0\\ 0& 0& cn{t}_3& cn{t}_3\end{array}\right]$$

代码

#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⨁a_k\mathrm{mod}3=0\right]$$

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

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

$data(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\mathrm{mod}x}=f_{i-1,j}+num(k)$$

其中 $num(k)$ 表示：$$num(k)=\sum _{i=1}^n[a_i\mathrm{mod}x=k]$$

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

代码

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