981 字
5 分钟
BZOJ2688: Green Hackenbush
2018-01-18

Description#

有一个古老的游戏叫做Green Hackenbush,游戏是这样进行的:两个人轮流在一棵树上删边,每次删边后不与根联通的子树直接被ignore,不能删边的游戏者输。Alice和Bob也在玩这个游戏,不过他们面对的是n棵树,第i棵树是含有a[i]个节点的二叉树。先手的Alice想知道自己有多大的概率获胜(假设我们的Alice和Bob同学都是无限聪明的)。

Input#

第一行一个数n。 接下来每行一个数a[i]。

Output#

一个保留6位小数的实数ans。

Sample Input#

1
2

Sample Output#

1.000000

HINT#

对于100%的数据,n<=100,a[i]<=100

题解#

首先我们考虑正常的Green Hackenbush游戏

Step1:#

让我们先从最简单的开始
假设树退化为一条链
那么我们会发现这好像就是一个Nim游戏
那么我们可以通过异或来解决这个问题

Step2:#

再让我们考虑一颗树
那么根据Colon Principle原理
一个点的SG函数值为它的所有的子树的SG+1的异或和
举个例子 从网上找的一张图

1344074319_7883.jpg
大家可以自己算一下

感性证明#

首先不考虑这个点以下的部分(我们一会再去管他) , 在这个点以上的部分先不考虑链接这个点的那些边。
那么他上面可以看做是几个子游戏。 我们可以递归的计算他们是SG值
把他们等效成一条链, 然后加上链接这个点的那些边, 及SG+1
根据Nim 的结论, 我们可以将他们异或起来。


现在让我们考虑下面的部分
假设一个任意固定的图G,一个任意节点x,让H1和H2为任意的树,且拥有相同的SG值。考虑这样两个图G1=Gx

和G2=Gx

#

,Gx:Hi表示该图是把树Hi连接图的x节点。
则我们需要证明G1与G2的SG值相等
G1、G2拥有相同的SG值意味着两个游戏的总SG值为0,G1+G2的和是一个P局面,也就是必败
先手一旦在其中一幅图中取走任意一条边,后手即可在另一幅图中取走相对应的一条边。轮流下去,最后肯定是后手获胜。

然后我们搞定了正常的Green Hackenbush游戏

现在让我们来看这道题
对应xx个点去建一颗二叉树有多少种方法?
分别考虑左右子树
我们有
h[x]=i=0n1h[i]h[ni1]h[x] = \sum_{i = 0}^{n - 1}{h[i] * h[n - i - 1]}
这好像就是卡特兰数。
然后我们设g[i][j]g[i][j]为有ii个点的树SG值为jj的概率

得DP方程为

g[n][(x + 1) \^ (y + 1)] = \sum_{i = 0}^{n - 1}{ h[i] * g[i][x] * h[n - 1 - i] * g[n - 1 - i][y]}

f[i][j]表示的是前i颗子树异或值为j的概率

f[i][j \^ k]=f[i-1][j] * g[a[i]][k]

搞定 ans=1f[n][0]ans = 1-f[n][0]

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int a[105];
double h[150];
double g[350][350], f[350][350];
int main()
{
    int n = read(), m = 0;
    for (int i = 1; i <= n; i++)
        a[i] = read(), m = max(m, a[i]);
    h[0] = 1;
    for (int i = 1; i <= m; i++)
        h[i] = h[i - 1] * (4 * i - 2) / (i + 1);
    g[1][0] = 1;
    for (int i = 2; i <= m; i++)
    {
        for (int j = 0; j <= 127; j++) g[i][j + 1] += h[i - 1] * 2 * g[i - 1][j];
        for (int j = 1; j < i - 1; j++)
        {
            int k = i - j - 1;
            for (int x = 0; x <= 127; x++)
                for (int y = 0; y <= 127; y++)
                    g[i][(x + 1) ^ (y + 1)] += h[j] * g[j][x] * h[k] * g[k][y];
        }
        for (int j = 0; j <= n - 1; j++) g[i][j] /= h[i];
    }
    for (int i = 0; i <= 127; i++) f[1][i] = g[a[1]][i];
    for (int i = 2; i <= n; i++)
        for (int j = 0; j <= 127; j++)
            for (int k = 0; k <= 127; k++)
                f[i][j ^ k] += f[i - 1][j] * g[a[i]][k];
    printf ("%.6f\n", 1.0 - f[n][0]);
}
BZOJ2688: Green Hackenbush
https://www.nekomio.com/posts/125/
作者
NekoMio
发布于
2018-01-18
许可协议
CC BY-NC-SA 4.0