BZOJ2688: Green Hackenbush

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的异或和
举个例子从网上找的一张图

大家可以自己算一下

感性证明#

首先不考虑这个点以下的部分(我们一会再去管他) ，在这个点以上的部分先不考虑链接这个点的那些边。
那么他上面可以看做是几个子游戏。我们可以递归的计算他们是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游戏

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

得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 = 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]);
}