問題一覧 > 通常問題

No.563 超高速一人かるた large

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 : koyumeishikoyumeishi / テスター : PulmnPulmn
1 ProblemId : 777 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-08-24 22:02:25

超高速一人かるた smallの制約大きい版です。
small に large 用の解法を提出することは特に制限しませんが、 large をコンテスト中に解くつもりのある方は、他の方の提出を覗かないようお願いします。

問題文

かるた取りとは $N$ 枚の読み札と $N$ 枚の取り札を使ったゲームです。

  • 読み札 $x$ には文字列 $S_x$ が書かれています。 $S_x \neq S_y (x \neq y)$
  • 読み札 $x$ には対応する取り札 $f(x)$ が一つだけ存在します。
    異なる読み札が同じ取り札に対応することはありません(つまり一対一対応)。 $f(x) \neq f(y) (x \neq y)$

ゲームは次のように進行します。

  1. 読手は $N$ 枚の読み札を持ち、競技者は $N$ 枚の取り札を場に並べます
  2. 読手はまだ読んでいない読み札 $1$ 枚を等確率で選び、書かれている文字列を読み上げます。
  3. 文字列が読み上げられ始めたら、競技者は今読まれている読み札 $x$ を推定し、 場から対応する取り札 $f(x)$ を探して取ります
  4. 読まれていない読み札がまだ残っているなら 2. へ戻ります。 そうでないならゲームは終了です

太郎くんはかるたが得意なので、読み上げられている読み札が一意に定まった瞬間に取り札を取ることができます。 一意に定まらないうちに札を取ることはありません。
しかし大変集中力を要するため、取るまでに読み上げられた文字列長分の疲労度が蓄積されます。 つまり、 $i$ 文字目まで読み上げられた時点で読み札が一意に定まるとき、 $i$ の疲労度が蓄積されます。 ただし、 $i$ 文字目が読み上げられないことで一意に定まるとき、 $i$ 文字目に空文字が読み上げられたとみなして $i$ の疲労度が蓄積されます。 また、残る札が$1$枚であっても、$1$文字目が読み上げられてからでないと札を取ることはできません。

$N$ 枚の読み札の中から $K$ 枚読み上げられたときに蓄積される疲労度の期待値 $E_K$ を計算してください。
ただし、読み上げられ方のパターン数 ${}_N \mathrm{P} _K$ を掛けると丁度整数になるので、 $E_K \times {}_N \mathrm{P} _K \mod 1,000,000,007$ を出力してください。

入力

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

1行目に読み札・取り札の枚数 $N$ 、 続く $N$ 行に読み札 $i$ に書いてある文字列 $S_i$ が与えられます。

制約
$1 \leq N \leq 2000$
$1 \leq |S_i|$
$\sum |S_i| \leq 2 \times 10^5$
$S_i$ は小文字の英アルファベット'a'-'z'のみで構成される

出力

$E_1 \times {}_N \mathrm{P} _1$
$E_2 \times {}_N \mathrm{P} _2$
$\vdots$
$E_N \times {}_N \mathrm{P} _N$

$K$ 行目に $E_K \times {}_N \mathrm{P} _K \mod 1,000,000,007$ を出力してください。

サンプル

サンプル1
入力
3
umr
uma
tsf
出力
7
24
30

3枚中1枚読まれるとき、それぞれ次の強調部が読まれたときに一意に定まります

  • umr 疲労度+3
  • uma 疲労度+3
  • tsf 疲労度+1

それぞれ 1/3 の確率なので、 (3+3+1)/3 * 3 = 7

3枚中2枚読まれるとき、

[1枚目が"umr" 疲労度+3]

  • uma 疲労度+1
  • tsf 疲労度+1

[1枚目が"uma" 疲労度+3]

  • umr 疲労度+1
  • tsf 疲労度+1

[1枚目が"tsf" 疲労度+1]

  • umr 疲労度+3
  • uma 疲労度+3

(4+4+4+4+4+4)/6 * 6 = 24

3枚中3枚読まれるとき、2枚のときに加えて残った1枚を取るときに 疲労度+1
(5+5+5+5+5+5)/6 * 6 = 30

サンプル2
入力
2
a
aa
出力
4
6

"a" だけでは一意に定まりません。 2文字目に"a"が読み上げられるか、 何も読み上げられないかを確認する必要があります。

  • a.
  • aa
サンプル3
入力
12
a
b
c
d
e
f
g
h
i
j
k
l
出力
12
264
3960
47520
475200
3991680
27941760
159667200
718502400
395007986
269017565
748019165

$\mod 1,000,000,007$ をお忘れなく

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。