#10193 「一本通 6.1 例 1」序列的第 k 个数
3A取模的时候记得全局取模……能取的一定要取
#10195 「一本通 6.1 练习 2」转圈游戏
2A,还是上面的问题，对于转圈圈的问题一定要取模！
#10196 「一本通 6.1 练习 3」越狱
1A快速幂专题是来教你怎么取模的………………注意减法的时候要加上模数再取模
- 矩乘的n,m,p枚举顺序随便
#10221 「一本通 6.5 例 3」Fibonacci 前 n 项和
如果要维护线性递推式的每一项的和的话，就多加一维，记录前缀和。
状态定义的话：怎么推着舒服怎么来。
注意矩乘没有交换律，在写柿子的时候要慎重！
but,we have 黑科技：
S(n)=Fib(n+2)-1
int n,mod;
struct Matrix{
int m[4][4];
Matrix(){mem(m,0);}
friend Matrix operator *(Matrix a,Matrix b){
Matrix c;
rep(i,1,3)
rep(k,1,3)
rep(j,1,3)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
return c;
}
friend Matrix operator ^(Matrix a,int k){
Matrix res;
rep(i,1,3)res.m[i][i]=1;
for(;k;k>>=1){
if(k&1)res=res*a;
a=a*a;
}
return res;
}
};
#undef int
int main(){
#define int long long
#ifdef WIN32
freopen("a.txt","r",stdin);
#endif
rd(n),rd(mod);
Matrix base,ans;
ans.m[1][1]=1,ans.m[1][2]=1,ans.m[1][3]=1;//sum[1] f[2] f[1]
base.m[1][1]=1,base.m[1][2]=0,base.m[1][3]=0;
base.m[2][1]=1,base.m[2][2]=1,base.m[2][3]=1;
base.m[3][1]=0,base.m[3][2]=1,base.m[3][3]=0;
base=base^(n-1);
ans=ans*base;
printf("%lld\n",ans.m[1][1]%mod);
return 0;
}P4838 P哥破解密码
首先你得看出这是个线性递推，由上一个状态有多少个A转移而来
范围：1e9的线性递推，那么，上，矩乘！
集合：\(f[i][j]\)表示转移到i位字符串，第i位填了j个A的集合的合法个数。
转移：
f[i][0]=f[i-1][0]+f[i-1][1]+f[i-1][2];//第i位填B的时候可以由上一位填B，A，AA转移而来
f[i][1]=f[i-1][0]//第i位填A的时候可以由上一位填B转移而来
f[i][2]=f[i-1][1]//第i位填AA的时候可以由上一位填A转移而来
/* 转移矩阵：
1 1 0
1 0 1
1 0 0
*/ 终态:f[n][0]+f[n][1]+f[n][2]
初始化：
f[1][0]=1,f[1][1]=1,f[1][2]=0;BTW:求长度为n的字符串的合法个数，那么只需要转移n-1次（因为已经预处理出长度为1的字符串的合法个数）
注意：在base矩阵里面我并没有用到”0“这个角标，以为嫌麻烦。所以所有角标都加上了1的哦
int n;
const int mod=19260817;
struct Matrix {
int m[4][4];
Matrix(){mem(m,0);}
friend Matrix operator *(Matrix a,Matrix b){
Matrix c;
rep(i,1,3)
rep(k,1,3)
rep(j,1,3)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
return c;
}
friend Matrix operator ^(Matrix a,int k){
Matrix res;
rep(i,1,3)res.m[i][i]=1;
for(;k;k>>=1){
if(k&1)res=res*a;
a=a*a;
}
return res;
}
};
#undef int
int main(){
#define int long long
#ifdef WIN32
freopen("a.txt","r",stdin);
#endif
int T;rd(T);
while(T--){
rd(n);
Matrix ans,base;
ans.m[1][1]=1,ans.m[1][2]=1,ans.m[1][3];
base.m[1][1]=1,base.m[1][2]=1,base.m[1][3]=0;
base.m[2][1]=1,base.m[2][2]=0,base.m[2][3]=1;
base.m[3][1]=1,base.m[3][2]=0,base.m[3][3]=0;
base=base^(n-1);
ans=ans*base;
printf("%lld\n",(ans.m[1][1]+ans.m[1][2]+ans.m[1][3])%mod);
}
return 0;
}