Public Judge

pjudge

Time Limit: 2 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 21658. 【PR #6】DNA 匹配

统计

称一个字符串 $s$ 是 DNA 序列,当且仅当 $s$ 只由 A, C, G, T 组成。

给定 $m$ 个 字符串 $s_1,\cdots,s_m$ ,每个序列的长度均为 $n$ ,且只由 A, C, G, T, ? 组成。

对于一个长度为 $n$ 的 DNA 序列 $t$ ,称 $t$ 是合法的,当且仅当存在一个 $s_i$ ,且存在一种把 $s_i$ 中的 ? 替换的方法,使得替换后得到的 $\tilde s_i$ 等于 $t$ 。

你需要求出,当 $t$ 在所有长度为 $n$ 的 DNA 序列中等概率随机时,$t$ 合法的概率。

你的答案在相对误差不超过 $5\%$ 时会被视为正确。换句话说,若真实概率是 $w$ ,而你输出了 $v$ ,那么当且仅当 $0.95w\le v\le 1.05w$ 时你会被视为正确。

输入格式

第一行,两个正整数 $n,m$ 。

接下来 $m$ 行,每行一个长度为 $n$ 的字符串 $s_i$ ,保证 $s_i$ 只由 A, C, G, T, ? 组成。

输出格式

一行,一个实数,表示答案。

你可以选择使用科学计数法。比如 $\texttt{0.045}$ 也可以输出为 $\texttt{4.5e-2}$ 。

样例一

input

3 1
AC?

output

0.0625

explanation

在区间 $[0.059375,0.065625]$ 的实数都会被判定为正确答案。

保证样例输出与真实答案的相对误差不超过 $1\%$ 。

样例二

input

6 2
AC??A?
A??A?T

output

0.0302734375

样例三

input

30 1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

output

8.673617379884035e-19

explanation

此处输出 $0$ 是错误的,因为计算的是相对误差。

注意当 $n$ 变得更大时答案可以更小。可以考虑使用 long double ,然后在输出时使用 printf("%.70Lf\n",ans)

样例四

见下发文件,该样例满足正确答案 $w\ge 0.01$ 。

样例五

见下发文件,该样例满足 $n=100$ ,$s_i$ 中 ? 的数量在 $[0,n-20]$ 均匀随机。

样例六

见下发文件。

数据范围与提示

对于 $30\%$ 的数据,保证 $m\le 20$ 。

对于另外 $20\%$ 的数据,保证正确答案 $w\ge 0.01$ 。

对于另外 $20\%$ 的数据,保证 $n=100$ ,$s_i$ 中 ? 的数量在 $[0,n-20]$ 均匀随机。

对于 $100\%$ 的数据,保证 $1\le n\le 100, 1\le m\le 40$ 。

因为一些原因,最后 $30\%$ 的数据捆绑测试。

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$