[hiho1952]运算数

可以发现如果将根的结果写成多项式，可以发现只需要预处理出f[i][j]表示以i为根的子树j次项有多少个，g[i]表示从n个数中选取i个数相乘的和，就可以通过\sum_{i=1}^{n}f[1][i]\cdot g[i]\cdot (n-i)!$计算。可以发现有递推式：$g[i]=g[i-1]\cdot i\cdot \sum_{i=1}^{n}a[j]$，当符号是+，f[i][j]=f[ls][j]+f[rs[j]]；当符号是*，$f[i][j]=\sum\limits_{k=1}^{j-1}f[ls][k]\cdot f[rs][j-k]$；当是叶子节点，f[i][j]=[j==1]。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define mod 1000000007

 4 #define N 6005

 5 long long n,p,ans,jc[N],a[N],x[N],y[N],sz[N],dp[N][N],f[N];

 6 char s[N][11];

 7 void dfs(int k){

 8     if (!x[k]){

 9         sz[k]=dp[k][1]=1;

10         return;

11     }

12     dfs(x[k]);

13     dfs(y[k]);

14     sz[k]=sz[x[k]]+sz[y[k]];

15     if (s[k][0]=='+')

16         for(int i=1;i<=sz[k];i++)dp[k][i]=(dp[x[k]][i]+dp[y[k]][i])%mod;

17     else

18         for(int i=1;i<=sz[x[k]];i++)

19             for(int j=1;j<=sz[y[k]];j++)dp[k][i+j]=(dp[k][i+j]+dp[x[k]][i]*dp[y[k]][j])%mod;

20 }

21 int main(){

22     scanf("%lld",&n);

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

24     f[0]=1;

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

26         for(int j=i;j>=0;j--)f[j]=(f[j]+j*f[j-1]%mod*a[i])%mod;

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

28         scanf("%lld",&p);

29         if (p==1)scanf("%lld%lld%s",&x[i],&y[i],s[i]);

30     }

31     jc[1]=1;

32     for(int i=2;i<=n;i++)jc[i]=jc[i-1]*i%mod;

33     dfs(1);

34     for(int i=1;i<=n;i++)ans=(ans+jc[n-i]*dp[1][i]%mod*f[i])%mod;

35     printf("%lld",ans);

36 }

巴特西

[hiho1952]运算数

最新文章

热门文章