题意：两个长度相同的字符串，在两个字符串中选取相同长度的子串，所有情况概率相同，问对应位置相同的期望是多少？
题解：暴力方法是求出每一对串，再计算所有的和，O(n*n)，这里期望用贡献来算，算出来每一个字母出现多少次，
比如：AAB和CAA，s1[0]的A可以匹配s2的两个A，也就是AA-AC, A-A这是最长的字符串
可以发现，s1的字符串中的字母A位置为i，s2中小于i位置的字母是决定最长字符串的左侧长度
比如ABC和DCD那么s2中的C在s1中的C的左侧，那么C左侧最长为1，右侧最长为0，答案就是(1+1)*(0+1) = 2，也就是BC-DC,C-C
这里注意会爆long long，要边算边除，而且不能算重复
#include <bits/stdc++.h>#define maxn 00#define INF 0x3f3f3f3ftypedef long long ll;using namespace std;ll cnt[30], l;double ans;char s1[maxn], s2[maxn];int main(){scanf("%lld", &l);double c = l*(l+1)*(2*l+1)/6.0;scanf("%s%s", s1, s2);for(ll i=0;i<l;i++){cnt[s2[i]-'A'] += i+1;ans += (l-i)*cnt[s1[i]-'A']/c;}memset(cnt, 0, sizeof(cnt));for(ll i=l-1;i>=0;i--){ans += (i+1)*cnt[s1[i]-'A']/c;cnt[s2[i]-'A'] += l-i;}printf("%f\n", ans);return 0;}
