#include #include #include #include #include typedef int32_t i32; typedef int64_t i64; #define ALLOC(size,type) ((type*)calloc((size),sizeof(type))) i32 popcnt (i32 v) { v = (v & 0x55555555) + ((v >> 1) & 0x55555555); v = (v & 0x33333333) + ((v >> 2) & 0x33333333); v = (v & 0x0F0F0F0F) + ((v >> 4) & 0x0F0F0F0F); v = (v & 0x00FF00FF) + ((v >> 8) & 0x00FF00FF); return (v & 0x0000FFFF) + (v >> 16); } typedef struct count_val { i32 cnt; i32 val; } node; void run (void) { char *s = ALLOC (1000000 + 1, char); scanf ("%s", s); const i32 n = strlen (s); node *p = ALLOC (26, node); i32 len = 0; i64 sum = 0; for (i32 i = 0; i < n; ++i) { i32 k = s[i] - 'a'; for (i32 j = 0; j < len; ++j) { p[j].val |= 1 << k; } p[len++] = (node) {1, 1 << k}; i32 nlen = 1; for (i32 j = 1; j < len; ++j) { if (p[j].val == p[nlen - 1].val) { p[nlen - 1].cnt += p[j].cnt; } else { p[nlen++] = p[j]; } } len = nlen; for (i32 j = 0; j < len; ++j) { sum += popcnt (p[j].val) * p[j].cnt; } } double ans = (double) sum / n / (n + 1) * 2; printf ("%.6f\n", ans); } int main (void) { run(); return 0; }