《P3216 [HNOI2011] 数学作业》

题目描述小 C 数学成绩优异于是老师给小 C 留了一道非常难的数学作业题给定正整数 n,m要求计算 Concatenate(n)mod m 的值其中 Concatenate(n) 是将 1∼n 所有正整数 顺序连接起来得到的数。例如n13Concatenate(n)12345678910111213。小 C 想了大半天终于意识到这是一道不可能手算出来的题目于是他只好向你求助希望你能编写一个程序帮他解决这个问题。输入格式一行两个正整数 n,m。输出格式输出一行一个整数表示答案。输入输出样例输入 #1复制13 13输出 #1复制4说明/提示【数据范围】对于 30% 的数据1≤n≤106对于 100% 的数据1≤n≤10181≤m≤109。2023.4.20 添加一组 hack 数据。代码实现#includeiostream #includecstring 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(b1) 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; }