Description
三核苷酸是组成DNA序列的基本片段。具体来说，核苷酸一共有4种，分别用’A’，’G’，’C’，’T’来表示。而三核苷酸就是由3个核苷酸排列而成的DNA片段。三核苷酸一共有64种，分别是’AAA’，’AAG’，…，’GGG’。给定一个长度为L的DNA序列，一共可以分辨出（L-2）个三核苷酸。现在我们想用一些统计学的方法来进行一些分析，步骤如下：
1.对于这（L-2）个三核苷酸，我们从左到右给予编号，分别为1到L-2。
2.从这（L-2）个三核苷酸挑选一对出来，一共有(L-2)*(L-3)/2种可能。如果某一对三核苷酸是一样的，我们就记录他们之间的距离。他们之间的距离定义为他们的编号之差。
3.根据我们所记录的“样本数据”，我们现在需要计算样本数据的方差。方差的计算公式是S2=[(x1-X) 2+(x2-X) 2+…+(xn-X)2]/n, X=(x1+x2+…+xn)/n。如果样本的大小n=0，那么我们认为S2=X=0。
例如，我们要统计DNA序列’ATATATA’：
- 为三核苷酸编号. L1: ATA, L2:TAT, L3:ATA, L4:TAT, L5:ATA.
- (L1,L3)=2, (L1,L5)=4, (L3,L5)=2, (L2,L4)=2. 所以样本数据是2,4,2,2.
- 样本数据平均值X=(2+4+2+2)/4=2.5.
方差S2=[(2-2.5)2+(4-2.5) 2+(2-2.5)2+(2-2.5)2]/4=0.75.
给定一个DNA序列，请你计算出它的方差。
Input
输入包含多组测试数据。第一行包含一个正整数T，表示测试数据数目。每组数据包含一个由’A’，’G’，’C’，’T’组成的字符串，代表要统计的DNA序列。DNA序列的长度大于等于3且不会超过100000。
Output
对每组测试数据，输出一行答案，为一个保留6位精度的实数，代表S2的值。如果你的答案和标准答案的“相对误差”小于1e-8，你的答案会被视为正确的答案。
Sample Input
1
ATATATA
Sample Output
0.750000
.
.
.
.
.
.
程序：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
freopen("tri.in","r",stdin);
freopen("tri.out","w",stdout);
int t;
scanf("%d",&t);
while (t--)
{
int a[100005],b[100005];
char c[100005];
long long s[505],sum[505],cnt[505],s1[505],s2[505];
scanf("%s",c+1);
int n=strlen(c+1);
for (int i=111;i<=444;i++)
s[i]=sum[i]=s1[i]=s2[i]=cnt[i]=0;
for (int i=1;i<=n;i++)
{
if (c[i]=='A') a[i]=1; else
if (c[i]=='G') a[i]=2; else
if (c[i]=='C') a[i]=3; else a[i]=4;
}
for (int i=1;i<=n-2;i++)
b[i]=a[i]*100+a[i+1]*10+a[i+2];
for (int i=1;i<=n-2;i++)
{
s[b[i]]+=cnt[b[i]]*i*i+s1[b[i]]-s2[b[i]]*i*2;
sum[b[i]]+=cnt[b[i]]*i-s2[b[i]];
s1[b[i]]+=(long long)i*i;
s2[b[i]]+=i;
cnt[b[i]]++;
}
long long ans1=0,w=0,x=0;
double ans=0;
for (int i=111;i<=444;i++)
{
ans1+=s[i];
w+=sum[i];
x+=cnt[i]*(cnt[i]-1)/2;
}
if (x==0) ans=0; else ans=1.0*ans1/x-(1.0*w/x)*(1.0*w/x);
printf("%.6f
",ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}