[ICPC2018西安J] Philosophical … Balance

[ICPC2018西安J] Philosophical … Balance - 后缀自动机,纳什均衡,概率期望dp

Description

给出一个字符串 (s) ，你需要给每一个 (i) 一个 ([0,1]) 之间的权值 (k_i)，且满足 (sum k_i=1)。并且最大化 (min_{i=1}^n(sum_{j=1}^nlcp(suf(s,j),suf(s,i)) imes k_j))

Solution

在反串的 Suffix Tree 上利用 Nash 性质做概率 dp

设 (f[i]) 表示对于 (i) 子树内做整个游戏（此时的概率总和为 (1)），能获得的最大结果是多少

对于一个点 (p) 的子树，如果 (p) 本身包含一个是反串的前缀的状态，那么 (f[p]) 显然等于 (len[p])，因为一定会将所有概率分布在 (p) 上

否则，此时子树内的贡献需要进一步计算，而子树间的贡献必然是 (len[p])

假设我们现在点 (p) 有 (q_1,q_2,...,q_k) 这些孩子

那么对于 (q_i) 这个孩子，假设我们给他 (x) 的概率，那么他的贡献就是 (len[p] + (f_{q_i}-len[p]) x)

这个分布是先手设定的，而后手会取最小的那个，先手要使得最小值最大，根据纳什均衡，所有的取值应该相等

可以推出，最后的 (x) 是按照系数的倒数来分布的，因此这一去做一个树上的 dp 即可

[f[p] = len[p] + frac {1} {sum_{q} frac 1 {(f[q]-len[p])}} ]

#include <bits/stdc++.h>
using namespace std;
const int N = 2000005;
struct SAM
{
    // int len[N], ch[N][26], fa[N], ind, last;
    // int t[N], a[N], cnt[N], f[N];
    vector<int> len;
    vector<vector<int>> ch;
    vector<int> fa;
    vector<double> f;
    vector<vector<int>> g;
    vector<int> tag;
    int ind, last;
    SAM(int N)
    {
        ind = last = 1;
        len.resize(N);
        ch = vector<vector<int>>(N, vector<int>(26));
        g.resize(N);
        tag.resize(N);
        fa.resize(N);
        f.resize(N);
    }
    inline void extend(int id)
    {
        int cur = (++ind), p;
        len[cur] = len[last] + 1;
        for (p = last; p && !ch[p][id]; p = fa[p])
            ch[p][id] = cur;
        if (!p)
            fa[cur] = 1;
        else
        {
            int q = ch[p][id];
            if (len[q] == len[p] + 1)
                fa[cur] = q;
            else
            {
                int tmp = (++ind);
                len[tmp] = len[p] + 1;
                for (int i = 0; i < 26; i++)
                    ch[tmp][i] = ch[q][i];
                fa[tmp] = fa[q];
                for (; p && ch[p][id] == q; p = fa[p])
                    ch[p][id] = tmp;
                fa[cur] = fa[q] = tmp;
            }
        }
        last = cur;
    }

    void puttag(const string &str)
    {
        int p = 1;
        for (int i = 0; i < str.length(); i++)
        {
            p = ch[p][str[str.length() - 1 - i] - 'a'];
            tag[p] = 1;
        }
    }

    void dfs(int p)
    {
        if (tag[p])
        {
            f[p] = len[p];
        }
        else
        {
            double sum = 0;
            // todo: distribute by (f_q - len_p), so just sum the inv and then inv
            for (int q : g[p])
            {
                dfs(q);
                sum += 1.0 / (f[q] - len[p]);
            }
            f[p] = len[p] + 1.0 / sum;
        }
    }
    void solve()
    {
        for (int i = 1; i <= ind; i++)
            g[fa[i]].push_back(i);
        // Todo: Do dfs and calculate all f[]
        dfs(1);
        cout << fixed << setprecision(12) << f[1] << endl;
    }
};

void solve()
{
    string str;
    cin >> str;
    SAM sam(2 * str.length() + 2);
    int t, k;
    for (int i = 0; i < str.length(); i++)
        sam.extend(str[str.length() - 1 - i] - 'a');
    sam.puttag(str);
    sam.solve();
}

signed main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
        solve();
}