Background

In Gensokyo, Motoori Kosuzu not only often gets bumped into by others, but also has to organize the books in Suzunaan. She has many troubles.

Problem Description

Kosuzu organizes the books in Suzunaan once every day. This time there are $n$ magic books on the table, placed in a row. Each book has a magic attribute and an index.

At the beginning, all books had the same magic attribute. However, after being used many times, their magic attributes changed. Kosuzu wants all books to have the same magic attribute again.

This time Kosuzu asks Kirisame Marisa for help. Each time, Marisa can cast a chosen spell, and the spell will randomly choose two books $a,b$ (where $a$ is not equal to $b$).

After these two books are chosen, Marisa casts a transfer spell: with probability $p_{a,b}\ (p_{a,b}\in (0,1])$, the magic attribute of book $b$ becomes the magic attribute of book $a$. That is, with probability $1-p_{a,b}$, even if you have chosen books $a,b$, the transfer fails, meaning this operation is invalid.

Note that $p_{a,b}$ is the probability that the transfer succeeds, and it does not affect the random process of choosing the two books.

Now Kosuzu wants to know: what is the expected number of operations needed to make the magic attributes of all books identical? Since time is tight, Kosuzu asks you for help. Otherwise, she will not give you the points for this problem.

Input Format

The first line contains a string. The $i$-th character represents the magic attribute of the $i$-th book. Note that each book’s magic attribute is any uppercase letter from $A$ to $Z$. (Let the length of the string be $n$.)

Lines $2$ to $n+1$ each contain $n$ real numbers. The $j$-th number on the $i$-th of these lines represents $p_{i,j}$.

Output Format

Output the answer, accurate to $1$ digit after the decimal point.

NACLYFISHAKIOI
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0

164.9

DSGAY
1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0
1.0 1.0 1.0 1.0 1.0

16.0

Hint

For the first $10\%$ of the testdata, $n\leq 10$, and there is at most one kind of magic attribute.

For another $20\%$ of the testdata, $n\leq 10$, and there are at most two kinds of magic attributes, and the count of one of the attributes is at most $1$.

For $100\%$ of the testdata, $n\leq2\times 10^3$.

For all testdata, $\left(\sum\limits_{a=1}^{n}\sum\limits_{b=1}^{n}p_{a,b}\right) = n^2$.

Source

Meituzhijia 2019 League (MtOI2019) T3

Problem setter: Qiuly

Translated by ChatGPT 5