卡特兰数+博弈论+dp

树上删边游戏的公式是一个节点的$sg$值为儿子节点$sg$值$+1$的异或和。

设$dp_{i,j}$表示$i$个节点的二叉树$sg$值为$j$的概率，二叉树个数为卡特兰数，转移即可。

整个游戏的$sg$值等于每棵二叉树的$sg$值异或和。

设$g_{i.j}$为前i棵二叉树$sg$值为$j$的方案数，转移即可，答案为$1-g_{n,0}$。

复杂度$O(n^4)$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 155, m = 128;
int n;
int A[maxn];
double h[maxn], dp[maxn][maxn], f[maxn][maxn];
int main() {
    h[0] = 1;
    for(int i = 1; i < m; ++i)
        for(int j = 0; j < i; ++j)
            h[i] += h[j] * h[i - j - 1]; 
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &A[i]);
    dp[1][0] = 1;
    for(int i = 2; i <= n; ++i) {
        for(int j = 0; j < m; ++j)
            dp[i][j + 1] += 2 * dp[i - 1][j] * h[i - 1];
        for(int j = 1; j < i - 1; ++j)
            for(int a = 0; a < m; ++a)
                for(int b = 0; b < m; ++b)
                    dp[i][(a + 1) ^ (b + 1)] += dp[j][a] * dp[i - j - 1][b] * h[j] * h[i - j - 1];
        for(int j = 0; j < m; ++j) 
            dp[i][j] /= h[i];
    }
    f[0][0] = 1;
    for(int i = 1; i <= n; ++i) 
        for(int a = 0; a < m; ++a)
            for(int b = 0; b < m; ++b) {
                f[i][a ^ b] += f[i - 1][a] * dp[A[i]][b];
    //            printf("f[%d][%d] = %.3f dp[%d][%d] = %.3f\n", i - 1, a, f[i - 1][a], A[i], b, dp[A[i]][b]);
            }
    printf("%.6f\n", 1.0 - f[n][0]);
    return 0;
}

View Code