CF954H Path Counting

又是一道树上数路径条数，但是这题感觉蛮educational的。之前的题基本都是在LCA处统计这条路径的值，但是这次是在端点处统计。

首先，对于一个点$S$出发的长度为$k$路径有两种情况：向下或者向上。选择向下的话，路径条数是很容易求得，主要考虑第一步向上。

向上的之后又有两种情况：

• 接着向上
• 选择一个儿子向下（且不能选择S）

我们令$dp[s][i]$代表从点$S$开始第一步向上，走$i$步的方案数。第一种情况就可以直接转移了，而第二种情况也很好解决，不能选择S这个限制稍微处理下即可。

这道题主要是想到比较反套路的在端点初统计路径，其他的就很好想了。

/*
                                                  
  _|_|                              _|  _|    _|  
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|    
_|    _|  _|_|          _|          _|  _|_|      
_|    _|  _|          _|      _|    _|  _|  _|    
  _|_|    _|        _|_|_|_|    _|_|    _|    _|  
                                                                                                    
*/ 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=5005;
const int mod=1e9+7;
int a[maxn*2];
int prod[maxn*4];
int cnt(int dep){
	return prod[dep-1];
}
int invp[2*maxn];
int ksm(int num,int t){
	int res=1;
	for(;t;t>>=1,num=1ll*num*num%mod){
		if(t&1)res=1ll*res*num%mod;
	}
	return res;
}
int down(int lev,int len){
	//a[lev]*a[lev+1]*...*a[lev+len-1]
	return (1ll*prod[lev+len-1]*invp[lev-1]%mod);
}
int dp[maxn][2*maxn];
int inv[2*maxn];
int ans[2*maxn];
int main(){
	ios::sync_with_stdio(0);
	int n;cin>>n;int lim=2*n-2;
	prod[0]=1;
	rep(i,1,n-1)cin>>a[i],prod[i]=1ll*prod[i-1]*a[i]%mod,inv[i]=ksm(a[i],mod-2);
	rep(i,0,n)invp[i]=ksm(prod[i],mod-2);
	rep(i,1,n)dp[i][0]=1;
	rep(i,2,n)rep(k,1,lim){
		dp[i][k]=dp[i-1][k-1];
		if(k>=2)dp[i][k]=(dp[i][k]+1ll*down(i-1,k-1)*inv[i-1]%mod*(a[i-1]-1)%mod)%mod;
	}int inv2=ksm(2,mod-2);
	rep(i,1,n)rep(j,1,lim){
		ans[j]=(ans[j]+1ll*(dp[i][j]+down(i,j))*cnt(i))%mod;
	}
	rep(i,1,lim)ans[i]=(1ll*ans[i]*inv2%mod+mod)%mod;
	rep(i,1,lim)cout<<ans[i]<<' ';
	return 0;
}