HNOI2008 GT 考试

我不明白为什么是DP,我感觉和vijos的核电站问题（https://www.vijos.org/p/1232）差不多啊

这是别人的题解：http://www.cnblogs.com/Skywalker-Q/archive/2011/03/17/1987395.html

 1 type matrix=array[0..30,0..30] of longint;
 2 var n,m,i,j,k,p,sum:longint;
 3     a,ans,zero:matrix;
 4     s,ts:string;
 5     ch:char;
 6 function mul(a,b:matrix):matrix;
 7  var i,j,k:longint;
 8  begin
 9  fillchar(mul,sizeof(mul),0);
10  for i:=0 to m-1 do
11   for j:=0 to m-1 do
12    for k:=0 to m-1 do
13     mul[i,j]:=(mul[i,j]+a[i,k]*b[k,j]) mod p;
14  end;
15 function power(a:matrix;k:longint):matrix;
16  begin
17  power:=zero;
18  while k>0 do
19   begin
20   if k and 1=1 then power:=mul(power,a);
21   a:=mul(a,a);k:=k>>1;
22   end;
23  end;
24 begin
25  readln(n,m,p);
26  readln(s);
27  for j:=0 to m-1 do
28   zero[i,i]:=1;
29  for j:=0 to m-1 do
30   for ch:='0' to '9' do
31    begin
32    ts:=copy(s,1,j)+ch;
33    for k:=j+1 downto 0 do
34     if copy(s,1,k)=copy(ts,j-k+2,k) then break;
35    inc(a[j,k]);
36    end;
37  ans:=power(a,n);
38  for i:=0 to m-1 do sum:=(sum+ans[0,i]) mod p;
39  writeln(sum);
40 end.
41

View Code

等我改一下的我的程序再发上来……