bzoj2326

首先不难得出递推式f[i]=(f[i-1]*10^k+i) mod m;
f[i]表示接到第i个数时的余数，k表示i的位数
不难想到先按位数穷举位数，然后对于确定的位数，构造矩阵解决
易得出：
f[i] 10^k 1 1 f[i-1]
i = 0 1 1 * i-1
1 0 0 1 1
矩阵乘法优化的特点就是有一维特别的大，且这一阶段的值只和上一阶段有关

 1 var a,b,w,c:array[1..3,1..3] of int64;
 2     f,p:array[1..3] of int64;
 3     d:array[0..100] of longint;
 4     e:array[0..20] of int64;
 5     j,i,l,m:longint;
 6     x,n:int64;
 7 
 8 procedure mul1;
 9   var i,j,k:longint;
10   begin
11     for i:=1 to 3 do
12       for j:=1 to 3 do
13       begin
14         c[i,j]:=0;
15         for k:=1 to 3 do
16           c[i,j]:=(c[i,j]+a[i,k]*b[k,j] mod m) mod m;
17       end;
18   end;
19 
20 procedure mul2;
21   var i,k:longint;
22   begin
23     for i:=1 to 3 do
24     begin
25       f[i]:=0;
26       for k:=1 to 3 do
27         f[i]:=(f[i]+c[i,k]*p[k] mod m) mod m;
28     end;
29   end;
30 
31 
32 procedure quick(x:int64);
33   var i,j:longint;
34   begin
35     j:=0;
36     while x>0 do
37     begin
38       inc(j);
39       d[j]:=x mod 2;
40       x:=x div 2;
41     end;
42     fillchar(c,sizeof(c),0);
43     for i:=1 to 3 do
44       c[i,i]:=1;
45     for i:=j downto 1 do
46     begin
47       a:=c;
48       b:=c;
49       mul1;
50       if d[i]=1 then
51       begin
52         a:=c;
53         b:=w;
54         mul1;
55       end;
56     end;
57   end;
58 
59 begin
60   readln(n,m);
61   e[0]:=1;
62   l:=19;
63   for i:=1 to 18 do
64   begin
65     e[i]:=e[i-1]*10;
66     if e[i]>n then
67     begin
68       l:=i;
69       break;
70     end;
71   end;
72   e[19]:=e[18] mod m*10 mod m;
73   x:=0;
74   w[1,1]:=e[1] mod m;  w[1,2]:=1;  w[1,3]:=1;
75   w[2,1]:=0;  w[2,2]:=1;  w[2,3]:=1;
76   w[3,1]:=0;  w[3,2]:=0;  w[3,3]:=1;
77   f[1]:=1;  f[2]:=1;  f[3]:=1;
78   if l<>1 then x:=8
79   else x:=n-1;
80   p:=f;
81   quick(x);
82   mul2;
83   x:=9;
84   for i:=2 to l do
85   begin
86     p:=f;
87     if i<>l then x:=x*10
88     else x:=n-e[i-1]+1;  //防止爆int64的
89     w[1,1]:=e[i] mod m;
90     quick(x);
91     mul2;
92   end;
93   writeln(f[1]);
94 end.

View Code