题意:
有 \(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]);
}