| |
|
算法
这是一道典型的动态规划题。
要求有多少个包含指定的排列，实际上就是求有多少个串不包含给定排列，再用 减去即可。
设指定排列为S，长度为l。
令f(i,j)表示符合下列两个条件的串P的数目。
1） P的长度为i。
2）  ，且j是满足该式最大的一个。
显然，长度为n、不包含给定排列的串的数目就是f(n,0)+f(n,1)+……+f(n,l-1)。
采用顺推的形式实现动态规划。如果已经算出f(i,j)的结果，
1） 第i+1位为 。将f(i,j)的结果累加到f(i+1,j+1)。
2） 第i+1位不为。将f(i,j)的结果累加到f(i+1,k)，k为添加1-所到达的状态（用循环或者Kmp实现）。
参考程序
{$R-,S-,Q-}
const
fin = 'contest.in';
fout = 'contest.out';
base = 10000;
maxn = 2000;
var
l, n : integer;
s : array[0 .. maxn] of char;
next : array[0 .. maxn] of integer;
i, j : integer;
f, old : array[0 .. maxn] of integer;
result : integer;
md: array[0 .. base shl 1] of integer;
begin
for i := 0 to base shl 1 do
md[i] := i mod base;
assign(input, fin); reset(input);
readln(n);
l := 0;
while not seekeof do begin
inc(l); read(s[l]);
end;
close(input);
next[1] := 0;
i := 1; j := 0;
while i < l do
if (j = 0) or (s[i] = s[j]) then begin
inc(i); inc(j);
if s[i] = s[j] then next[i] := next[j] else next[i] := j;
end else j := next[j];
f[0] := 1;
for i := 0 to n - 1 do begin
old := f;
move(f[0], f[1], (l - 1) * sizeof(f[0]));
f[0] := 0;
for j := 0 to l - 1 do
f[next[j + 1]] := md[f[next[j + 1]] + old[j]];
end;
assign(output, fout); rewrite(output);
result := 1;
for i := 1 to n do result := result * 2 mod base;
for i := 0 to l - 1 do
result := (result - f[i] + base) mod base;
writeln(result);
close(output);
end.
|
|
|
