题解：CF954H Path Counting

· · 题解

更好的阅读体验

这么简单的题哪里有 *2500 啊 /fn

一条路径的形态和两个端点的 LCA 有关。路径总共有两种情况：LCA 在端点上、LCA 不在端点上。

我们发现深度为 x 的节点共有 \prod \limits_{i = x}^{x + y - 1}a_i 个 y 辈后代。对于第一种情况，计算链长为 t 的答案时，我们可以枚举链上端的深度，计算出下端的情况数。而当下端节点和链长固定后，上端也是固定的。所以有：

ans_t \leftarrow ans_t + \sum _{i=1}^{n-t}\prod_{j=1}^{i+t-1}a_j

对于第二种情况，计算链长为 t 的答案时，我们可以枚举 LCA 的深度，再枚举链的一端时 LCA 的多少辈后代。假设 mul_i = \prod \limits_{j=1}^{i}a_j，则 LCA 深度为 i 时，共有 mul_{i-1} 种满足条件的 LCA，从 LCA 选取两个不同的子树共有 a_i \choose 2 种情况。

此时再设一端是 LCA 的 j 辈后代，则是 LCA 直系儿子的 j-1 辈后代，方案数为 \frac{mul_{i+j-1}}{mul_i}；另一端为 LCA 直系儿子的 t-j-1 辈后代，方案数为 \frac{mul_{i+t-j+1}}{mul_i}。

因此有：

ans_t \leftarrow ans_t + \sum_{i=1}^{n-1}mul_{i-1} {a_i \choose 2} \sum_{j=1}^{t-1} \frac{mul_{i+j-1}mul_{i+t-j+1}}{mul_i^2}

把分母移出来，就变成：

ans_t \leftarrow ans_t + \sum_{i=1}^{n-1}\frac{mul_{i-1}}{mul_i^2} {a_i \choose 2} \sum_{j=1}^{t-1} mul_{i+j-1}mul_{i+t-j+1}

直接做是 O(n^3) 的，但可以取：

f_{t, i}=\sum_{j=1}^{t-1} mul_{i+j-1}mul_{i+t-j+1}

发现把求和符号展开后式子变成 mul_{i}mul_{i+t-2}+mul_{i+1}mul_{i+t-3}+mul_{i+2}mul_{i+t-4}+\cdots。考虑取 i' = i+1, t' = t-2，则 f_{t',i'} 可以展开成 mul_{i+1}mul_{i+t-3}+mul_{i+2}mul_{i+t-4}+\cdots。容易发现，这两个式子只差一个项，因此 f_{t,i} 可以由 f_{t-2,i+1} 递推而来。具体地，有：

f_{t,i}=f_{t-2,i+1}+2mul_{i}mul_{i+t-2}

可以 O(n^2) 预处理。

那么这道题就做完了，可以预处理前缀积和逆前缀积，复杂度为 O(n^2)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 5006
#define MOD 1000000007
using namespace std;
int n,a[N],mul[N<<2],imul[N<<2],ans[N<<2],f[N<<1][N];
inline void add(int &x,int y){x+=y,x-=x>=MOD?MOD:0;}
int qpow(int x,int y)
{
    if(y==0)return 1;if(y==1)return x%MOD;
    int ret=qpow(x,y>>1);return 1ll*ret*ret%MOD*qpow(x,y&1)%MOD;
}
int binom2(int x){return (1ll*x*(x-1)/2)%MOD;}
main()
{
    scanf("%d",&n),mul[0]=1;
    for(int i=1;i<n;i++)
        scanf("%d",&a[i]),mul[i]=1ll*mul[i-1]*a[i]%MOD;
    imul[n-1]=qpow(mul[n-1],MOD-2);
    for(int i=n-2;~i;i--)imul[i]=1ll*imul[i+1]*a[i+1]%MOD;
    for(int t=1;t<=2*n-2;t++)
        for(int i=1;i<n;i++)add(ans[t],mul[i+t-1]);
    for(int i=n-1;i;i--)
    {
        f[2][i]=1ll*mul[i]*mul[i]%MOD;
        for(int t=3;t<=2*n-2;t++)
            f[t][i]=(f[t-2][i+1]+2ll*mul[i]*mul[i+t-2]%MOD)%MOD;
    }
    for(int t=1;t<=2*n-2;t++)
        for(int i=1;i<n;i++)
            add(ans[t],1ll*mul[i-1]*imul[i]%MOD*imul[i]%MOD*binom2(a[i])%MOD*f[t][i]%MOD);
    for(int i=1;i<=2*n-2;i++)
        printf("%d ",ans[i]);
    return 0;
}