《P3216 [HNOI2011] 数学作业》

题目描述

小 C 数学成绩优异，于是老师给小 C 留了一道非常难的数学作业题：

给定正整数 n,m，要求计算 Concatenate(n)mod m 的值，其中 Concatenate(n) 是将 1∼n 所有正整数 顺序连接起来得到的数。

例如，n=13，Concatenate(n)=12345678910111213。小 C 想了大半天终于意识到这是一道不可能手算出来的题目，于是他只好向你求助，希望你能编写一个程序帮他解决这个问题。

输入格式

一行两个正整数 n,m。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1复制

13 13

输出 #1复制

4

说明/提示

【数据范围】

对于 30% 的数据，1≤n≤106；
对于 100% 的数据，1≤n≤1018，1≤m≤109。

• 2023.4.20 添加一组 hack 数据。

代码实现：

#include<iostream> #include<cstring> using namespace std; unsigned long long n, mod, pow10[20]; struct mat { int m[105][105] = {}; mat() {memset(m,0,sizeof(m));} mat operator * (const mat b) { mat res; for(int i = 1;i <= 3;i++) for(int j = 1;j <= 3;j++) for(int k = 1;k <= 3;k++) { res.m[i][j] += 1ll * m[i][k] * b.m[k][j] % mod; res.m[i][j] %= mod; } return res; } void output() { for(int i = 1;i <= 3;i++) { for(int j = 1;j <= 3;j++) printf("%lld ",m[i][j]); printf("\n"); } } }; mat qpow(mat x, long long b) { mat res; for(int i = 1;i <= 3;i++) res.m[i][i] = 1; while(b) { if(b&1) res = res * x; x = x * x; b >>= 1; } return res; } int cnt_dig(long long x) { int cnt = 0; while(x) { cnt++; x /= 10; } return cnt; } int main() { pow10[0] = 1; for(int i = 1;i < 20;i++) pow10[i] = pow10[i-1] * 10ll; scanf("%lld%lld",&n,&mod); mat trans, res; for(int i = 1;i <= 3;i++) res.m[i][i] = 1; for(int i = 1;i <= cnt_dig(n);i++) { trans.m[1][2] = trans.m[2][2] = trans.m[2][3] = trans.m[3][3] = 1; trans.m[1][1] = pow10[i] % mod; if(i == 1) res = res * qpow(trans, min(n-pow10[i-1], pow10[i]-pow10[i-1]-1)); else res = qpow(trans, min(n-pow10[i-1]+1, pow10[i]-pow10[i-1])) * res; } printf("%lld",(res.m[1][1] + 2ll * res.m[1][2] + res.m[1][3]) % mod); return 0; }