【NOIP2012模拟8.7】字符串函数
Description
两个等长的由大写英文字母构成的字符串a和b，从a中选择连续子串x，从b中选出连续子串y。 定义函数f(x,y)为满足条件xi=yi(1<=i<=|x|)的i的个数，计算f(x,y)的数学期望。(|x|=|y|)
Input
第一行输入n(1<=n<=2*10^5)，表示a和b的长度 第二行输入字符串a 第三行输入字符串b
Output
输出一个实数表示f(x,y)的期望，如果你的答案与正确答案相差不超过10^-6则认为是正确的。(保留6位)
Sample Input
2 AB BA
Sample Output
0.400000
Hint
考虑第一个样例，x,y的选择有5种情况分别是(“A”,“B”),(“A”,“A”),(“B”,“B”),(“B”,“A”),(“AB”,“BA”)其中，第2对和第3对所对应的f(x,y)等于1，其他都是0，由于选择每一对的概率都是1/5，所以f(x,y)的期望为1/50+1/51+1/51+1/50+1/5*0=2/5=0.4
题解
考虑a和b中一个相同的字符的贡献 设(i>j) a[i]=b[j] 贡献是i*sum(j (b[j]==a[i])) 用前缀和和后缀和维护，预处理
code
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define R register
using namespace std
;
const int N
=200100;
int n
,a
[N
],g
[26][N
],f
[26][N
];
long long num
,tot
;
int main(){
scanf("%d",&n
);
char ch
=getchar();
while(!('A'<=ch
&&ch
<='Z'))ch
=getchar();
for(R
int i
=1;i
<=n
;++i
,ch
=getchar())a
[i
]=ch
-'A';
while(!('A'<=ch
&&ch
<='Z'))ch
=getchar();
for(R
int i
=1;i
<=n
;++i
,ch
=getchar())f
[ch
-'A'][i
]+=i
,g
[ch
-'A'][i
]+=n
-i
+1;
for(R
long long i
=1;i
<=n
;++i
)tot
+=i
*i
;
for(R
int i
=0;i
<26;++i
){
for(R
int j
=2;j
<=n
;++j
)f
[i
][j
]+=f
[i
][j
-1];
for(R
int j
=n
-1;j
;--j
)g
[i
][j
]+=g
[i
][j
+1];
}
for(R
long long i
=1;i
<=n
;++i
)num
+=(n
-i
+1)*f
[a
[i
]][i
]+i
*g
[a
[i
]][i
+1];
printf("%.6lf",1.0*num
/tot
);
}
