SP3734题解

题意：

有 \(n\) 列表格，第 \(i\) 列有 \(a_i\) 个格子，问在 \(n\) 列表格中有多少种放置 \(k\) 个棋子的方法使没有棋子在同一列和同一行。（如果中间有一个“格子”是空的，那么不算在同一行）

思路很妙。

如果所有 \(a_i\) 都相等（一个矩形），答案明显是 \(\binom {a_i} k \times \binom n k \times k!\)。

我们发现这个问题棘手的地方在于不能在同一行，所以考虑将答案分为两部分：

去掉最下面的矩形后，剩下两块不规则图形的答案
最下面的矩形

然后我们发现不会做。。。

你不会做的题很可能是DP。

考虑 DP，设 \(dp[u][k]\)表示以 \(u\) 为分治中心时，放置 \(k\) 个棋子的方案数。

对于两块不规则图形的答案，合并这一部分的答案类似一个背包 DP。

最下面的矩形明显可以直接计算其答案。

于是我们就做完了。。。

对于找最小值，我们发现只需要对序列建笛卡尔树就能很方便地找到最小值。ST表也可以，只不过是 \(O(n\log n)\) 的。

复杂度为 \(O(n^2k)\)

#include<cstdio>

typedef long long ll;

const int M=505,mod=1e9+7;

int n,k,a[M],L[M],R[M],siz[M],dp[M][M];

int fac[1000005],ifac[1000005];

int top,stk[M];

inline int Add(const int&a,const int&b){

	return a+b>=mod?a+b-mod:a+b;

}

inline void init(const int&M){

	register int i;fac[0]=fac[1]=ifac[0]=ifac[1]=1;

	for(i=2;i<=M;++i){

		fac[i]=1ll*fac[i-1]*i%mod;

		ifac[i]=1ll*(mod-mod/i)*ifac[mod%i]%mod;

	}

	for(i=2;i<=M;++i)ifac[i]=1ll*ifac[i]*ifac[i-1]%mod;

}

inline int C(const int&n,const int&m){

	return m>n?0:1ll*ifac[m]*ifac[n-m]%mod*fac[n]%mod;

}

void DFS(int u,int f){

	if(!u)return;

	register int i,j,tmp;

	DFS(L[u],u);DFS(R[u],u);siz[u]=siz[L[u]]+siz[R[u]]+1;

	for(i=0;i<=siz[L[u]];++i){

		for(j=0;j<=siz[R[u]];++j){

			dp[u][i+j]=Add(dp[u][i+j],1ll*dp[L[u]][i]*dp[R[u]][j]%mod);

		}

	}

	for(i=siz[u];i>=0;--i){

		tmp=0;

		for(j=0;j<=i;++j){

			tmp=Add(tmp,1ll*dp[u][j]*fac[i-j]%mod*C(a[u]-a[f],i-j)%mod*C(siz[u]-j,i-j)%mod);

		}

		dp[u][i]=tmp;

	}

}

signed main(){

	register int i;

	scanf("%d%d",&n,&k);dp[0][0]=1;init(1e6);

	for(i=1;i<=n;++i)scanf("%d",a+i);

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

		if(top&&a[i]<=a[stk[top]]){

			while(top&&a[i]<=a[stk[top]])R[stk[top-1]]=stk[top],--top;

			L[i]=stk[top+1];

		}

		stk[++top]=i;

	}

	while(top)R[stk[top-1]]=stk[top],--top;

	DFS(stk[1],0);

	printf("%d",dp[stk[1]][k]);

}

巴特西

SP3734题解

最新文章

热门文章