148. Day 4 PB. 配對期望值

配對期望值

題目敘述

對於任兩個字串$s$跟$t$，我們把$f(s,\,t)$定義為$s$在$t$當中出現的次數，例如：

• $f('ab',\;'ababab')=3$
• $f('abab',\;'ababab')=2$
• $f('aa',\;'ababab')=0$

你有$n$個由小寫英文字母組成的字串$s_1,\,s_2\,\,...\, s_n$，當中有些可能會重複出現。
你想要生成一個由小寫英文字母組成、長度為$m$的字串，我們稱之為$T$。
你很好奇如果你隨機生成$T$的話，$\sum_1^n\,f(s_i, T)$的期望值會是多少。

輸入說明

每個檔案當中只包含一筆測試資料，第一行包含兩個正整數$n,\,m\,(n, m\le1000)$
接下來有$n$行，每行包含一個字串$s_i\,(1≤|s_i|≤1000)$，$s_i$由小寫英文字母組成
$\sum_1^n|s_i|≤1000$

輸出說明

對於每筆測試資料輸出一個浮點數，四捨五入到小數點後六位，代表該期望值

範例輸入 1

2 1
a
a

範例輸出 1

0.076923

範例輸入 2

1 2
a

範例輸出 2

0.076923

Judge Setting

run-time limit: 1000 ms
memory limit: 6553500 byte
測資數量: 0