填坑……链接：http://cogs.pro/cogs/problem/problem.php?pid=1277
题意：求出数列$f(x)=f(x-1)*10^{lg(x)}+x$的第$n$项。
我真的不知道怎么玩了……这个该死的$lg(x)$卡死了我……最后不得不把我的手伸向了黄学长博客……最后震惊了……
这两个矩阵就是需要的……然后对于每一个$k$都求一遍就行了……
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 long long n,m; 7 struct matrix 8 { 9 long long a[4][4]; 10 matrix(){clear();} 11 void clear(){memset(a,0,sizeof(a));} 12 matrix operator *(const matrix &b)const 13 { 14 matrix c; 15 for(int i=1;i<=3;i++) 16 for(int j=1;j<=3;j++) 17 for(int k=1;k<=3;k++)c.a[i][j]=(c.a[i][j]+(a[i][k]%m)*(b.a[k][j]%m))%m; 18 return c; 19 } 20 }mmm,ans; 21 void calc(long long val,long long tim) 22 { 23 mmm.clear(); 24 mmm.a[1][1]=val; 25 mmm.a[1][2]=mmm.a[2][2]=mmm.a[1][3]=mmm.a[3][3]=mmm.a[2][3]=1; 26 for(long long y=tim-val/10+1;y;y>>=1,mmm=mmm*mmm) 27 if(y&1)ans=mmm*ans; 28 } 29 int haha() 30 { 31 freopen("mathwork.in","r",stdin); 32 freopen("mathwork.out","w",stdout); 33 scanf("%lld%lld",&n,&m); 34 for(int i=1;i<=3;i++)ans.a[i][i]=1; 35 long long t=10; 36 while(n>=t)calc(t,t-1),t*=10; 37 calc(t,n); 38 printf("%lld ",ans.a[1][3]); 39 } 40 int sb=haha(); 41 int main(){;}