[ZSOI 三核苷酸]求一个特殊的方差

【题目】

Description

　　三核苷酸是组成DNA序列的基本片段。具体来说，核苷酸一共有4种，分别用’A’，’G’，’C’，’T’来表示。而三核苷酸就是由3个核苷酸排列而 成的DNA片段。三核苷酸一共有64种，分别是’AAA’，’AAG’，…，’GGG’。给定一个长度为L的DNA序列，一共可以分辨出（L-2）个三核 苷酸。现在我们想用一些统计学的方法来进行一些分析，步骤如下：

给定一个DNA序列，请你计算出它的方差。

Input

　　输入包含多组测试数据。第一行包含一个正整数T，表示测试数据数目。每组数据包含一个由’A’，’G’，’C’，’T’组成的字符串，代表要统计的 DNA序列。DNA序列的长度大于等于3且不会超过100000。

Output

　　对每组测试数据，输出一行答案，为一个保留6位精度的实数，代表S2的值。如果你的答案和标准答案的“相对误差”小于1e-8，你的答案会被视为正确 的答案。

Sample Input

1
ATATATA

Sample Output

0.750000

【算法分析】
由于只有64种那个XX，所以开一个大小为64的桶，并将之与4进制数对应起来。
然后就是类似dp那样，根据前面的信息，推出新的信息。
【其他】
由于精度过紧，而我又不会用C++的long double类型的scanf读入和printf输出。。。
于是果断Pascal。。。
【CODE】
const
inf=’tri.in’;
ouf=’tri.out’;

var
Tc,n:longint;
p,total:array [0..64] of extended;
num,ss:array [0..64] of extended;
str:ansistring;
a:array [1..200000] of longint;

procedure init;
var
i:longint;
begin
for i:=1 to n do
case str[i] of
‘A’:a[i]:=0;
‘T’:a[i]:=1;
‘G’:a[i]:=2;
‘C’:a[i]:=3;
end;
end;

procedure solve;
var
i,now:longint;
sum,times,pj:extended;
begin
sum:=0; times:=0;
fillchar(num,sizeof(num),0);
fillchar(total,sizeof(total),0);
fillchar(p,sizeof(p),0);
for i:=n-2 downto 1 do
begin
now:=a[i]*4+a[i+1];
now:=now*4+a[i+2];
if p[now]=0 then
begin
total[now]:=1;
p[now]:=i;
num[now]:=0;
end
else
begin
sum:=sum+total[now]*(p[now]-i)+num[now];
times:=times+total[now];

num[now]:=total[now]*(p[now]-i)+num[now];
total[now]:=total[now]+1;
p[now]:=i;
end;
end;
if times=0 then
begin
sum:=0;
writeln(sum:0:6);
exit;
end;
pj:=sum/times;
fillchar(num,sizeof(num),0);
fillchar(total,sizeof(total),0);
fillchar(p,sizeof(p),0);
fillchar(ss,sizeof(ss),0);
sum:=0;
for i:=n-2 downto 1 do
begin
now:=a[i]*4+a[i+1];
now:=now*4+a[i+2];
if (p[now]=0) then
begin
total[now]:=1;
p[now]:=i;
num[now]:=0;
ss[now]:=0;
end
else
begin
num[now]:=num[now]
+sqr(p[now]-i)*(total[now]-1)
+2*ss[now]*(p[now]-i)+sqr(p[now]-i-pj);

ss[now]:=ss[now]
+(total[now]-1)*(p[now]-i)
+p[now]-i-pj;

total[now]:=total[now]+1;

p[now]:=i;

sum:=sum+num[now];
end;
end;
writeln(sum/times:0:6);
end;

procedure main;
var
i:longint;
begin
readln(Tc);
for i:=1 to Tc do
begin
readln(str);
n:=length(str);
init;
solve;
end;
end;

begin
assign(input,inf);
assign(output,ouf);
reset(input);
rewrite(output);
main;
close(input);
close(output);
end.