P3216 题解
robertuu
·
·
题解
题目传送门
构造出答案矩阵：
$$ \begin{bmatrix}
ans_{i-1} \\
i \\
1 \\
\end{bmatrix} $$
构造出转移矩阵：
$$ \begin{bmatrix}
10^x&1&0 \\
0&1&1 \\
0&0&1 \\
\end{bmatrix} $$
其中 $x$ 是这一步对应 $i$ 的数位数。
会发现 $x$ 会随着 $i$ 改变，因此不能一次快速幂解决，需要按数位进行分类，对于每一类单独构建转移矩阵，快速幂之后和之前的结果相乘，快速幂的幂次是 $\min(n-10^{x-1}+1,10^x-10^{x-1})$，也就是这一层进行转移的次数（需要注意，由于初始状态不需要进行转移，一位数的时候需要额外减 $1$）。
#### 注意！顺序很重要，需要先快速幂再去乘原来的答案！
代码：
```cpp
#include<iostream>
#include<cstring>
using namespace std;
unsigned long long n,m,p10[20];
struct matrix
{
int a[105][105] = {};
matrix() {memset(a,0,sizeof(a));}
matrix operator * (const matrix b)
{
matrix c;
for(int i = 1;i <= 3;i++)
for(int j = 1;j <= 3;j++)
for(int k = 1;k <= 3;k++)
{
c.a[i][j] += 1ll * a[i][k] * b.a[k][j] % m;
c.a[i][j] %= m;
}
return c;
}
void output()
{
for(int i = 1;i <= 3;i++)
{
for(int j = 1;j <= 3;j++)
printf("%lld ",a[i][j]);
printf("\n");
}
}
};
matrix pow(matrix x,long long b)
{
matrix ans;
for(int i = 1;i <= 3;i++) ans.a[i][i] = 1;
while(b)
{
if(b&1) ans = ans * x;
x = x * x;
b >>= 1;
}
return ans;
}
int digits(long long x)
{
int cnt = 0;
while(x)
{
cnt++;
x /= 10;
}
return cnt;
}
int main()
{
p10[0] = 1;
for(int i = 1;i < 20;i++)
p10[i] = p10[i-1] * 10ll;
scanf("%lld%lld",&n,&m);
matrix p,ans;
for(int i = 1;i <= 3;i++) ans.a[i][i] = 1;
for(int i = 1;i <= digits(n);i++)
{
p.a[1][2] = p.a[2][2] = p.a[2][3] = p.a[3][3] = 1;
p.a[1][1] = p10[i] % m;
if(i == 1) ans = ans * pow(p,min(n-p10[i-1],p10[i]-p10[i-1]-1));
else ans = pow(p,min(n-p10[i-1]+1,p10[i]-p10[i-1])) * ans;
}
printf("%lld",(ans.a[1][1] + 2ll * ans.a[1][2] + ans.a[1][3]) % m);
return 0;
}
```