论如何用两枚硬币代替骰子

感谢伟大的 Cai 提供的思路！

首先，我们先制造一枚正反面概率均为 $\frac{1}{2}$的硬币，然后构造一棵比较大的完全二叉树，假设这棵二叉树有 k 个叶子节点，那么每个节点被选到的概率就是 $\frac{1}{k}$

然后将这 k 个叶子分为 n 组，其中，前 n-1 组的叶子数相等且不为 0，最后一组的叶子数小于等于前 n-1 组每组的叶子数，可以为 0。假设前 n-1 组每组有 $k_0$个叶子，最后一组有 $k_1$个叶子。

如果 $k_0=k_1$，就可以直接按照这种分组输出答案了。

否则前 n-1 组每组的概率为 $\frac{k_0}{k}$，这个概率是大于 $\frac{1}{n}$的，那么要从这个概率里” 分 “一点给最后一组。所以从每组中取一片叶子，给它添加两个儿子，抛第二枚硬币，让新的两个叶子，一个分给当前组，一个分给第 n 组，使得当前组的概率减少一点，恰好变成 $\frac{1}{n}$。

可知第二枚硬币的正面概率应为 $(\frac{1}{n}-\frac{k_0-1}{k})*k$

显然此时最后一组的概率也为 $\frac{1}{n}$

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int LIM=100000;
int n,tot,SZ,p1,q1;
int s[LIM+5][2],num[LIM+5],yb[LIM+5];
void build(int nowjs) {//建二叉树
    for(RI i=1;i<nowjs;++i)
        ++SZ,s[i][0]=i<<1,s[i][1]=(i<<1)|1,yb[i]=0;
}
void print() {
    puts("YES");
    printf("1 2 %d %d\n",p1,q1);
    printf("%d\n",SZ);
    for(RI i=1;i<=SZ;++i)
        if(num[i]) printf("E %d\n",num[i]-1);
        else printf("C %d %d %d\n",yb[i],s[i][0]-1,s[i][1]-1);
    exit(0);
}
int gcd(int x,int y) {
    int r=x%y;
    while(r) x=y,y=r,r=x%y;
    return y;
}
int main()
{
    scanf("%d",&n);
    for(RI nowjs=1;nowjs*2<=LIM;nowjs<<=1) {
        if(nowjs%n==0) {
            build(nowjs),p1=1,q1=2;
            for(RI j=1;j<=n;++j) ++SZ,num[SZ]=j;
            print();
        }
        else if(nowjs/(n-1)>0) {
            int k0=nowjs/(n-1),k1=nowjs-k0*(n-1);
            if(k1>=k0) continue;
            build(nowjs);
            p1=nowjs-(k0-1)*n,q1=n;int d=gcd(p1,q1);
            p1/=d,q1/=d;
            int kSZ=nowjs*2-1;
            for(RI j=1;j<=nowjs;++j) {
                int knum=(j-1)/k0+1,x=++SZ;
                if((j-1)%k0==0) {
                    s[x][0]=++kSZ,s[x][1]=++kSZ,yb[x]=1;
                    num[s[x][0]]=knum,num[s[x][1]]=n;
                }
                else num[x]=knum;
            }
            SZ=kSZ;print();
        }
    }
    puts("NO");
    return 0;
}

如何检查你的代码

因为太菜而 WA 了一次的 litble, 又因为太菜不会写 spj，所以让原来那个代码把 n 也输出来了，然后不输出”YES” 或”NO”，写了一个程序检验是否正确：

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int N=100005;
int n,SZ;
int vis[N];
struct fs{int a,b;}u[N],ans[N],g0,g1;
int gcd(int x,int y) {
    int r=x%y;
    while(r) x=y,y=r,r=x%y;
    return y;
}
fs operator - (fs x1,fs x2) {
    fs re;int d=1;
    re.b=x1.b*x2.b,re.a=x1.a*x2.b-x2.a*x1.b;
    d=gcd(re.a,re.b),re.a/=d,re.b/=d;return re;
}
fs operator + (fs x1,fs x2) {
    fs re;int d;
    re.b=x1.b*x2.b,re.a=x1.a*x2.b+x2.a*x1.b;
    d=gcd(re.a,re.b),re.a/=d,re.b/=d;return re;
}
fs operator * (fs x1,fs x2) {
    fs re;int d;
    re.b=x1.b*x2.b,re.a=x1.a*x2.a;
    d=gcd(re.a,re.b),re.a/=d,re.b/=d;return re;
}
int main()
{
    freopen("lx.out","r",stdin);
    char ch[10];int p,x,y;
    fs e=(fs){1,1};
    scanf("%d",&n);
    if(n==-1) {puts("WA");return 0;}
    scanf("%d%d%d%d",&g0.a,&g0.b,&g1.a,&g1.b);
    scanf("%d",&SZ);
    u[1].a=u[1].b=1;
    for(RI i=1;i<=n;++i) ans[i].b=1;
    for(RI i=1;i<=SZ;++i) {
        scanf("%s",ch);
        if(ch[0]=='E') {
            scanf("%d",&x);
            if(x>=n||x<0) {puts("WA");return 0;}
            ans[x+1]=ans[x+1]+u[i];
        }
        else {
            scanf("%d%d%d",&p,&x,&y);
            ++x,++y;
            if(x>SZ||y>SZ||x<=i||y<=i) {puts("WA");return 0;}
            if(p==0) u[x]=u[i]*g0,u[y]=u[i]*(e-g0);
            else u[x]=u[i]*g1,u[y]=u[i]*(e-g1);
        }
    }
    for(RI i=1;i<=n;++i) if(ans[i].a!=1||ans[i].b!=n) {puts("WA");return 0;}
    puts("AC");
    return 0;
}