bzoj4574:Zjoi2016线段树 dp

传送门

题解传送门

//Achen

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<vector>

#include<cstdio>

#include<queue>

#include<cmath>

using namespace std;

const int N=;

#define mo 1000000007

int n,q,x[N],y[N],rank[N];

int cnt[N],A[N][N];long long dp[][N][N],sum[N][N];

bool mycmp(int a,int b) { return x[a]<x[b]; }

void init() {

    scanf("%d%d",&n,&q);

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

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

      sort(y+,y++n,mycmp);

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

      return ;

}

#define dp(i,j,k) dp[(i)%2][j][k]

void solve(int l,int r,int now) {

    for(int i=l;i<=r;i++) for(int j=l;j<=r;j++)dp(,i,j)=dp(,i,j)=;

      dp(,l,r)=;

      long long ct;

      for(int k=;k<=q;k++) {

        for(int i=l;i<=r;i++) {

              ct=;

              for(int j=r;j>=i;j--) {

                dp(k,i,j)=ct; ct=(ct+dp(k-,i,j)*(n-j))%mo;

              }

        }

            for(int j=l;j<=r;j++) {

              ct=;

              for(int i=l;i<=j;i++) {

                dp(k,i,j)=(dp(k,i,j)+ct)%mo; ct=(ct+dp(k-,i,j)*(i-));

              }

        }

        for(int i=l;i<=r;i++) {

              for(int j=i;j<=r;j++) {

                    dp(k,i,j)=(dp(k,i,j)+(dp(k-,i,j)*A[i][j]))%mo;

            }

           }

      }

    for(int i=l;i<=r;i++) {

           ct=;

        for(int j=r;j>=i;j--) {

              ct=(ct+dp(q,i,j));

              sum[j][rank[now]]=(ct+sum[j][rank[now]])%mo;

        }

      }

      return ;

}

int main() {

#ifdef DEBUG

    freopen(".in","r",stdin);

    freopen(".out","w",stdout);

#endif

    init();

    int l,r;

    for(int i=;i<=n;i++)  cnt[i]=i*(i+)/;

    for(int i=;i<=n;i++) for(int j=i;j<=n;j++) A[i][j]=cnt[i-]+cnt[n-j]+cnt[j-i+];

    memset(sum,,sizeof(sum));

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

           l=r=i;

        while(l && x[l]<=x[i])l--; while(r<=n && x[r]<=x[i])r++;

        solve(l+,r-,i);

    }

    int ans;

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

        ans=;

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

              if(!sum[i][j])continue;

              for(int u=;u<j;u++)sum[i][j]=(sum[i][j]-sum[i][u])%mo;

              ans=((long long)ans+1ll*x[y[j]]*sum[i][j])%mo;

        }

        ans=(ans+mo)%mo;

        if(i!=n) printf("%d ",ans);else printf("%d",ans);

      }

  return ;

}