考虑 \(\sum (N_i-mval)^2=\sum {N_i}^2-2\times N_i \times mval+mval^2\),我们用一个 \(tot\) 记录贡献个数,用 \(val\) 记录贡献和,\(ans\) 为每一个贡献的方的和。
由于答案是每一个两两的贡献,我们再定义 \(queue_{a,b,c,t}\) 代表 \(a,b,c\) 这种块的第 \(t\) 个出现的位置存一下。\(match_{a,b,c,t}\) 代表 \(queue_{a,b,c,t}-queue_{a,b,c,t-1}\)。用 \(tail_{a,b,c}\) 代表 \(queue\) 的指针。
首先 \(queue_{a,b,c,t}\) 和 \(match_{a,b,c,t}\) 的转移十分的显然。
但是仅仅这样是不够的,我们设 \(sum_{a,b,c}\) 代表这种块的贡献的后缀和的和。设 \(square_{a,b,c}\) 代表这种块的贡献的后缀和后的每一个数的平方的和。
比如:
\(tail_{a,b,c}=\) 3
\(queue_{a,b,c}=\) i | j | k
\(match_{a,b,c}=\) x | y 或者说 j-i | k-j
\(sum_{a,b,c}=\) x+2*y (x+y | y)
\(square_{a,b,c}=\) (x+y)^2+y^2
现在我们来看一下答案的更新。(我们用 \(X\) 代表 \(tail_{a,b,c}-1\),\(tmp\) 代表 \(match_{a,b,c}\))
\[tot+=X\]
\[val+=sum_{a,b,c}\]
\[ans+=square_{a,b,c}+2 \times tmp*sum_{a,b,c}+X*tmp^2\]
更新的时候也很简单
\[square_{a,b,c}+=tmp^2*X+2 \times tmp*sum_{a,b,c}\]
\[sum+=tmp*X\]
神奇 \(60\) 分,公式没有问题...
Const total=100010;var match,queue:array[1..4,1..4,1..4,-1..total] of longint; sum,tail,square:array[1..4,1..4,1..4] of longint; num:array[-1..total] of longint; i,j,k,n,m,a,b,c,tmp,test:longint; val,tot,ans:int64; exist:boolean; s:ansistring;// match 表示上一个与此相同的字符串的位置差,queue 表示与此字符串相同的位置集合// sum 表示 match 的后缀和的和,square 为 match 的后缀和的平方和// tot 为个数,val 是和,ans 为平方和procedure Work;var len:longint;begin fillchar(square,sizeof(square),0); fillchar(queue,sizeof(queue),0); fillchar(match,sizeof(match),0); fillchar(tail,sizeof(tail),0); fillchar(sum,sizeof(sum),0); fillchar(num,sizeof(num),0); readln(s); len:=length(s); ans:=0; tot:=0; val:=0; exist:=True; for i:=1 to len do Case s[i] of 'A' : num[i]:=1; 'G' : num[i]:=2; 'C' : num[i]:=3; 'T' : num[i]:=4; end; for i:=1 to len-2 do begin a:=num[i]; b:=num[i+1]; c:=num[i+2]; inc(tail[a,b,c]); queue[a,b,c,tail[a,b,c]]:=i; if tail[a,b,c]=1 then continue; match[a,b,c,tail[a,b,c]]:=i-queue[a,b,c,tail[a,b,c]-1]+1; tmp:=match[a,b,c,tail[a,b,c]]; dec(tail[a,b,c]); inc(ans,square[a,b,c]+tmp*(sum[a,b,c] << 1)+tail[a,b,c]*sqr(tmp)); inc(square[a,b,c],sqr(tmp)*tail[a,b,c]+tmp*(sum[a,b,c] << 1)); inc(sum[a,b,c],tmp*tail[a,b,c]); inc(val,sum[a,b,c]); inc(tot,tail[a,b,c]); inc(tail[a,b,c]); end; for i:=1 to 4 do for j:=1 to 4 do for k:=1 to 4 do if tail[i,j,k]>1 then exist:=False; if exist then begin writeln('0.000000'); exit; end; writeln(ans,' ',val,' ',tot); writeln(ans/tot-sqr(val/tot):0:6);end;begin {assign(input,'tri.in');reset(input); assign(output,'tri.out');rewrite(output);} readln(test); while test>0 do begin Work; dec(test); end; close(input); close(output);end.