题解 SP3734 【PERIODNI

考虑用\(DP\)和组合数学来解决。

因为原图像不规则的形状不好处理，所以先用笛卡尔树（性质为小根堆）将其划分成一个一个的矩形。

发现在笛卡尔树上的每个节点都对应一个矩形，矩形高为\(h_x-h_{fa_x}\)，宽为\(size_x\)。

结合笛卡尔树的性质，不难得到，红色矩形所对应的节点的两个儿子为绿色矩形和蓝色矩形。

设\(f_{x,i}\)为在节点\(x\)所对应的矩形及其以上的图形中放\(i\)个点的方案数，那么答案为\(f_{root,k}\)

与子树合并时只需枚举在子树图像中放的点个数，再用乘法原理乘起来。

再考虑其本身的矩形。

若是在一个\(n \times m\)的矩形中放\(k\)个点，其方案数为\(C_{n}^kC_{m}^kk!\)，因为你需要从\(n\)行中选\(k\)行，从\(m\)列中选\(k\)列，同时这些选择的顺序可以改变，所以再乘上\(k!\)。

那么再考虑本身的矩形时，枚举在自身的矩形中放的点个数，再乘上\(C_{n}^kC_{m}^kk!\)即可

实现细节就看代码吧。

\(code:\)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define maxn 5010

#define mod 1000000007

template<typename T> inline void read(T &x)

{

	x=0;char c=getchar();bool flag=false;

	while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

	if(flag)x=-x;

}

ll n,k,top,root;

ll ls[maxn],rs[maxn],st[maxn];

ll f[maxn][maxn],h[maxn],siz[maxn],fac[1000050],inv[1000050];

ll qp(ll x,ll y)

{

    ll ans=1;

    while(y)

    {

        if(y&1) ans=(ans*x)%mod;

        x=(x*x)%mod;

        y>>=1;

    }

    return ans%mod;

}

void init()

{

    fac[0]=fac[1]=inv[0]=inv[1]=1;

	fac[2]=2,inv[2]=qp(2,mod-2);

	for(int i=3;i<=1000000;++i)

	{

		fac[i]=(fac[i-1]*i)%mod;

		inv[i]=qp(fac[i],mod-2);

	}

}

ll C(ll n,ll m)

{

    if(n<m) return 0;

    return fac[n]*inv[m]%mod*inv[n-m]%mod;

}

int build()

{

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

    {

        while(top&&h[st[top]]>h[i]) ls[i]=st[top--];

        if(top) rs[st[top]]=i;

        st[++top]=i;

    }

    return st[1];

}

void dfs(int x,int val)

{

    f[x][0]=siz[x]=1;

    ll high=h[x]-val;

    if(ls[x])

    {

        ll y=ls[x];

        dfs(y,h[x]),siz[x]+=siz[y];

        for(ll i=min(siz[x],k);i>=0;--i)

            for(ll j=1;j<=min(siz[y],i);++j)

                f[x][i]=(f[x][i]+f[y][j]*f[x][i-j]%mod)%mod;

    }

    if(rs[x])

    {

        ll y=rs[x];

        dfs(y,h[x]),siz[x]+=siz[y];

        for(ll i=min(siz[x],k);i>=0;--i)

            for(ll j=1;j<=min(siz[y],i);++j)

                f[x][i]=(f[x][i]+f[y][j]*f[x][i-j]%mod)%mod;

    }

    for(ll i=min(siz[x],k);i>=0;--i)

        for(ll j=1;j<=min(high,i);++j)

            f[x][i]=(f[x][i]+f[x][i-j]*fac[j]%mod*C(high,j)%mod*C(siz[x]-(i-j),j)%mod)%mod;

}

int main()

{

    init();

    read(n),read(k);

    for(int i=1;i<=n;++i) read(h[i]);

    root=build();

    dfs(root,0);

    printf("%lld",f[root][k]);

	return 0;

}

巴特西

题解 SP3734 【PERIODNI - Periodni】

最新文章

热门文章