Codeforces 954H Path Counting

令输入的为 \(a'\)，同时 \(a'_0 = 1\)。
对其做一个前缀积 \(a_i = \prod\limits_{i = 0}^i a'_i\)，对于 \(i\ge n\)，认为 \(a_i = 0\)。
那么 \(a_i\) 就相当于是深度 \(i + 1\) 的点的个数。
同时也可以得到根的深度为 \(l\) 时子树内深度为 \(r\) 的深度的点数为 \(\dfrac{a_{r - 1}}{a_{l - 1}}\)。

考虑固定了距离为 \(d\) 来算。
那么有两种情况：

1. 两点为祖先关系，那么考虑到深度 \(\ge d + 1\) 的点都能找到其祖先。
   所以贡献就为 \(\sum\limits_{i = d}^{n - 1} a_i\)。
2. 两点不为祖先关系，考虑枚举 \(\text{LCA}\) 的深度 \(i\)，那么就会有 \(a_{i - 1}\) 个点。
   首先这两个点不能为祖先关系，所以对于 \(\text{LCA}\)，这两个点一定在其两个不同的儿子的子树中，这部分的方案数就为 \(\binom{a'_i}{2} = \binom{\frac{a_i}{a_{i - 1}}}{2}\)。
   然后考虑枚举其中一个点的深度为 \(i + j(1\le j < d)\)，那么另一个点的深度就为 \(i + d - j\)，那么方案数就为 \(\dfrac{a_{i + j - 1} a_{i + d - j - 1}}{a_i^2}\)。
   于是方案数就相当于是 \(\sum\limits_{i = 1}^{n - 1} a_{i - 1}\binom{\frac{a_i}{a_{i - 1}}}{2}\frac{1}{a_i^2}\sum\limits_{1\le j < d} a_{i + j - 1} a_{i + d - j - 1}\)。

考虑优化第二部分。
能发现主要是 \(\sum\limits_{1\le j < d} a_{i + j - 1} a_{i + d - j - 1}\) 这部分每次都需要 \(\mathcal{O}(n)\) 的复杂度，考虑优化这部分。
令 \(f_{i, d} = \sum\limits_{1\le j < d} a_{i + j - 1} a_{i + d - j - 1}\)，能发现这也就是 \(\sum\limits_{x, y\ge i, x + y = 2i + d - 2} a_x a_y\)。
初始情况显然有 \(f_{i, 1} = 0, f_{i, 2} = a_i^2\)。
对于 \(d\ge 3\)，考虑 \(f_{i + 1, d - 2} = \sum\limits_{x, y\ge i + 1, x + y = 2i + d - 2} a_x a_y\)，能发现 \(f_{i, d} - f_{i + 1, d - 2} = a_i a_{i + d - 2} + a_{i + d - 2} a_i = 2a_i a_{i + d - 2}\)，所以有 \(f_{i, d} = f_{i + 1, d - 2} + 2a_i a_{i + d - 2}\)，便可以 \(\mathcal{O}(1)\) 递推了。

注意到 \(f_{i, d}\) 的递推只与 \(f_{i + 1, d + 2}\) 有关，可以把 \(d\) 这一维压成 \(0 / 1\)。

时间复杂度 \(\mathcal{O}(n^2)\)。

#include<bits/stdc++.h>
using ll = long long;
const ll mod = 1e9 + 7;
inline ll binom2(ll n) {
   return n * (n - 1) / 2 % mod;
}
inline ll qpow(ll a, ll b, ll v = 1) {
   while (b) {
      if (b & 1) (v *= a) %= mod;
      b >>= 1, (a *= a) %= mod;
   }
   return v;
}
const int maxn = 5e3 + 10;
ll a[maxn], inva[maxn];
ll f[maxn][2];
int main() {
   int n;
   scanf("%d", &n);
   int m = 2 * n - 2;
   a[0] = 1;
   for (int i = 1; i < n; i++)
      scanf("%lld", &a[i]);
   for (int i = 1; i < n; i++)
      (a[i] *= a[i - 1]) %= mod;
   for (int i = 0; i < n; i++)
      inva[i] = qpow(a[i], mod - 2);
   for (int d = 1; d <= m; d++) {
      ll ans = 0;
      for (int i = 1; i + d <= n; i++)
         (ans += a[i + d - 1]) %= mod;
      if (d == 1);
      else if (d == 2) {
         for (int i = 1; i < n; i++)
            f[i][d & 1] = a[i] * a[i] % mod;
      } else {
         for (int i = 1; i < n; i++) {
            f[i][d & 1] = f[i + 1][d & 1];
            if (i + d - 1 <= n)
               (f[i][d & 1] += 2ll * a[i] * a[i + d - 2]) %= mod;
         }
      }
      for (int i = 1; i < n; i++)
         (ans += f[i][d & 1] % mod * inva[i] % mod * inva[i] % mod
                 * binom2(a[i] * inva[i - 1] % mod) % mod * a[i - 1] % mod) %= mod;
      printf("%lld ", ans);
   }
   return 0;
}