BZOJ2688 Green Hackenbush <概率DP+博弈论>

Problem

Green Hackenbush

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

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

Input

第一行一个数$n$。
接下来每行一个数$a_i$。

Output

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

Sample Input

1
2

Sample Output

1.000000

HINT

对于$100\%$的数据，$n\le100$，$a_i\le100$。

Source

CodeCraft09

标签：概率DP 博弈论

Solution

概率$\mathrm{DP}$与博弈论的结合，需要用到克朗原理（$\mathrm{Colon\;Principle}$），即在树上删边游戏中，一个结点的$\mathrm{SG}$值等于其儿子的$\mathrm{SG}$值加$1$后的异或和。
用$h_i$表示结点数为$i$的二叉树的形态种数，那么有状态转移方程：$h_i=\sum_{j=0}^{i-1}h_jh_{i-j-1}$。边界：$h_0=1$。
用$g_{i,x}$表示结点数为$i$的二叉树根节点$\mathrm{SG}$值为$x$的期望。由于只有$100$个结点，可知$\mathrm{SG}$值最大为$127$。于是有状态转移：（刷表法）做到$i$个结点的情况时，枚举两棵子树的大小$j,k$，保证$j+k=i-1$且$j,k\in[1,i)$，枚举两棵子树的$\mathrm{SG}$值$x,y\in[0,127]$，那么其对$g_{i,(x+1)\oplus(y+1)}$的贡献为$\frac{h_jg_{j,x}\cdot h_kg_{k,y}}{h_i}$。边界：$g_{1,0}=1$。
用$f_{i,x}$表示第$1\sim i$棵树$\mathrm{SG}$值异或和为$x$的期望。同样用刷表法，做到$1\sim i$棵树时，枚举第$i$棵树的$\mathrm{SG}$值$x\in[0,127]$，枚举前$1\sim(i-1)$棵树$\mathrm{SG}$值异或和为$y\in[0,127]$，那么其对$f_{i,x\oplus y}$的贡献为$f_{i-1,y}\cdot g_{a_i,x}$。边界：$f_{1,x}=g_{a_1,x}\;(x\in[0,127])$。
按顺序$\mathrm{DP}$出$h,g,f$即可求解，显然当$\mathrm{SG}$值不等于$0$时$\mathrm{Alice}$获胜，于是答案为$1-f_{n,0}$。

Code

#include <bits/stdc++.h>
using namespace std;
typedef double dnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, a[105];
dnt f[105][130], g[105][130], h[105];
int main() {
    read(n); g[1][0] = h[0] = 1.0;
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i <= 100; i++)
        for (int j = 0, k = i-1; j < i; j++, k--)
            h[i] += h[j]*h[k];
    for (int i = 2; i <= 100; i++) {
        for (int x = 0; x <= 127; x++)
            g[i][x+1] += 2.0*g[i-1][x]*h[i-1]/h[i];
        for (int j = 1, k = i-2; j < i-1; j++, k--)
            for (int x = 0; x <= 127; x++)
                for (int y = 0; y <= 127; y++)
                    g[i][(x+1)^(y+1)] += g[j][x]*g[k][y]*h[j]*h[k]/h[i];
    }
    for (int x = 0; x <= 127; x++) f[1][x] = g[a[1]][x];
    for (int i = 2; i <= n; i++)
        for (int x = 0; x <= 127; x++)
            for (int y = 0; y <= 127; y++)
                f[i][x^y] += f[i-1][x]*g[a[i]][y];
    return printf("%.6lf\n", 1.0-f[n][0]), 0;
}