Gym 100187B - A Lot of Joy

Two boys Gena and Petya wrote on two strips of paper the same string s that consisted of lowercase Latin letters. Theneach boy took one strip, cut it into small pieces so that each piece containedexactly one letter and put all pieces into his pocket. After that Gena andPetya repeated the following procedure until their pockets became empty: theytook one piece from their pockets and rejoiced if the letters on these pieceswere equal.

Determine the expected number of times the boys rejoiced during thisprocess.

Input

The input contains the only string s which was initially written on Gena's and Petya's strips. The string haslength between 1 and200000, inclusively, and consists of lowercase Latin letters.

Output

Output the only real number — theexpected number of times Gena and Petya rejoiced during their business. Theabsolute or relative error of the answer should not exceed 10 - 9.

Sample test(s)

input

abc

output

1.000000000000000

input

zzz

output

3.000000000000000

思路：

看成數學期望求即可

代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 200005;

#define rep(i,x,y) for (i=x;i<=y;i++)

int main()
{
	char st[N];

	scanf("%s", st);

	int len = strlen(st), i;

	sort(st, st + len);

	char c = st[0];
	double ans = 0;
	int count = 1;
	rep(i, 1, len)
	{
		if (st[i] == st[i - 1])
			count++;
		else
		{
			ans += (double)count*count;
			count = 1;
		}
	}

	printf("%.15lf\n", ans / len);
	return 0;
}