题目描述：
华华和秀秀在玩纸牌游戏，游戏的规则如下：
初始时，桌面上有?张纸牌，每张纸牌上写有一个正整数。游戏开始时华华先在黑板上写上数字0，之后秀秀和华华轮流选取纸牌（秀秀先手）。当一个人选定一张纸牌时，他需要将黑板上的数字改写成这个数和纸牌上的数的最大公约数，然后将这张纸牌丢弃。当一个人写下了1 或者无法选取纸牌时，他就输了。现在秀秀想知道：1. 当华华和秀秀都按照随机策略选取卡片时，秀秀获胜的概率有多少；2. 当华华和秀秀都按照最优策略选取卡片时，秀秀获胜的概率有多少。输入：
输入第一行，包含一个正整数?。
输入第二行，包含?个正整数，表示纸牌上的数字。输出：
输出两个由空格隔开的实数，分别表示随机策略下的获胜概率和最优策略下的获胜概率。
数据范围：
对于60%的数据：? ≤ 10;
另有10%的数据：纸牌上的数≤ 100;另有10%的数据：? ≤ 100;对于100%的数据：? ≤ 300, 纸牌上的数≤ 1000。算法标签：DP...乱搞
思路：
看到概率题就讨厌...我还有可能写好概率吗？？？
直接上转移式子：f[i][j] i 表示已经选了i个数，j表示目前黑板上写下的数(所有数的公共最大公因数)为j,转移式子是：
if(s[j]>=i)f[i][j]+=(s[j]-i+1)*f[i-1][j]/(n-i+1);
if (tt[j][a[k]]！=j) f[i][gcd[j][a[k]]]+=f[i-1][j]/(D)(n-i+1); 因为效率很卡，所以几乎所有能预处理的全部都要预处理鸭！
以下代码：
#include#define il inline#define D double#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=305,M=1005;int n,a[N],b[N][M],s[M],maxn,tt[M][M];D f[N][M],ans,aaa;il int read(){ int x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return f*x;}il int gcd(int x,int y){ if(x>y)swap(x,y);if(x==0)return y;return gcd(y%x,x);}int main(){ n=read();f[0][0]=1; for(int i=1;i<=n;i++){ a[i]=read();int tmp=a[i];if(a[i]>maxn)maxn=a[i]; for(int j=1;j*j<=a[i];j++){ if(a[i]%j==0){ s[j]++;if(j*j!=a[i])s[a[i]/j]++; if(j!=1&&tmp%j==0){ b[i][++b[i][0]]=j; while(tmp%j==0)tmp/=j; } } }if(tmp!=1)b[i][++b[i][0]]=tmp; } for(int i=0;i<=maxn;i++)for(int j=0;j<=maxn;j++)tt[i][j]=tt[j][i]=gcd(i,j); for(int i=1;i<=n;i++){ for(int j=0;j<=maxn;j++){ if(j==1)continue; if(s[j]>=i)f[i][j]+=(D)(s[j]-i+1)*f[i-1][j]/(D)(n-i+1); for(int k=1;k<=n;k++){ if(tt[j][a[k]]==j)continue; f[i][tt[j][a[k]]]+=f[i-1][j]/(D)(n-i+1); } } } for(int i=2;i<=n;i+=2)if((i&1)==0)ans+=f[i][1];bool pd=1; for(int i=1;i<=n;i++)if(f[i][1]>0)pd=0;if(pd&&(n&1)==1)ans=1;printf("%lf ",ans); for(int i=1;i<=n;i++){ bool pd=0; for(int k=1;k<=b[i][0];k++){ if((s[b[i][k]]&1)==0){pd=1;break;} } if(pd==0){aaa=1.0;break;} }printf("%lf\n",aaa); return 0;}