CF1773G
lsj2009
·
·
题解
Problem
状压 dp 绝世好题。
看到 m 非常小，我们考虑压一手，设 f_S 为剩余选手为 S 时 Genie 获胜得概率。
但是现在有个问题是，我们肯定要选择一个问题让 S 转移到 T，但是我们不知道这个问题之前有没有被选过，如果重复选择不就寄了，如果再开一维记录问题得状态，2^{2\cdot 10^5} 也寄了，怎么办？
这里用到了 UOJ370 的 trick：如果某个问题被重复选择，则集合 S 在问完这个问题后不会发生变化，因为不会这个问题的人都寄了。
接下来考虑如何转移。我们设 g_{S,T} 表示为可以令参赛者状态从 S 转移到 T 问题个数，显然 T\subset S，所以 g 的空间是 \Theta(3^n) 的，可以存的下。然后显然易得的是转移方程 f_S=\frac{\sum\limits_{T\subset S} f_T\cdot g_{S,t}}{n-g_{S,\emptyset}-g_{S,S}}，那么问题在于如何求 g。
然后就做完了，复杂度 $\Theta(nm+3^m)$。
### Code
```cpp
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=2e5+5,N1=17,M=1<<17;
vector<PII> g[M];
int tmp[N];
ld f[N];
char s[N1];
signed main() {
int n,m;
scanf("%d%d",&n,&m);
int tot=(1<<m)-1;
rep(S,0,tot) {
int len=1<<__builtin_popcount(S);
g[S].resize(len);
for(int T=S;;T=(T-1)&S) {
g[S][--len].first=T;
if(T==0)
break;
}
}
rep(i,1,n) {
scanf("%s",s);
int res=0;
rep(j,0,m-1) {
if(s[j]=='1')
res|=1<<j;
}
++g[tot][res].second;
}
per(S,tot-1,0) {
int k=-1;
rep(i,0,m-1) {
if(!((S>>i)&1)) {
k=i; break;
}
}
int t=S|(1<<k);
for(auto x:g[S])
tmp[x.first]=0;
for(auto x:g[t])
tmp[S&x.first]+=x.second;
for(auto &x:g[S])
x.second=tmp[x.first];
}
rep(S,0,tot) {
if((S+1)&1)
continue;
int cnt=n-g[S][0].second-g[S][(int)g[S].size()-1].second;
if(cnt==0)
f[S]=1.0;
else {
for(auto x:g[S]) {
int T=x.first;
if(T!=0&&T!=S)
f[S]+=f[T]*x.second;
}
f[S]/=cnt;
}
}
printf("%.12Lf\n",f[tot]);
return 0;
}
```