考场上以为自己写了个跑得飞快的暴力程序踩了标算,然后赛后发现是一种正解 :)
# 题面
点击展开/折叠 题面
有 $n$ 个正整数($n\le100$,数的大小不超过 $10^6$),A,B 两人轮流取数。
两人每次随机从剩下的数中取出一个,放入集合 $S$。若一个人取数后 $\gcd(x\mid x\in S)=1$,则他输了;或者轮到一个人取数的时候,已经没有数了,他也输了。
A 为先手,求 A 获胜的概率。
# 解析
盲猜 $n$ 个数中取出一些数能够构成的 gcd 数量很少(前提是先给每个数的质因子去重)……
因为最后只要判断 gcd 是否为 $1$,所以可以预先处理一下,若 $a_i=p_1^{x_1}p_2^{x_2}\dots p_m^{x_m}$,则 $a_i:=p_1p_2\dots p_m$,这样显然不会对 “gcd 是否为 $1$” 造成影响。
然后我们发现 $10^6$ 内,一个数最多有 $7$ 个不同的质因子,能够构成 $2^7$ 种不同的因子,因此能够构成的 gcd 数量的粗略上界是 $2^7\times n=12800$,可以看到是非常小的。
有了这个结论,我们可以稍微大胆一点设计 DP。$f_{i,j,k}$ 表示前 $i$ 个数中,选了 $j$ 个、$\gcd=k$ 的方案数。对于 $k$ 可以哈希储存现在能够构成的 $\gcd$,转移则是 01背包。
然后乘上 $j!$,即算上选择的顺序。
设 $g_i$ 表示恰好选了 $i$ 个数,游戏结束的方案数。则 $i$ 为偶数时先手获胜,求得 $g_i$ 就可以算出答案了。
但是 $g_i$ 并不直接为 $f_{n,i,1}$,因为在选择 $i$ 个数之前可能 gcd 已经为 $1$ 了。也只需要容斥一下,减去选了 $i-1$ 个数 gcd 为 $1$ 的方案数即可(考试的时候想复杂了……),即 $g_i=f_{n,i,1}-f_{n,i-1,1}$。
原题是要输出五位小数的……管都没有管直接上 double
居然过了 awa 反正不太重要。
还有个莫比乌斯反演的方法,可能复习(学习)了过后会回来咕
# 源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
| #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
inline int Read(){ register int r=0,c=getchar(); while(c<'0' || '9'<c) c=getchar(); while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar(); return r; }
const int N=105,M=1e6; #define ci const int &
int n; int num[N]; double f[2][N][30000],g[N],fac[N]; double comb[N][N]; int has[M+10],ihas[M+10],nhas; int vis[M+10],prn[M],nprn;
inline int GCD(ci a,ci b){return b? GCD(b,a%b):a;} void Init(){ for(int i=0;i<=n;i++){ comb[i][0]=1; for(int j=1;j<=i;j++) comb[i][j]=comb[i-1][j-1]+comb[i-1][j]; } fac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i; for(int i=2;i<=M;i++){ if(!vis[i]) vis[i]=prn[++nprn]=i; for(int j=1;j<=nprn && prn[j]*i<=M;j++){ vis[prn[j]*i]=prn[j]; if(i%prn[j]==0) break; } } } int main(){ freopen("math.in","r",stdin); freopen("math.out","w",stdout); n=Read(); Init(); int allgcd=0; bool all1=true; for(int i=1;i<=n;i++){ allgcd=GCD(allgcd,num[i]=Read()); int res=1,las=-1; while(num[i]>1){ if(las!=vis[num[i]]) res*=vis[num[i]]; las=vis[num[i]]; num[i]/=vis[num[i]]; } num[i]=res; all1&=num[i]==1; } if(allgcd>1){ printf("%.5f\n",(n&1)? 1.0:0.0); return 0; } if(all1){ printf("%.5f\n",0.0); return 0; } f[0][0][1]=1; ihas[has[0]=++nhas]=0; for(int i=1;i<=n;i++){ int I=i&1,J=!I; for(int j=0;j<=i;j++) for(int k=1;k<=nhas;k++) f[I][j][k]=0; for(int j=0;j<=i;j++) for(int k=1,K=nhas;k<=K;k++){ f[I][j][k]+=f[J][j][k]; int gcd=GCD(ihas[k],num[i]);
if(!has[gcd]) ihas[has[gcd]=++nhas]=gcd; f[I][j+1][has[gcd]]+=f[J][j][k]; } } for(int I=n&1,j=1;j<=n;j++){ g[j]=f[I][j][has[1]]*fac[j]; } double totA=0,totB=0; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++) g[j]-=fac[j-i]*comb[n-i][j-i]*g[i]; if(i&1) totB+=g[i]*fac[n-i]; else totA+=g[i]*fac[n-i]; } printf("%.5f\n",totA/(totA+totB)); return 0; }
|
THE END
Thanks for reading!
> Linked hello&bye,days-网易云
> Linked 无星夜-Bilibili