bzoj2326 [HNOI2011]数学作业

Description

正解：DP+矩阵快速幂。

这道题，我们可以写出递推方程：$f[i]=f[i-1]*10^{k}+i$，然后我们可以画出$3*3$的初始矩阵和转移矩阵。

初始矩阵：

$f[n]$ $n$ 1

0 0 0

转移矩阵：

$10^{k}$ 0 0

1 1 0

1 1 1

然后我们按照位数分段进行矩阵快速幂，这道题就能成功解决了。

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <complex>
 5 #include <cstring>
 6 #include <cstdlib>
 7 #include <cstdio>
 8 #include <vector>
 9 #include <cmath>
10 #include <queue>
11 #include <stack>
12 #include <map>
13 #include <set>
14 #define inf (1<<30)
15 #define il inline
16 #define RG register
17 #define ll long long
18 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
19 
20 using namespace std;
21 
22 ll bin[22],di[22],n,k;
23 
24 struct data{ ll m[4][4]; }ans,a;
25 
26 il ll gi(){
27     RG ll x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
28     if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;
29 }
30 
31 il data mul(RG data a,RG data b){
32     RG data c;
33     for (RG int i=1;i<=3;++i)
34     for (RG int j=1;j<=3;++j){
35         c.m[i][j]=0;
36         for (RG int p=1;p<=3;++p)
37         (c.m[i][j]+=a.m[i][p]*b.m[p][j])%=k;
38     }
39     return c;
40 }
41 
42 il data qpow(RG data a,RG ll b){
43     RG data ans=a; b--;
44     while (b){
45     if (b&1) ans=mul(ans,a);
46     a=mul(a,a),b>>=1;
47     }
48     return ans;
49 }
50 
51 il void work(){
52     n=gi(),k=gi(),bin[0]=1,ans.m[1][3]=1;
53     for (RG int i=1;i<=18;++i) bin[i]=bin[i-1]*10%k,di[i]=di[i-1]*10+9;
54     for (RG int i=1;i<=18;++i){
55     memset(a.m,0,sizeof(a.m));
56     a.m[1][1]=bin[i],a.m[2][1]=a.m[2][2]=1;
57     for (RG int j=1;j<=3;++j) a.m[3][j]=1;
58     if (n>=di[i]) a=qpow(a,di[i]-di[i-1]);
59     else a=qpow(a,n-di[i-1]);
60     ans=mul(ans,a); if (n<=di[i]) break;
61     }
62     printf("%lld",ans.m[1][1]); return;
63 }
64 
65 int main(){
66     File("homework");
67     work();
68     return 0;
69 }