牛客多校第六场 F 题题解

F Hash

题意：记 $nn$ 个点的树哈希 ${\displaystyle H(T)=\sum _{i=1}^n\sum _{j=i+1}^n{x}^i{y}^j{z}^{\mathrm{l}\mathrm{c}\mathrm{a}(i,j)}\mathrm{m}\mathrm{o}\mathrm{d}P}\backslash displaystyle\; H(T)=\backslash sum\_\{i=1\}^n\; \backslash sum\_\{j=i+1\}^n\; x^iy^jz^\{\{\backslash rm\; lca\}(i,j)\}\; \backslash bmod\; P$，其中 $P=998244353P=998244353$。给定 $H,x,y,zH,x,y,z$，构造一个不超过 $5050$ 个点的树满足其树哈希为 $HH$。

解法：考虑构造 $37=1+6\times 637=1+6\backslash times\; 6$ 个点的树——$11$ 为根，剩余 $3636$ 个节点分为 $66$ 组，每组中选出一个节点 $uu$ 和两个节点 $v_1,v_{2}v\_1,v\_2$，使得 $v_1,v_{2}v\_1,v\_2$ 的父亲是 $uu$，而其他所有节点的父亲均为 $11$。这样每组均有 ${\displaystyle 6\left(\genfrac{}{}{0px}{}{5}{2}\right)=60}\backslash displaystyle\; 6\{5\backslash choose\; 2\}=60$ 种变化方式，树的结构总共有 $60^{6}60^6$ 种变化，达到了 $40P40P$，因而不碰撞到给定数值是不可能事件（概率过低的可能事件）。而找到这一碰撞只需要使用双向广搜，记录前三个和后三个的全部变化，即可在 $\mathcal{O}(60^3\log 60)\backslash mathcal\; O(60^3\; \backslash log\; 60)$ 的复杂度内通过。

关于哈希：有三类哈希问题，原像（已知 $yy$ 求 $xx$ 使得 $f(x)=yf(x)=y$）、第二原像（给定 $x_{1}x\_1$，求 $x\mathrm{\ne }{x}_{1}x\; \backslash neq\; x\_1$ 且 $f(x)=f(x_1)f(x)=f(x\_1)$）、碰撞（找到 $x_1\mathrm{\ne }{x}_{2}x\_1\; \backslash neq\; x\_2$ 使得 $f(x_1)=f(x_2)f(x\_1)=f(x\_2)$）。对于原像和第二原像问题，其大概率成功所需要查询谕示器的次数为 $O(P)O(P)$，其中 $PP$ 为哈希池大小。构造哈希碰撞的期望次数仅为 $O(\sqrt{P})O(\backslash sqrt\; P)$。而构造碰撞的第一要务就是找到 $O(\sqrt{P})O(\backslash sqrt\; P)$ 级别的组合可能。由生日悖论，超过 $O(\sqrt{P})O(\backslash sqrt\; P)$ 级别的哈希值已经有极高概率碰撞。利用这一“悖论”，密码学中有一种生日攻击的方法可在很短的时间内制造 80bit 的哈希碰撞。通常建议使用长度为 160bit 的信息摘要（哈希）。

#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
const int N = 6, M = 6, ALL = N * M + 1;
const int WAY = M * (M - 1) * (M - 2) / 2;
const int INTREE = (M - 1) * (M - 2) / 2;
int spe[N][WAY];
pair<int, int> newson[N][WAY];
long long delta[N][WAY];
long long h, x, y, z;
long long thx[ALL + 5], thy[ALL + 5], thz[ALL + 5];
long long cal(int u, int v, int lca)
{
    if(u > v)
        swap(u, v);
    return thx[u] * thy[v] % mod * thz[lca] % mod;
}
int main()
{
    for (int i = 0; i < WAY;i++)
        for (int k = 0; k < N;k++)
        {
            int fa = (i / INTREE) + M * k + 2;
            spe[k][i] = fa;
            int sona = -1, sonb = -1, cnt = 0;
            for (int s1 = 0; s1 < M && sona == -1;s1++)
                if (s1 != i / 10)
                    for (int s2 = s1 + 1; s2 < M && sonb == -1;s2++)
                        if (s2 != i / INTREE)
                        {
                            if (cnt == i % 10)
                            {
                                sona = s1 + M * k + 2;
                                sonb = s2 + M * k + 2;
                            }
                            cnt++;
                        }
            newson[k][i] = make_pair(sona, sonb);
        }
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld%lld%lld%lld", &h, &x, &y, &z);
        printf("%d\n", ALL);
        thx[0] = thy[0] = thz[0] = 1;
        for (int i = 1; i <= ALL;i++)
        {
            thx[i] = thx[i - 1] * x % mod;
            thy[i] = thy[i - 1] * y % mod;
            thz[i] = thz[i - 1] * z % mod;
        }
        long long ori = 0;
        for (int i = 1; i <= ALL;i++)
            for (int j = i + 1; j <= ALL;j++)
                ori = (ori + thx[i] * thy[j] % mod * thz[1] % mod) % mod;
        if (ori == h)
        {
            for (int i = 2; i <= ALL;i++)
                printf("1 %d\n", i);
            continue;
        }
        memset(delta, 0, sizeof(delta));
        for (int k = 0; k < N; k++)
            for (int i = 0; i < WAY; i++)
            {
                delta[k][i] = (delta[k][i] - cal(spe[k][i], newson[k][i].first, 1) + mod - cal(spe[k][i], newson[k][i].second, 1) + mod - cal(newson[k][i].second, newson[k][i].first, 1) + mod) % mod;
                delta[k][i] = (delta[k][i] + cal(spe[k][i], newson[k][i].first, spe[k][i]) + cal(spe[k][i], newson[k][i].second, spe[k][i]) + cal(newson[k][i].first, newson[k][i].second, spe[k][i])) % mod;
            }
        map<long long, int> memo;
        function<void(int, int, long long)> dfs_front = [&](int step, int id, long long H)
        {
            if (step == N / 2)
            {
                memo[H] = id;
                return;
            }
            for (int i = 0; i < WAY; i++)
                dfs_front(step + 1, id * WAY + i, (H + delta[step][i]) % mod);
        };
        dfs_front(0, 0, 0);
        vector<int> mode(N, -1);
        function<bool(int, int, long long)> dfs_back = [&](int step, int id, long long H)
        {
            if (step == N / 2 - 1)
            {
                long long front = (h - H + mod - ori + mod) % mod;
                if (memo.count(front))
                {
                    int former = memo[front], latter = id;
                    for (int i = N / 2 - 1; i >= 0; i--, former /= WAY)
                        mode[i] = former % WAY;
                    for (int i = N / 2; i < N; i++, latter /= WAY)
                        mode[i] = latter % WAY;
                    return true;
                }
                else
                    return false;
            }
            for (int i = 0; i < WAY; i++)
            {
                auto d = dfs_back(step - 1, id * WAY + i, (H + delta[step][i]) % mod);
                if(d)
                    return true;
            }
            return false;
        };
        dfs_back(N - 1, 0, 0);
        vector<int> father(ALL + 1, 1);
        for (int i = 0; i < N;i++)
            father[newson[i][mode[i]].first] = father[newson[i][mode[i]].second] = spe[i][mode[i]];
        for (int i = 2; i <= ALL;i++)
            printf("%d %d\n", father[i], i);
    }
    return 0;
}