BZOJ先剧透了是矩阵乘法...这道题显然可以f(x) = f(x-1)*10t+x ,其中t表示x有多少位。
这个递推式可以变成这样的矩阵...(不会用公式编辑器...), 我们把位数相同的一起处理, 那么10^t就可以确定，加上快速幂就行了
------------------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef int matrix[3][3];
ll N;
int MOD;
matrix mat, Q, tmp;
void Mul(matrix &a, matrix &b) {
memset(tmp, 0, sizeof tmp);
for(int i = 0; i < 3; i++)
for(int k = 0; k < 3; k++)
for(int j = 0; j < 3; j++)
if((tmp[i][j] += ll(a[i][k]) * b[k][j] % MOD) >= MOD)
tmp[i][j] -= MOD;
memcpy(a, tmp, sizeof a);
}
void Power(matrix &a, matrix &b, ll k) {
for(; k; k >>= 1, Mul(b, b))
if(k & 1) Mul(a, b);
}
void Init_matrix() {
memset(mat, 0, sizeof mat);
mat[0][1] = mat[0][2] = mat[1][1] = mat[1][2] = mat[2][2] = 1;
memset(Q, 0, sizeof Q);
for(int i = 0; i < 3; i++)
Q[i][i] = 1;
}
int main() {
scanf("%lld%d", &N, &MOD);
int len = 0, B = 0, C = 0;
ll p = 1;
for(ll t = N; t; t /= 10, len++);
for(int i = 1; i < len; i++) {
Init_matrix();
mat[0][0] = (p = p * 10) % MOD;
Power(Q, mat, p - p / 10);
B = (ll(B) * Q[0][0] % MOD + ll(C) * Q[0][1] % MOD + Q[0][2]) % MOD;
C = ((p % MOD) - 1 + MOD) % MOD;
}
Init_matrix();
mat[0][0] = p * 10 % MOD;
Power(Q, mat, N - p + 1);
B = (ll(B) * Q[0][0] % MOD + ll(C) * Q[0][1] % MOD + Q[0][2]) % MOD;
printf("%d\n", B);
return 0;
}
------------------------------------------------------------------------------------
2326: [HNOI2011]数学作业
Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1452 Solved: 841 [ ][ ][ ]Description
Input
Output
Sample Input
Sample Output
HINT
Source