f[i]表示计算了前i位的值,f[i]=f[i-1]*10^k+i
N太大了，发现是线性常系数递推，要用矩阵来优化，就是10^n+0~10^n+9一起计算
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 typedef long long ll; 7 ll n,mod; 8 struct matrix{ 9 int n,m; 10 ll mat[10][10]; 11 matrix(int n=0,int m=0):n(n),m(m){} 12 void clear(){memset(mat,0,sizeof(mat));} 13 void iden(){ 14 memset(mat,0,sizeof(mat)); 15 for(int i=0;i<n;i++) mat[i][i]=1; 16 } 17 matrix operator*(const matrix b) const{ 18 if(m!=b.n) exit(2); 19 int p=b.m; 20 matrix c(n,b.m); 21 c.clear(); 22 for(int i=0;i<n;i++){ 23 for(int j=0;j<p;j++){ 24 for(int k=0;k<m;k++){ 25 c.mat[i][j]+=mat[i][k]*b.mat[k][j]; 26 c.mat[i][j]%=mod; 27 } 28 } 29 } 30 return c; 31 } 32 matrix operator^(ll p){ 33 matrix ret(n,n),tmp; 34 ret.iden(); 35 for(tmp=*this;p;p>>=1,tmp=tmp*tmp){ 36 if(p&1) ret=ret*tmp; 37 } 38 return ret; 39 } 40 }; 41 char buf[2007]; 42 int main(){ 43 ll n,bit; 44 scanf("%lld%lld",&n,&mod); 45 sprintf(buf,"%lld",n); 46 bit=strlen(buf); 47 matrix ans(1,3); 48 ans.clear(); 49 ans.mat[0][2]=1; 50 for(int i=1;i<=bit;i++){ 51 ll unit=pow(10,i-1); 52 matrix com(3,3); 53 com.clear(); 54 com.mat[0][0]=unit%mod*10%mod; 55 com.mat[1][0]=com.mat[1][1]=com.mat[2][0]=com.mat[2][1]=com.mat[2][2]=1; 56 if(i!=bit) ans=ans*(com^(unit*9));//10^n+0~10^n+9一起计算 57 else ans=ans*(com^(n-unit+1));//到最后逐个计算 58 for(int i=0;i<3;i++) cout<<ans.mat[0][i]<<" "; 59 cout<<endl; 60 } 61 printf("%lld",ans.mat[0][0]);//不能加& 62 return 0; 63 }
return 0是c语言中的保留字,指示程序正常结束,而exit()是一个库函数,后面可以加参数；
exit(0)也可以正常退出，如果加其它的数值：1，2，....可以表示由于不同的错误原因而退出
sprintf(string,"%f",num);
string是一个字符串，num是你要的数字，这样就能将浮点数num转成字符串string了
用矩阵乘法计算斐波那契额数列：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 const ll mod = 19260817; 6 const int N = 2; 7 struct Matrix{ 8 ll a[N][N]; 9 10 void clear(){ 11 memset(a, 0, sizeof(a)); 12 } 13 14 Matrix operator * (const Matrix b) const{ 15 Matrix ret; ret.clear(); 16 for(int i = 0; i < N; i ++){ 17 for(int j = 0; j < N; j ++){ 18 for(int k = 0; k < N; k ++){ 19 ret.a[i][j] = (ret.a[i][j] + a[i][k] * b.a[k][j]) % mod; 20 } 21 } 22 } 23 return ret; 24 } 25 }A, B; 26 27 28 Matrix qpow(Matrix A, ll b){ 29 Matrix ret; ret.clear(); 30 for(int i = 0; i < N; i ++) ret.a[i][i] = 1; 31 for(; b; b >>= 1, A = A * A){ 32 if(b & 1) ret = ret * A; 33 } 34 return ret; 35 } 36 ll n; 37 int main(){ 38 scanf("%lld", &n); 39 A.clear(); A.a[0][0] = A.a[0][1] = A.a[1][0] = 1; 40 B = qpow(A, n - 1); 41 ll ans = 0; 42 cout<<B.a[0][0]<<" "<<B.a[0][1]<<endl; 43 ans = (B.a[0][0] + B.a[0][1]) % mod; 44 printf("%lld ", ans); 45 }