cf954H

挖我自闭了这是什么东西啊。

 表示对于在  层的  个节点，向下走  步的方案数

 表示对于在  层的  个节点，向上走  步的方案数

然后我们可以得到这样的递推式。

 f[i][j]=a[i]*f[i+1][j-1]);

g[i][j]=(j>=2)*(a[i-1]-1)*f[i][j-2]+g[i-1][j-1])；

显然对于一条路径会算两次。所以最终答案除以 2

 即可。
你以为这就完了？
下面才是自闭的开始。
256M大概能开6e7？记不清了。。。所以我们只能开一个[5000][9999]这样纸的数组，然后滚来滚去滚来滚去。
ac代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int mod = 1e9+;

 int n;

 int a[],c[];

 int f[][],ans[];

 int main(){

     ios::sync_with_stdio(false);

     cin>>n;c[]=;

     for(int i=;i<n;i++)cin>>a[i];

     for(int i=;i<=n;i++)c[i]=1ll*a[i]*c[i-]%mod;

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

         f[i][]=;

         for(int j=;j<=n-i;j++){

             f[i][j]=(1ll*a[i]*f[i+][j-])%mod;

             ans[j]=(1ll*f[i][j]*c[i-]+ans[j])%mod;

         }

     }

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

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

             f[i][j]=f[i-][j-];

             if(i>&&j>)

                 f[i][j]=(1ll*(a[i-]-)*f[i][j-]+f[i][j])%mod;

             ans[j]=(1ll*f[i][j]*c[i-]+ans[j])%mod;

         }

     }

     for(int i=;i<=*n-;i++){

         cout<<(mod+1ll)*ans[i]/%mod<<' ';

     }

 }

MLE ON TEST 01 代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int mod = 1e9+;

 int n;

 int a[];

 int f[][],g[][];

 int main(){

     ios::sync_with_stdio(false);

     cin>>n;a[]=;

     for(int i=;i<n;i++)cin>>a[i];

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

        f[i][]=a[i],f[i][]=;

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

         g[i][]=,g[i][]=;

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

         for(int j=;j<=n-i;j++){

             f[i][j]=(1ll*a[i]*f[i+][j-])%mod;

         }

     }

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

         for(int j=;j<=*n-;j++){

             g[i][j]=(1ll*(j>=)*(a[i-]-)*f[i][j-]+g[i-][j-])%mod;

         }

     }

     for(int i=;i<=n;i++)a[i]=1ll*a[i]*a[i-]%mod;

     for(int i=;i<=*n-;i++){

         ll sum = ;

         for(int j=;j<=n;j++){

             sum=(sum+1ll*a[j-]*(f[j][i]+g[j][i])%mod)%mod;

         }

         cout<<sum/<<' ';

     }

 }