CF 997D Cycles in product

传送门

题目大意

给你大小分别为 n1 n 1 $n_1$ 和 n2 n 2 $n_2$ 的两棵树 T1 T 1 $T_1$ 和 T2 T 2 $T_2$。构造一张新图，该图中每一个点的编号为 (u,v) ( u , v ) $(u, v)$。如果在 T1 T 1 $T_1$ 中 u1 u 1 $u_1$ 和 u2 u 2 $u_2$ 之间有边，那么在该图上对于任意的 v v $v$，(u1,v)$(u_1,v)$$(u_1, v)$ 和 (u2,v) ( u 2 , v ) $(u_2, v)$ 之间有边。同样，如果在 T2 T 2 $T_2$ 中 v1 v 1 $v_1$ 和 v2 v 2 $v_2$ 之间有边，那么在该图上对于任意的 u u $u$，(u,v1)$(u,v_1)$$(u, v_1)$ 和 (u,v2) ( u , v 2 ) $(u, v_2)$ 之间有边。问你这个图上长度为 K K $K$ 的环有多少个。环的定义是从一个点出发，走 k$k$$k$ 步回到起点，可以经过重复点和重复边，路径相同，起点不同的环看作是不同的。

n1,n2≤4000 n 1 , n 2 ≤ 4000 $n_1, n_2 \le 4000$， k≤75 k ≤ 75 $k \le 75$，答案对 998244353 998244353 $998244353$ 取模。

思路

什么都不会的感觉……

考虑子问题。如果直接给你一张图，让你求出走 k k $k$ 步回到原点的方案数可以怎么做？由于可以经过重复点和重复边，因此设 fi,j$f_{i,j}$$f_{i, j}$ 表示走 j j $j$ 步到 i$i$$i$ 的方案数，边界条件为 fs,0=1 f s , 0 = 1 $f_{s, 0} = 1$，最终答案为 fs,k f s , k $f_{s, k}$。 n n $n$ 个点的时间复杂度为 O(n2k)$O(n^{2}k)$$O(n^2 k)$ 或者 O(n3logk) O ( n 3 log ⁡ k ) $O(n^3 \log k)$。

现在我们要求从每个点出发的答案之和，显然我们不能写一个 O(n4k) O ( n 4 k ) $O(n^4 k)$ 的算法……

---

显然我们甚至不能把这张新的图建出来，因此我们考虑下这个新图到底是什么意思。我们把它看作一个二维坐标 (x,y) ( x , y ) $(x, y)$，每次移动要么根据 T1 T 1 $T_1$ 改变 x x $x$，要么根据 T2$T_2$$T_2$ 改变 y y $y$。这样我们就明白了，原来可以把问题抽象到这两棵树上，看作两棵树上分别有一个棋子，我们每次能够选一个棋子走一步，问操作 k$k$$k$ 次后两个棋子都在原位的方案数。

考虑枚举在第一棵树上走了多少步。设 f1,i f 1 , i $f_{1, i}$ 表示在第一棵树上走了 i i $i$ 步回到起点的方案数，f2,i$f_{2,i}$$f_{2, i}$ 表示在第二棵树上走了 i i $i$ 步回到起点的方案数，那么最终答案为：

$$\sum_{i = 0}^{k} f_{1, i} \cdot f_{2, k - i} \mathrm{C}_{k}^{i}$$
f1,i f 1 , i $f_{1, i}$ 等于从第一棵树上的每个结点出发走 i i $i$ 步回到自己的方案数之和；注意要乘以一个组合数。如果沿用前面的思路，那么不可避免的每个结点出发都要算一遍，时间复杂度为 O(n2k)$O(n^{2}k)$$O(n^2 k)$，不足以通过此题。

有没有更好的做法呢？

---

由于不同的路径对于所有不同的起点都有贡献，那我们考虑一下，对于一条路径能不能让所有经过的点都算上贡献。考虑点分治，每次统计经过分治中心的路径对所有点的答案的贡献。注意到，对于一个点来说，一条回路必然呈花瓣状，于是我们求两个东西： fi,j f i , j $f_{i, j}$ 和 gi,j g i , j $g_{i, j}$。 fi,j f i , j $f_{i, j}$ 表示从分治中心出发走 j j $j$ 步停在 j$j$$j$ 点的方案数，要求中间不经过分治中心（也就是一个花瓣）， gi,j g i , j $g_{i, j}$ 意义与 fi,j f i , j $f_{i, j}$ 相同，但是没有限制（也就是任意多个花瓣）。对于分治中心而言，贡献就是 gc,k g c , k $g_{c, k}$，但是对于其它点 v v $v$ 而言，我们考虑这样两条路径：从分治中心出发，不经过分治中心到达 v$v$$v$；从分治出发，可以经过分治中心到达 v v $v$。把第二条路径反转，我们就得到一条从 v$v$$v$ 出发的回路。我们枚举第一条路径的长度（这条路径必然是一个花瓣的一部分，就不会算重了），然后用 O(k2) O ( k 2 ) $O(k^2)$ 的时间复杂度做卷积即可。时间复杂度 O(nk2logn) O ( n k 2 log ⁡ n ) $O(n k^2\log n)$。

参考代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
    putchar('\n');
}

const int mod = 998244353;
inline void add(int& a, const int& b)
{
    register int t;
    a = (t = a + b) >= mod ? t - mod : t;
}
const int maxn = 4005;
const int maxk = 80;
int k;
typedef std::vector<std::vector<int> > Graph;
struct Tree
{
    int n;
    Graph G;
    void resize(int size)
    {
        n = size;
        G.resize(size + 1);
    }
    void read()
    {
        for (int i = 2; i <= n; i++)
        {
            int from = readIn();
            int to = readIn();
            G[from].push_back(to);
            G[to].push_back(from);
        }
    }

    bool vis[maxn];
    int size[maxn];
    void DFS1(int node, int parent)
    {
        size[node] = 1;
        for (int i = 0; i < G[node].size(); i++)
        {
            int to = G[node][i];
            if (to == parent || vis[to]) continue;
            DFS1(to, node);
            size[node] += size[to];
        }
    }
    int findRoot(int node, int parent, int s)
    {
        for (int i = 0; i < G[node].size(); i++)
        {
            int to = G[node][i];
            if (to == parent || vis[to])
                continue;
            if (size[to] > (s >> 1))
                return findRoot(to, node, s);
        }
        return node;
    }

    std::vector<std::pair<int, int> > transfer[2];
    std::vector<int> nodes;
    int f[maxn][maxk];
    int g[maxn][maxk];

    void DFS2(int node, int parent)
    {
        nodes.push_back(node);
        std::memset(f[node], 0, sizeof(f[node]));
        std::memset(g[node], 0, sizeof(g[node]));
        for (int i = 0; i < G[node].size(); i++)
        {
            int to = G[node][i];
            if (to == parent || vis[to])
                continue;
            transfer[0].push_back(std::make_pair(node, to));
            transfer[1].push_back(std::make_pair(node, to));
            transfer[1].push_back(std::make_pair(to, node));
            if (node != nodes.front())
                transfer[0].push_back(std::make_pair(to, node));
            DFS2(to, node);
        }
    }

    void solve(int node)
    {
        DFS1(node, 0);
        node = findRoot(node, 0, size[node]);
        vis[node] = true;

        transfer[0].clear();
        transfer[1].clear();
        nodes.clear();
        DFS2(node, 0);
        f[node][0] = g[node][0] = 1;
        for (int i = 1; i <= k; i++)
        {
            for (int j = 0; j < transfer[0].size(); j++)
            {
                const std::pair<int, int>& trans = transfer[0][j];
                add(f[trans.second][i], f[trans.first][i - 1]);
            }
            for (int j = 0; j < transfer[1].size(); j++)
            {
                const std::pair<int, int>& trans = transfer[1][j];
                add(g[trans.second][i], g[trans.first][i - 1]);
            }
        }
        for (int i = 0; i <= k; i++)
            add(ans[i], g[node][i]);
        for (int i = 1; i < nodes.size(); i++)
        {
            int t = nodes[i];
            for (int j = 0; j <= k; j++)
                for (int l = 0; l <= j; l++)
                    ans[j] = (ans[j] + (LL)f[t][l] * g[t][j - l]) % mod;
        }

        for (int i = 0; i < G[node].size(); i++)
        {
            int to = G[node][i];
            if (vis[to]) continue;
            solve(to);
        }
    }

    int ans[maxk];
    void run()
    {
        nodes.reserve(maxn);
        transfer[0].reserve(maxn * 2);
        transfer[1].reserve(maxn * 2);
        solve(1);
    }
    const int& operator[](int x) const { return ans[x]; }
} tree[2];

int C[maxk][maxk];
void init()
{
    C[0][0] = 1;
    for (int i = 1; i <= k; i++)
    {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
        {
            register int t;
            C[i][j] = (t = C[i - 1][j - 1] + C[i - 1][j]) >= mod ? t - mod : t;
        }
    }
}

void run()
{
    tree[0].resize(readIn());
    tree[1].resize(readIn());
    k = readIn();
    for (int i = 0; i < 2; i++)
    {
        tree[i].read();
        tree[i].run();
    }
    init();

    int ans = 0;
    for (int i = 0; i <= k; i++)
        add(ans, (LL)C[k][i] * tree[0][i] % mod * tree[1][k - i] % mod);
    printOut(ans);
}

int main()
{
    run();
    return 0;
}

总结

首先要知道如何用动态规划求解一般图走 k k $k$ 步的回路的方案数，然后要把这道题转化模型，前两步做出来后就能写出一个合法的暴力了。要想出点分治的方法，应该要从“贡献一起算”出发，进而想到从某个点出发引两条路径，把其中一条路径反转，进而想到点分治。

Remarks

我们还可以做得更好。由于这是在树上，考虑树形 DP，用与上面相同的思路来做。设 fi,j$f_{i,j}$$f_{i, j}$ 表示在以 i i $i$ 为根的子树中走 j$j$$j$ 步回到 i i $i$ 且中途不回到 i$i$$i$ 的方案数，设 gi,j g i , j $g_{i, j}$ 表示在以 i i $i$ 为根的子树中走 j$j$$j$ 步回到 i i $i$ 且中途可以回到 i$i$$i$（但不能继续往上走）的方案数。注意到，由于 DP 时必须先下去，再上来，因此 j j $j$ 一定为偶数，我们可以将 j$j$$j$ 除以二。

在已知儿子的 f f $f$ 的情况下，g$g$$g$ 显然可以通过枚举第一个“花瓣”所在子树求得，这与前面的方法是一样的。考虑如何求 f f $f$，显然需要选一棵子树走，走到子树的根结点后剩下的步数任其它们在子树中走，因此答案为所有子树的 g$g$$g$ 之和。

现在我们求出了以 1 1 $1$ 为根结点的 f$f$$f$ 和 g g $g$，g1$g_1$$g_1$ 显然就是 1 1 $1$ 的答案。考虑换根 DP。现在实际上是要让结点 u$u$$u$ 加一棵子树，再求出结点 u u $u$ 对应的以它为根的 g$g$$g$。如果我们求出了以它的父结点为根并且不走 u u $u$ 时走任意多个花瓣的方案数，那么问题就解决了。我们在从上往下 DP 时，假设自己已经有自己父结点的信息。先减去子结点的信息，然后求出子结点需要的父结点的信息，再还原原来子结点的信息，就能做了。（有点抽象，不过这是换根 DP 的难点）

总的来说，由于题目给的是树，因此树形 DP 的做法应该更容易得到启发？主要是能不能做出来的问题。时间复杂度为 O(nk2)$O(n{k}^2)$$O(n k^2)$。

参考代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
    putchar('\n');
}

const int mod = 998244353;
inline void add(int& a, const int& b)
{
    register int t;
    a = (t = a + b) >= mod ? t - mod : t;
}
inline void sub(int& a, const int& b)
{
    register int t;
    a = (t = a - b) < 0 ? t + mod : t;
}
const int maxn = 4005;
const int maxk = 40;
int m;
typedef std::vector<std::vector<int> > Graph;
struct Tree
{
    int n;
    Graph G;
    void resize(int size)
    {
        n = size;
        G.resize(size + 1);
    }
    void read()
    {
        for (int i = 2; i <= n; i++)
        {
            int from = readIn();
            int to = readIn();
            G[from].push_back(to);
            G[to].push_back(from);
        }
    }

    int f[maxn][maxk];
    int g[maxn][maxk];
    int h[maxn][maxk];

    void DP1(int node, int parent)
    {
        for (int i = 0; i < G[node].size(); i++)
        {
            int to = G[node][i];
            if (to == parent) continue;
            DP1(to, node);
            for (int j = 0; j <= m; j++)
                add(f[node][j], g[to][j]);
        }

        g[node][0] = 1;
        for (int i = 1; i <= m; i++)
            for (int j = 0; j < i; j++)
                g[node][i] = (g[node][i] + (LL)f[node][j] * g[node][i - j - 1]) % mod;
    }
    void DP2(int node, int parent)
    {
        for (int i = 0; i < G[node].size(); i++)
        {
            int to = G[node][i];
            if (to == parent) continue;
            for (int j = 0; j <= m; j++)
                sub(f[node][j], g[to][j]);

            std::memset(g[node], 0, sizeof(g[node]));
            g[node][0] = 1;
            for (int j = 1; j <= m; j++)
                for (int k = 0; k < j; k++)
                    g[node][j] = (g[node][j] + (LL)f[node][k] * g[node][j - k - 1]) % mod;
            for (int j = 0; j <= m; j++)
                add(f[to][j], g[node][j]);

            for (int j = 0; j <= m; j++)
                add(f[node][j], g[to][j]);

            h[to][0] = 1;
            for (int j = 1; j <= m; j++)
                for (int k = 0; k < j; k++)
                    h[to][j] = (h[to][j] + (LL)f[to][k] * h[to][j - k - 1]) % mod;

            DP2(to, node);
        }
    }

    void run()
    {
        DP1(1, 0);
        std::memcpy(h[1], g[1], sizeof(h[1]));
        DP2(1, 0);
        for (int i = 0; i <= m; i++)
            for (int j = 1; j <= n; j++)
                add(ans[i], h[j][i]);
    }

    Tree() : f(), g(), h() {}

    int ans[maxk];
    const int& operator[](int x) const { return ans[x]; }
} tree[2];

int C[maxk * 2][maxk * 2];
void init()
{
    C[0][0] = 1;
    for (int i = 1; i <= m; i++)
    {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
        {
            register int t;
            C[i][j] = (t = C[i - 1][j - 1] + C[i - 1][j]) >= mod ? t - mod : t;
        }
    }
}

void run()
{
    tree[0].resize(readIn());
    tree[1].resize(readIn());
    m = readIn();
    if (m & 1)
    {
        printOut(0);
        return;
    }
    init();
    m >>= 1;
    for (int i = 0; i < 2; i++)
    {
        tree[i].read();
        tree[i].run();
    }

    int ans = 0;
    for (int i = 0; i <= m; i++)
        add(ans, (LL)C[m << 1][i << 1] * tree[0][i] % mod * tree[1][m - i] % mod);
    printOut(ans);
}

int main()
{
    run();
    return 0;
}