#include #include #include using namespace std; // 575 int main() { string S; cin >> S; if (S.size() > 100000) { cout << "No Judge" << endl; return 0; } static int dp[100001], use[26]; int64_t sum = 0; for (int i = 0;i < 26;++ i) use[i] = -1; dp[0] = 0; for (int i = 0;i < S.size();use[S[i] - 'a'] = i, ++ i) sum += dp[i + 1] = dp[i] + i - use[S[i] - 'a']; cout << setprecision(3) << fixed << sum * 2.0 / S.size() / (S.size() + 1) << endl; return 0; } /* 31536000のコメント解説欄 ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー dp[i]を第i番目の文字を最後とする部分文字列の文字種類数(の総和)とするよ これはdp[i-1]から見て、これら全部の総和+これらのうち同文字が入ってない文字列の総和+1になるよ これを全て求めたら、最後にdpを合計すれば答えになるね! */