题解：P8478 「GLR-R3」清明

· · 题解

一个 m+1\geq \dfrac{n}{2} 时的 poly 复杂度做法。

首先拆贡献：

\sum_v\prod_{i}a'_i=\sum_v\prod_{i}\sum_{j=i-m}^i v_{j\to i}=\sum_v\sum_{fa_i\in[i-m,i]}\prod_i v_{fa_i\to i}

也就是先给每个点钦定一个父亲然后求乘积，这个值显然只和每个点的儿子个数有关：

令点 i 的权值为 v，假设有 deg 个儿子，[i,\min(n,i+m)] 一共有 lim 个点。需要计算的就是 deg 个儿子算入乘积，剩下 lim-deg 不算入乘积的权值之和：

[x^v](\dfrac{x}{(1-x)^2})^{deg}\cdot (\dfrac{1}{1-x})^{lim-deg}=[x^{v-deg}]\dfrac{1}{(1-x)^{lim+deg}}=\dbinom{v+lim-1}{lim+deg-1}

由于 a_i 比较大但 n 比较小，可以 O(n) 地暴力计算组合数。故可以在 O(n^3) 的复杂度内预处理该权值，记其为 val_{i,deg}。现在计算的就是：

\sum_{fa_i\in[i-m,i]}\prod_i {val_{i,deg_i}}

那么在 m 比较小的时候，显然可以状压 DP，直接枚举子集的复杂度为 O(n3^m)，用子集卷积可以做到 O(nm^22^m)，在本题的数据范围下没有必要。

当 m+1\geq \dfrac{n}{2} 时，考虑把 0\sim m 放在第一行，m+1\sim n 放在第二行。每个点的 fa 的取值就是它同行前面的点，或者上一行后面的点。

考虑从后往前按列进行一个 DP：dp_{i,x,y,z} 表示考虑了 [i,m] 这些列；第一个有 x 个选择同行匹配，且还未匹配的；第二个有 y 个选择同行匹配，且还未匹配的；钦定 [0,i) 中有 z 个异行匹配的；其权值之和。按第一行和第二行分开转移：

第一行即枚举同行的儿子个数 p，异行的儿子个数 q，系数为 val_{i,p+q}\cdot \dbinom{x}{p}\cdot \dbinom{z+q}{q}。

第二行枚举同行的儿子个数 p，系数为 val_{i,p}\cdot\dbinom{y}{p}。

分讨一下 i 这个点的匹配情况，这是简单的。

复杂度看着是 O(m^6) 的，但实际转移数是非常少的，在本题的数据范围下最多只跑了 16ms。

#define N 40
int n, m;
int a[N], inv[200];
int val[N][N];
int C(int n, int m)
{
    int res = 1;
    for(int i = n; i >= n - m + 1; i--) mul_(res, i % mod);
    for(int i = 1; i <= m; i++) mul_(res, inv[i]);
    return res;
}

namespace Sub1
{
int dp[2][1 << 16], pp[1 << 16], op;
int tmp[N];
void solve()
{
    // debug("Sub1\n");
    dp[op = 0][0] = 1;
    for(int i = 0; i < (1 << m); i++) pp[i] = pp[i >> 1] + (i & 1);
    for(int i = n - 1; ~i; i--)
    {
        op ^= 1;
        for(int S = 0; S < (1 << m); S++) if(dp[op ^ 1][S])
        {
            int v = dp[op ^ 1][S]; dp[op ^ 1][S] = 0;
            for(int j = 0; j <= std::min(m + 1, n - i); j++) tmp[j] = 1ll * v * val[i][j] % mod;
            int U = S, X = 0;
            if(S >> (m - 1) & 1)
                U ^= 1 << (m - 1), X ^= 1 << (m - 1);
            for(int _T = U, T; ; _T = (_T - 1) & U)
            {
                T = _T | X;
                plus_(dp[op][(S ^ T) << 1 | 1], tmp[pp[T]]);
                plus_(dp[op][(S ^ T) << 1], tmp[pp[T] + 1]);
                if(!_T) break;
            }
        }
    }
    print(dp[op][0], '\n');
}
}

namespace Sub2
{
int dp[2][N][N][N], op;
int C[N][N];
void solve()
{
    // debug("Sub2\n");
    for(int i = 0; i < N; i++) for(int j = C[i][0] = C[i][i] = 1; j < i; j++)
        C[i][j] = sm(C[i - 1][j - 1] + C[i - 1][j]);
    dp[op][0][0][0] = 1;
    for(int i = m; i >= 0; i--)
    {
        if(i + m + 1 < n)
        {
            op ^= 1;
            for(int x = 0; x <= m - i; x++) for(int y = 0; y <= m - i; y++) for(int z = 0; z <= i + 1; z++) if(dp[op ^ 1][x][y][z])
            {
                int v = dp[op ^ 1][x][y][z]; dp[op ^ 1][x][y][z] = 0;   
                for(int p = 0; p <= y; p++)
                {
                    // 连自环
                    plus_(dp[op][x][y - p][z], 1ll * v * val[i + m + 1][p + 1] % mod * C[y][p] % mod);
                    // 向前连
                    plus_(dp[op][x][y - p + 1][z], 1ll * v * val[i + m + 1][p] % mod * C[y][p] % mod);
                    // 向上连
                    if(z) plus_(dp[op][x][y - p][z - 1], 1ll * v * val[i + m + 1][p] % mod * C[y][p] % mod);
                }
            }   
        }
        if(i < n)
        {
            op ^= 1;
            for(int x = 0; x <= m - i; x++) for(int y = 0; y <= m - i + 1; y++) for(int z = 0; z <= i + 1; z++) if(dp[op ^ 1][x][y][z])
            {
                int v = dp[op ^ 1][x][y][z]; dp[op ^ 1][x][y][z] = 0;   
                for(int p = 0; p <= x; p++) for(int q = 0; z + q <= m; q++)
                {
                    // 连自环
                    plus_(dp[op][x - p][y][z + q], 1ll * v * val[i][p + q + 1] % mod * C[x][p] % mod * C[z + q][q] % mod);
                    // 向前连
                    plus_(dp[op][x - p + 1][y][z + q], 1ll * v * val[i][p + q] % mod * C[x][p] % mod * C[z + q][q] % mod);
                }
            }
        }
    }
    print(dp[op][0][0][0], '\n');
}
} // namespace Sub2


void solve()
{
    // memset(h, idx = -1, sizeof(h));
    n = read(), m = read();
    for(int i = 0; i < n; i++) a[i] = read();
    for(int i = 0; i < n; i++) 
    {
        int lim = std::min(m + 1, n - i);
        for(int j = 0; j <= lim; j++) val[i][j] = C(a[i] + lim - 1, lim + j - 1);
    }
    if(m + m + 2 < n) Sub1::solve();
    else Sub2::solve();
}