Bzoj4498 魔法的碰撞

Description

https://hydro.ac/d/bzoj/p/4498

Solution

考虑一个排列紧密的布阵方案，令长度为 $k$ ，把其 $L-k$ 的盒子中，插入 $n$ 个板，方案为 $\dbinom{L-k+n}{n}$。

现在要 dp 出所有的长度为 $k$ 的紧密排列的方案数。发现是很典的插入dp。但是这样写的话需要维护左右端点是否被选，细节很多。讲一下从指导那里学来的做法。

同样是从大到小选，令 $f_{i,j,k}$ 表示选了前 $i$ 个大的魔法师，预留了 $j$ 个位置，占了 $k$ 个格子。答案就是 $f_{n,0,k}$。讨论第 $i$ 个魔法师旁边预留 0/1/2 个位置。

• 预留 $0$ 个位置，$f_{i,j,k}\gets f_{i-1,j+1,k}\times (j+1)$
• 预留 $1$ 个位置，还要选择预留是左边还是右边的位置，$f_{i,j,k}\gets f_{i-1,j,k-d_i}\times 2j$。
• 预留 $2$ 个位置，$f_{i,j,k}\gets f_{i-1,j-1,k-2d_i}\times (j-1)$。

其实和插入dp差不多，就是把维护段变成维护预留的位置。但是更好写。不用特判最左边和最右边端点的情况。

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 45
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int f[maxn][maxn][maxn*maxn];
int d[maxn],n,m,ans;
bool cmp(int x,int y) {return x>y;}
int suf[1000005],isuf[1000005];
int C(int x,int y) {return suf[x]*isuf[y]%mod*isuf[x-y]%mod;}
void add(int &x,int y) {x=(x+y)%mod;}
signed main(void){
	int i,j,k,t;
	read(m);read(n);
	for (i=1;i<=n;i++) read(d[i]);
	sort(d+1,d+1+n,cmp);
	for (suf[0]=1,i=1;i<=m;i++) suf[i]=suf[i-1]*i%mod;
	for (isuf[m]=power(suf[m]),i=m;i>=1;i--) isuf[i-1]=isuf[i]*i%mod;
	f[0][1][1]=1;
	int cnt=min(40*(40ll),m);
	for (i=1;i<=n;i++) {
		for (j=0;j<=n;j++) 
			for (k=0;k<=cnt;k++) {
				add(f[i][j][k],(j+1)*f[i-1][j+1][k]);
				if (k>=d[i]&&j) add(f[i][j][k],2ll*f[i-1][j][k-d[i]]*j);
				if (j>=1&&k>=2*d[i]) add(f[i][j][k],(j-1)*f[i-1][j-1][k-2*d[i]]);
			}
	}
	for (k=0;k<=cnt;k++) if (f[n][0][k]) add(ans,f[n][0][k]*C(m-k+n,n));
	printf("%lld",ans);
	return 0;
}