最近学了矩阵，kzj大佬推荐了我这一道题目。
乍一眼看上去，没看出是矩阵，就随便打了一个暴力，30分。
然后仔细分析了一波，发现蛮简单的。
结果全wa了，先看看下面的错误分析吧！
首先，设f[n]为最终答案，易得出$$ f[n]=f[n-1]*10+n$$
然后魔改一下：$$ f[n]=f[n-1]*10+n-1 => $$
\[\begin{matrix}
10&0&0\\
1&1&0\\
1&1&1\\
\end{matrix}\]
10&0&0\\
1&1&0\\
1&1&1\\
\end{matrix}\]
信心一波过样例提交，0分。
心态炸了，仔细想了想，原来这个矩阵是会变化的。
假设n的位数为k。
\[f[n]=f[n-1]*10^k+n-1$$ 这才是正确的递推公式。
所以矩阵也要改为：
$$\begin{matrix}
10^k&0&0\\
1&1&0\\
1&1&1\\
\end{matrix}\]
那么，矩阵会成长，怎么做呢，
我们可以分开处理，初始矩阵 \(f[0] => (0,0,1)\)
从1枚举位数，一直到\(length(n)-1\)位，一直乘\(10^k\)的矩阵\(9*10^{k-1}\)次。
最后处理\(length(n)\)位，乘以\(10^{length(n)}\)矩阵\(n-\sum_{k=1}^{length(n)}(9*10^{k-1})\)次。
献上巨弱的丑代码吧～
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int K=0;
ull n,m,len,p,tot;
ull f[]={0,0,0,1},t[4][4];
ull suan(ull,ull);
void fuyan();
void yuzhouzhou();
ull getpow(ull,ull);
string work();
string w=work();
int main() {;;;;;;;;;;;;;;;;;;}
ull suan(ull x,ull y)
{
ull d=0;
while (y) {
if (y&1) d=(d%m+x%m)%m;
x=(x%m+x%m)%m,y>>=1;
}
return d%m;
}
void fuyan()
{
ull d[4];
memcpy(d,f,sizeof(d));
memset(f,0,sizeof(f));
for (int i=1;i<=3;++i)
for (int j=1;j<=3;++j)
f[i]=(f[i]%m+suan(d[j]%m,t[j][i]%m))%m;
}
void yuzhouzhou()
{
ull d[4][4];
memcpy(d,t,sizeof(d));
memset(t,0,sizeof(t));
for (int i=1;i<=3;++i)
for (int j=1;j<=3;++j)
for (int k=1;k<=3;++k)
t[i][j]=(t[i][j]%m+suan(d[i][k]%m,d[k][j]%m))%m;
}
ull getpow(ull x,ull y)
{
ull d=x;
for (int i=1;i<y;++i) d*=10;
return d;
}
string work()
{
cin>>n>>m;
p=n;
while (p) ++len,p/=10;
for (int i=1;i<len;++i) {
p=getpow(9,i);
tot+=p;
t[1][1]=getpow(10,i);
t[1][2]=t[1][3]=t[2][3]=0;
t[2][1]=t[2][2]=t[3][1]=t[3][2]=t[3][3]=1;
while (p) {
if (p&1) fuyan();
yuzhouzhou(),p>>=1;
}
}
p=n-tot;
t[1][1]=getpow(10,len);
t[1][2]=t[1][3]=t[2][3]=0;
t[2][1]=t[2][2]=t[3][1]=t[3][2]=t[3][3]=1;
while (p) {
if (p&1) fuyan();
yuzhouzhou(),p>>=1;
}
cout<<f[1];
return "You succeeded,boy!";
}