Codeforces 954H Path Counting 【DP计数】*

时间：2024-01-18 13:05:08

Codeforces 954H Path Counting

LINK

题目大意：给你一棵n层的树，第i层的每个节点有a[i]个儿子节点，然后问你树上的简单路径中长度在1~n*2-2之间的每个有多少条

因为直接计算过每个节点的路径并不好算
所以可以算一算从每个节点出发的路径的个数
f[i][j]表示对于在i层的1个节点，向下走行走j步的方案数
g[i][j]表示对于在i层的1个节点，第一步向上行走共走j步的方案数

然后DP式子比较显然
f[i][j]=a[i]∗f[i+1][j−1]
g[i][j]=g[i−1][j−1]+[2≤j]∗f[i][j−2]
然后这样每条路径会在计算的时候被计算两次，所以乘上2的逆元就好了

但是这样会MLE，就很完蛋

然后我们发现g式子DP的时候f只会用到i相等，j比他小的
又因为g的DP式子中是i从小到大来转移的
所以直接在f上进行修改，i从小到大，j从大到小，然后就不会卡空间了

也可以滚动，不过要处理一堆东西，懒得写

 #include<bits/stdc++.h>

 using namespace std;

 #define N 5010

 #define Mod 1000000007

 #define inv2 500000004

 int f[N][N<<];

 int n,a[N],s[N];

 int ans[N<<]={};

 int add(int a,int b){return (a+b)%Mod;}

 int mul(int a,int b){return 1ll*a*b%Mod;}

 int main(){

     scanf("%d",&n);

     for(int i=;i<n;i++)scanf("%d",&a[i]);

     s[]=;for(int i=;i<=n;i++)s[i]=mul(s[i-],a[i-]);

     for(int i=;i<=n;i++)f[i][]=;

     for(int i=n-;i>=;i--)

         for(int k=;k<=n-;k++){

             f[i][k]=mul(a[i],f[i+][k-]);

             ans[k]=add(ans[k],mul(s[i],f[i][k]));

         }

     for(int i=;i<=n;i++)f[][i]=;

     for(int i=;i<=n;i++)

         for(int k=n*-;k>=;k--){

             f[i][k]=f[i-][k-];

             if(k>=)f[i][k]=add(f[i][k],mul(a[i-]-,f[i][k-]));

             ans[k]=add(ans[k],mul(s[i],f[i][k]));

         }

     for(int i=;i<=n*-;i++)printf("%d ",mul(ans[i],inv2));

     return ;

 }

相关文章