#C240808D. 打字机
网址（Website）
题目（Problem）
题目描述
小A打算创作一首诗歌，使用长度为 $ n \times m $ 的$01$串表示诗句。打字机有 $ p $ 的概率打出正确的数字，有 $ 1-p $ 的概率打出错误的数字。小A想知道，在他采用最优策略时打出好诗歌的概率。
输入格式
- 从文件
type.in读入数据。 - 第一行包含两个正整数 $ n $ 和 $ m $，以及一个浮点数 $ p $。
- 接下来 $ n $ 行，每行包含一个长度为 $ m $ 的$01$串。
输出格式
- 输出到文件
type.out。 - 输出一个浮点数代表正确的概率。
样例
输入数据 1
2 3 0.9
010
101输出数据 1
0.590490000000样例1解释
小A的策略是：一开始随便打一个数字，如果是 $00$，后续按 $1010110101$ 的顺序操作，成功打出好诗歌概率为 $ (0.9)^5 $。反之按 $0101001010$ 的顺序操作，成功打出好诗歌概率也为 $ (0.9)^5 $。所以按照此策略打出好诗歌的概率为 $ (0.9)^5 = 0.59049 $。
数据规模与约定
对于所有数据，有：
- $ 1 \leq n, m \leq 1000 $
- $ 0.5 \leq p < 1 $
测试点
| 测试点 | $ n, m \leq $ | 特殊性质 |
|---|---|---|
| $1\sim 6$ | $10$ | 无 |
| $7\sim12$ | $1000$ | $ n = 2^ m$ |
| $13\sim 20$ | $1000$ | 无 |
题解（Solution）
很明显，对于每一个位置，打印有没有错误的概率是一定的，而每一个串的顺序和答案无关，考虑对每一个 $01$ 串建 $Trie$ 树：对于 $Trie$ 树上的每一个节点，设它的下一位有 $x$ 个 $0$ ，$y$ 个 $1$ ，那么要打出好的串，这个节点至少要被经过 $x+y$ 次。
令 $f(x,y)$ 表示当前节点打出 $x$ 个 $0$ ，$y$ 个 $1$ 的概率，则可以推出：
f[0][0] = 1, f[x][0] = pow(p,x), f[0][y] = pow(p,y);f[x][y] = max(p*f[x-1][y]+(1-p)*f[x][y-1],p*f[x][y-1]+(1-p)*f[x-1][y]);
最终要求出每个点的 $f(x,y)$ ，由乘法原理，答案为 $\Pi_{p=0}^{p\le idx}f(x,y) $
代码（Code）
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
const int N = 1005;
bool ST;
int n,m,a[N];
double p,q;
int t[N*N][2],idx=0;
int cnt[N*N][2];
void insert(string s){
int p = 0, n = s.length();
for(int i = 0;i<n;i++){
int c = s[i] - '0';
cnt[p][c]++;
if(!t[p][c]) t[p][c] = ++idx;
p = t[p][c];
}
}
double f[N][N];
bool ED;
//看到题目就开走，不跑样例是小狗
//不打暴力是小狗
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("type.in","r",stdin);
freopen("type.out","w",stdout);
cin>>n>>m>>p;int Tim = clock();
For(i,1,n){
string s;cin>>s;
insert(s);
}q = 1 - p;
f[0][0] = 1;//打印 0 个 1 和 0 个 0 的概率为 1
For(i,1,n)
f[i][0] = f[i-1][0] * p,
f[0][i] = f[0][i-1] * p;
For(i,1,n) For(j,1,n)
f[i][j] = max(p*f[i][j-1]+q*f[i-1][j],p*f[i-1][j]+q*f[i][j-1]);
double ans = 1;
For(p,0,idx){
ans *= f[cnt[p][0]][cnt[p][1]];
}cout<<fixed<<setprecision(12)<<ans<<'\n';
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
