OI - math(Local) | Lucky_Glass's Blog
0%

OI - math(Local)

考场上以为自己写了个跑得飞快的暴力程序踩了标算,然后赛后发现是一种正解 :)


# 题面

点击展开/折叠 题面

有 $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
/*Lucky_Glass*/
#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]);
// printf("%d,%d -> %d\n",ihas[k],num[i],gcd);
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("%f\n",g[i]);
}
printf("%.5f\n",totA/(totA+totB));
return 0;
}

THE END

Thanks for reading!

> Linked hello&bye,days-网易云

> Linked 无星夜-Bilibili