P3216 [HNOI2011] 数学作业
最编程
2024-04-20 20:10:07
...
题目大意
小\(C\)数学成绩优异,于是老师给小\(C\)留了一道非常难的数学作业题:
给定正整数\(N\)和\(M\),要求计算\(Concatenate (1 .. N)\ Mod\ M\) 的值,其中 \(Concatenate (1 .. N)\)是将所有正整数\(1, 2, …, N\)顺序连接起来得到的数。例如,\(N = 13\), \(Concatenate(1..N)=12345678910111213\)。小\(C\)想了大半天终于意识到这是一道不可能手算出来的题目,于是他只好向你求助,希望你能编写一个程序帮他解决这个问题。
题目分析
显然矩阵快速幂。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull n,m;
struct Mat{
ull a[5][5];
Mat(){memset(a,0,sizeof(a));}
ull*operator[](int x){return a[x];}
void init(){for(int i=0;i<3;i++)a[i][i]=1;}
Mat operator*(Mat b){
Mat c;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)
c[i][j]=(c[i][j]+a[i][k]*b[k][j])%m;
return c;
}
Mat operator^(ull cnt){
Mat ret,mul=*this;ret.init();
for(;cnt;cnt>>=1,mul=mul*mul)if(cnt&1)ret=ret*mul;
return ret;
}
};
int main(){
cin>>n>>m;
ull now=1;
Mat Ans,mul;
Ans[0][0]=0;Ans[0][1]=1;Ans[0][2]=1;
while(1){
mul[0][0]=now*10%m;mul[0][1]=0;mul[0][2]=0;
mul[1][0]=1;mul[1][1]=1;mul[1][2]=0;
mul[2][0]=0;mul[2][1]=1;mul[2][2]=1;
if(now*10<=n){
mul=mul^(now*9);
Ans=Ans*mul;
}
else{
mul=mul^(n-now+1);
Ans=Ans*mul;break;
}
now*=10;
}
cout<<Ans[0][0]%m<<"\n";
}
/*
13 13
12345678910 1000000000
[10^k,0,0]
[num,next,1]*[1 ,1,0]
[0 ,1,1]
*/
推荐阅读
-
P3216 [HNOI2011] 数学作业
-
小明非常喜欢数学,有一次做数学作业时,老师让他计算 9~16 的和,他马上写出了正确答案是 100,但他并不满足于此,他想知道有多少个连续的正数序列的和(至少包括两个数)是 100。-说明
-
纯数学作业 - 第 0 章
-
恼人的数学作业(数字 dp)
-
P5390 [Cnoi2019] 数学作业
-
P3216 [HNOI2011] 数学作业
-
数学假期作业精选
-
小明非常喜欢数学,有一次做数学作业时,老师让他计算 9~16 的和,他马上写出了正确答案 100。但他并不满足于此,他想知道有多少个连续的正数序列的和(至少包括两个数)是 100。-源代码
-
离散数学作业 - 总收藏 - Assignmentday-
-
CSU 计算机数学作业解决方案 III(参考:特定数学)