【描述】 你在跟朋友玩一个记忆游戏。 朋友首先给你看了n个长度相同的串，然后从中等概率随机选择了一个串。 每一轮你可以询问一个位置上的正确字符，如果能够凭借已有的信息确定出朋友所选的串，那么游戏就结束了，你的成绩就是所用的轮数。 由于你实在太笨，不会任何策略，因此你采用一种方法，每次等概率随机询问一个未询问过的位置的字符。 现在你想知道，在这种情况下，你猜出结果所需的期望次数。 对于20%的数据，n，l<=10 对于30%的数据，n，l<=15 对于60%的数据，n，l<=20 对于100%的数据，n<=50，l<=20
首先设朋友选的串为第i个，猜出的期望次数为 E i E_i Ei。那么答案显然： a n s = ∑ E i / n ans=\sum E_i/n ans=∑Ei/n。 考虑暴力：对于每一个枚举的串，我们可以枚举全排列，判断第几次猜出来，然后加起来除以总排列数即可。考虑优化：我们发现，对于一个不能猜出来的状态，我们并不关心其询问集合的顺序，所以可以状压dp。此时如果加上判断状态是否合法的剪枝，随机数据下表现将相当优秀，甚至比正解快。时间复杂度 O ( n ∗ 2 l − n ∗ l ∗ 2 l ) O(n*2^l-n*l*2^l) O(n∗2l−n∗l∗2l)。这种乱搞的时间复杂度实际上和串密切相关，如果能很快区分每个串，就跑得很快。 考虑再优化：我们发现，对于每一次转移，实际上和我们当前枚举的串本身是无关的，只与下一步能否区分出有关。所以我们可以预处理有多少个串有当前这步转移，根据期望的线性性，加起来就是答案。 代码： 乱搞(90 points)：
#include<bits/stdc++.h> #define re register using namespace std; const int N=20+5; int n,l,U,cnt=0; char s[55][N]; inline int red(){ int data=0;int w=1; char ch=0; ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar(); return w==1?data:-data; } double f[1<<20|1]; long long d[25],law; bool vis[1<<20|1]; double ans=0; void dfs(const int&pos,const long long&now,const int&S){ if(law==now)return; vis[S]=1;if(pos==l)return; dfs(pos+1,now|d[pos],S|(1<<pos)); dfs(pos+1,now,S); } int main(){ n=red(); for(int re i=0;i<n;i++) scanf("%s",s[i]); l=strlen(s[0]);U=1<<l; for(int re i=0;i<n;i++){ law=((1ll<<n)-1)^(1ll<<i); memset(d,0,sizeof(d)); memset(f,0,sizeof(f)); memset(vis,0,sizeof(vis)); for(int re j=0;j<n;++j) for(int re k=0;k<l;++k) if(s[i][k]!=s[j][k]) d[k]|=1ll<<j; dfs(0,0,0); for(int re s=U-1;~s;--s){ if(!vis[s])continue; cnt=0; for(int re j=0;j<l;++j) if(!(s&(1<<j)))f[s]+=f[s|(1<<j)],++cnt; f[s]/=cnt;f[s]++; } ans+=f[0]; }ans/=n; printf("%.10f",ans); }正解(100 points)：
#include<bits/stdc++.h> #define re register using namespace std; const int N=20+5; int n,l,U; char s[55][N]; inline int red(){ int data=0;int w=1; char ch=0; ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar(); return w==1?data:-data; } long long d[25],law; double ans=0; int C[N][N],*c,num[1<<20|1],cnt[1<<20|1]; inline void dfs(int pos,long long now,int S){ if(now==law)return; if(pos==l)return void(cnt[S]+=(now!=law)); dfs(pos+1,now|d[pos],S|(1<<pos)); dfs(pos+1,now,S); } int main(){n=red(); for(int re i=0;i<n;i++)scanf("%s",s[i]); l=strlen(s[0]);U=1<<l; for(int re i=0;i<=l;++i)C[i][0]=C[i][i]=1; for(int re i=1;i<=l;++i) for(int re j=1;j^i;++j) C[i][j]=C[i-1][j]+C[i-1][j-1]; c=C[l]; for(int re i=0;i<U;++i)num[i]=num[i>>1]+(i&1); for(int re i=0;i<n;i++){ law=((1ll<<n)-1)^(1ll<<i); memset(d,0,sizeof(d)); for(int re j=0;j<n;++j) for(int re k=0;k<l;++k) if(s[i][k]!=s[j][k]) d[k]|=1ll<<j; dfs(0,0,0); }for(int re s=U-1;s;--s){ int res=0,u=s; while(u)res+=cnt[s^(u&(-u))]-cnt[s],u^=u&(-u); ans+=1.0*res/c[num[s]]; }printf("%.10f",ans/n); }