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

Problem

Green Hackenbush

Description

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

Input

第一行一个数。
接下来每行一个数。

Output

一个保留位小数的实数。

Sample Input

1
2

Sample Output

1.000000

HINT

对于的数据，，。

Source

CodeCraft09

标签：概率DP 博弈论

Solution

概率与博弈论的结合，需要用到克朗原理（），即在树上删边游戏中，一个结点的值等于其儿子的值加后的异或和。
用表示结点数为的二叉树的形态种数，那么有状态转移方程：。边界：。
用表示结点数为的二叉树根节点值为的期望。由于只有个结点，可知值最大为。于是有状态转移：（刷表法）做到个结点的情况时，枚举两棵子树的大小，保证且，枚举两棵子树的值，那么其对的贡献为。边界：。
用表示第棵树值异或和为的期望。同样用刷表法，做到棵树时，枚举第棵树的值，枚举前棵树值异或和为，那么其对的贡献为。边界：。
按顺序出即可求解，显然当值不等于时获胜，于是答案为。

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;
}