矩阵乘法题单¶
P哥破解密码¶
定义一个串合法，当且仅当串只由 \(\verb!A!\) 和 \(\verb!B!\) 构成，且没有连续的 \(3\) 个 \(\verb!A!\)。P 哥知道，密码就是长度为 \(N\) 的合法字符串数量对 \(19260817\) 取模的结果。但是 P 哥不会算，所以他只能把 \(N\) 告诉你，让你来算。
至于为什么要对这个数取模，好像是因为纪念某个人，但到底是谁，P 哥也不记得了。
然而他忘记字符串长度 \(N\) 应该是多少了，于是他准备试 \(M\) 组数据。
输入格式
第一行给出一个整数 \(M\) 表示询问次数。
接下来 \(M\) 行每行给出一个正整数 \(N\)，表示该组询问中字符串的长度。
输出格式
对于每一次询问输出一行一个整数表示答案。
- 对于 \(100\%\) 数据，全部 \(N\leq10^9\)，\(M\leq10\)。
先写出朴素转移，发现有很强的阶段性（即i从i-1转移）。考虑矩阵乘法。
弄清楚矩阵乘法的对应关系，还是很简单的。构造转移矩阵即可。
将f数组映射到A的第一行，再使用快速幂解决\(A·B^k\)即可
// Problem: P4838 P哥破解密码
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4838
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
//
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long
#define pb push_back
#define itn int
#define ps second
#define pf first
#define rd read()
int read()
{
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=1e7+5;
const ull P=137;
const int MOD=19260817;
const int INF=1e18+7;
/*
策略
*/
int f[N][3];
struct math{
int a[3][3];
void init(){
memset(a,0,sizeof a);
}
math operator *(const math b)const{
math r;r.init();
for(int k=0;k<3;k++){
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
(r.a[i][j]+=a[i][k]*b.a[k][j]%MOD)%=MOD;
}
}
}
return r;
}
};
math ksm(math a,int b){
math r=a;
b--;
while(b){
if(b&1){
r=r*a;
}
b>>=1;
a=a*a;
}
cdbg(b);
return r;
}
void solve(){
int n=rd;
math a,b;
a.init();
b.init();
a.a[0][0]=1;
// for(int i=1;i<=n;i++){
// f[i][0]=(f[i-1][0]+f[i-1][1]+f[i-1][2])%MOD;
// f[i][1]=f[i-1][0];
// f[i][2]=f[i-1][1];
// }
b.a[0][0]=b.a[1][0]=b.a[2][0]=b.a[0][1]=b.a[1][2]=1;
// for(int i=1;i<=n;i++){
// a=a*b;
// }
a=a*ksm(b,n);
// cdbg("OK");
cout<<(a.a[0][0]+a.a[0][1]+a.a[0][2])%MOD<<endl;
}
signed main(){
int t=rd;
while(t--){
solve();
}
}
斐波那契公约数¶
题目描述
对于 Fibonacci 数列： \(f_i = \begin{cases} [i = 1] & i \leq 1 \\ f_{i - 1} + f_{i - 2} & i \gt 1 \end{cases}\)
请求出 \(f_n\) 与 \(f_m\) 的最大公约数，即 \(\gcd(f_n, f_m)\)。
- 对于 \(100\%\) 的数据，保证 \(1 \leq n, m \leq 10^9\)。
重要结论：gcd(F[n],F[m])=F[gcd(n,m)]
推导：
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=105,MOD=1e8;
int n,K;
struct node {
int a[5][5];
node() {
memset(a,0,sizeof a); //一定要写！
}
};
node f(node a,node b) {
node x;
for(int K=1; K<=2; K++)
for(int i=1; i<=2; i++) {
for(int j=1; j<=2; j++)x.a[i][j]=(x.a[i][j]+a.a[i][K]*b.a[K][j]%MOD)%MOD;
}
return x;
}
node ksm() {
node res,c;
for(int i=1; i<=2; i++)res.a[i][i]=1;
c.a[1][1]=c.a[1][2]=c.a[2][1]=1;
while(K) {
if(K&1) {
res=f(res,c);
}
c=f(c,c);
K>>=1;
}
return res;
}
signed main() {
int n,m;
cin>>n>>m;
K=__gcd(n,m);
if(K<=2){
cout<<1<<endl;
return 0;
}
node res;
res=ksm();
cout<<res.a[2][1]<<endl;
return 0;
}
广义斐波那契¶
（矩阵快速幂的通用递推式推导|对于有初始值及类斐波那契数列的变种）
P1349 广义斐波那契数列
广义的斐波那契数列是指形如 \(a_n=p\times a_{n-1}+q\times a_{n-2}\) 的数列。
今给定数列的两系数 \(p\) 和 \(q\)，以及数列的最前两项 \(a_1\) 和 $ a_2$，另给出两个整数 \(n\) 和 \(m\)，试求数列的第 \(n\) 项 \(a_n\) 对 \(m\) 取模后的结果。
输入包含一行六个整数，\(p,q,a_1,a_2,n,m\)。
输出包含一行一个整数表示答案。
【数据范围】 对于 \(100\%\) 的数据，\(p,q,a_1,a_2 \in [0,2^{31}-1]\)，\(1\le n,m \le 2^{31}-1\)。
/*
Code by Ntsc_Hodaka
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define pii pair<int, int>
///----///
#define rd read()
inline int read() {
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
inline void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
///----///
const int N = 2e2 + 5;
const int M = 1e7 + 5;
const int INF = 1e12 + 5;
int MOD = 998244353;
const double eps = 1e-7;
int n, p, q, a1, a2;
struct node {
int m[10][10];
} ans, base;
inline void init() {
ans.m[1][1] = a2, ans.m[1][2] = a1;
base.m[1][1] = p, base.m[2][1] = q, base.m[1][2] = 1;
}
inline node mul(node a, node b) {
node res;
memset(res.m, 0, sizeof(res.m));
for (int i = 1; i <= 2; i++) {
for (int j = 1; j <= 2; j++) {
for (int k = 1; k <= 2; k++) {
res.m[i][j] += (a.m[i][k] % MOD) * (b.m[k][j] % MOD);
res.m[i][j] %= MOD;
}
}
}
return res;
}
inline void ksm(int p) {
while (p) {
if (p & 1)
ans = mul(ans, base);
base = mul(base, base);
p >>= 1;
}
}
signed main() {
p = rd, q = rd, a1 = rd, a2 = rd, n = rd, MOD = rd;
if (n == 1) {
cout << a1;
return 0;
}
if (n == 2) {
cout << a2;
return 0;
}
init();
ksm(n - 2);
// cerr<<"OK";
printf("%lld", ans.m[1][1] % MOD);
}