1.luogu P3216 [HNOI2011]数学作业
前言：
这sb题我竟然写了一下午，我TCL。
细节有点多，再加上我对矩阵快速幂的板子不熟，调了很长时间。
解析：
首先可以发现一个事情，不考虑进位的话，每次在末尾加一个数，相当于原数乘(10^k)再加上(i) ;
转移矩阵如下：（因为我Markdown太菜了不会打矩阵，就用这位大佬的题解里面的图了）
显然可以矩阵快速幂，因为每次的初始矩阵不一样，只要分段求就行了。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int maxn=100000+10,N=3;
#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
#define read() ({ register int x = 0, f = 1; register char c = gc(); while(c < '0' || c > '9') { if (c == '-') f = -1; c = gc();} while(c >= '0' && c <= '9') x = x * 10 + (c & 15), c = gc(); f * x; })
char buf[1 << 20], *p1, *p2;
ll ans,n,mod;
struct Matrix{
ll c[5][5];
}A;
ll mul(ll x,ll y){
ll res=0;
ll base=x;
while(y){
if(y&1) res=(res+base)%mod;
base=(base+base)%mod;
y>>=1;
}
return res;
}
Matrix operator *(const Matrix &x,const Matrix &y){
Matrix a;
memset(a.c,0,sizeof(a.c));
for(int i=1;i<=N;++i){
for(int j=1;j<=N;++j){
for(int k=1;k<=N;++k){
a.c[i][j]=(a.c[i][j]+mul(x.c[i][k],y.c[k][j]))%mod;
}
}
}
return a;
}
ll qpow(ll x,ll y){
ll res=1;
ll base=x;
while(y){
if(y&1) res=mul(res,base);
base=mul(base,base);
y>>=1;
}
return res;
}
void clear(Matrix &s,int l){
memset(s.c,0,sizeof(s.c));
s.c[1][1]=qpow(1ll*10,l);
s.c[1][2]=s.c[2][2]=s.c[2][3]=s.c[3][3]=1;
}
Matrix qp(ll x){
Matrix s;
memset(s.c,0,sizeof(s.c));
for(int i=1;i<=N;++i) s.c[i][i]=1;
while(x){
if(x&1) s=A*s;
A=A*A;
x>>=1;
}
return s;
}
void Solve1(){
ans= n ? 1 : 0 ;
for(int i=2;i<=n;++i) ans=ans*10+i;
printf("%llu",ans%mod);
}
void Solve(){
scanf("%lld%lld",&n,&mod);
if(n<10){
Solve1();
return;
}
ans=123456789%mod;
ll now=99,len=2,last=10;
while(now<n){
clear(A,len);
Matrix ccc=qp(now-last);
ans=(mul(ans,qpow(10,len))+last)%mod;
ans=(mul(ccc.c[1][1],ans)+mul(ccc.c[1][2],(last+1))+ccc.c[1][3])%mod;
last=now+1;
now=now*10+9;
len++;
}
clear(A,len);
Matrix ccc=qp(n-last);
ans=(mul(ans,qpow(10,len))+last)%mod;
ans=(mul(ccc.c[1][1],ans)+mul(ccc.c[1][2],(last+1))+ccc.c[1][3])%mod;
printf("%llu",ans);
}
int main(){
freopen("le.in","r",stdin);
freopen("le.out","w",stdout);
Solve();
return 0;
}
2.luogu P1349 广义斐波那契数列
前言：
第一次接触矩阵快速幂，应该就是fibonacci数列了吧。
然而我还是调了好长时间,WTCL
解析：
转移矩阵：
没啥可说的，调了半小时发现自己初始矩阵写错了。。。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int n=2,maxn=4;
ll k,a1,a2,mod,p,q;
struct Matrix{
ll c[maxn][maxn];
}A;
Matrix operator*(const Matrix &x,const Matrix &y){
Matrix a;
memset(a.c,0,sizeof(a.c));
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
for(int k=1;k<=n;++k){
a.c[i][j]=(a.c[i][j]+x.c[i][k]*y.c[k][j]%mod)%mod;
}
}
}
return a;
}
Matrix qpow(){
Matrix s;
memset(s.c,0,sizeof(s.c));
for(int i=1;i<=n;++i) s.c[i][i]=1;
while(k){
if(k&1) s=s*A;
A=A*A;
k>>=1;
}
return s;
}
void Solve(){
scanf("%lld%lld%lld%lld%lld%lld",&p,&q,&a1,&a2,&k,&mod);
if(k==1) {
printf("%lld
",a1);
return;
}
if(k==2){
printf("%lld
",a2);
return;
}
k-=2;
memset(A.c,0,sizeof(A.c));
A.c[1][1]=p;
A.c[1][2]=q;
A.c[2][1]=1;
Matrix ans=qpow();
printf("%lld
",(ans.c[1][1]*a2%mod+ans.c[1][2]*a1%mod)%mod);
}
int main(){
// freopen("in","r",stdin);
// freopen("out","w",stdout);
Solve();
return 0;
}