豌豆射手

题目简述

$d$ 个格子排成一行，现在要在格子里放 $n$ 个点。对于第 $i$ 个点有一个值 $r_{i}$，使这个点左右两边 $r_{i}$ 的范围内都不能放点（这个点所在的格子也算在内）。$n≤40,\ d≤10^{5},\ 1≤r_{i}≤40,\ \sum_{i=1}^{n}r_{i}≤d$

思路

考虑一个不是很难想的暴力：暴搜从左往右点的顺序，顺序确定以后可以先把点排布得尽量紧密，然后将空出来的位置插到点的中间。由于点之间有距离的限制，所以对于现在已经确定的这个排列可以很简单地求出将点排布得尽量紧密之后所占的格子数就是 $len=\sum_{i=1}^{n-1}\max(r_{i},r_{i+1})$。剩下的格子插到点中间的方案数可以用组合数求出：$C_{d-len+n}^{n}$。

不难发现，当排列顺序相同时答案是唯一确定的，而排列顺序不同时 $len$ 的值会发生改变，答案变得不同了。着眼于点排布的结构，可以设出设这样的状态：$f_{i,j,k}$ 表示放了 $i$ 个点，它们分成了 $j$ 块，所占的位置共有 $k$ 格的方案数。

其中每一个「块」是指一些连续的点构成的一个整体，指定块中点与点之间不能再放点，而块外可以放点 —— 你可以将一个「块」理解为是一段确定了点的放置顺序和位置的格子 —— 但无论怎样理解，重点在于**「块」内的点间不能再插入新的点**。

将点按照 $r_{i}$ 从小到大排序，这样在新插入一个点的时候状态中 $k$ 的变化量只与新插入点的 $r$ 值有关 —— 事实上由于状态中没有记录每个块内的点排布，所以我们也无从枚举块边缘的点来计算对 $k$ 的贡献。而每个点在插入时所属于的块以及所处的位置都是不确定的，所以排序不会对答案产生影响。当插入第 $i+1$ 个点时，有以下几种情况：

这个点不依附于任何一个块，自成一块。这时候有 $\large f_{i+1,j+1,k+1}=f_{i+1,j+1,k+1}+f_{i,j,k}$
这个点加入已有的一个块。现在有 $j$ 个块，而每个块只有左右两边可以插点，所以有 $\large f_{i+1,j,k+r_{i+1}}=f_{i+1,j,k+r_{i+1}}+2j·f_{i,j,k}$
这个点链接了已有的两个块。现在有 $j$ 个块，块的位置是不确定的，所以任意一个块都可能是新插入的块旁边的块，新的点插入后块的数量减少了一个，于是有：$\large f_{i+1,j-1,k+2r_{i+1}-1}=f_{i+1,j-1,k+2r_{i+1}-1}+j·(j-1)·f_{i,j,k}$

插入的所有点并成一个块，答案是 $\large\sum_{i=0}^{\min(d,1600)}C_{d-i+n}^{n}·f_{n,1,i}$

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<climits>
#include<algorithm>
#define int long long
using namespace std;
const int MaxN = 42, MaxD = 100005, Mod = 1000000007;
int n, d, ans, r[MaxN], fac[MaxD], inv[MaxD], f[MaxN][MaxN][MaxN*MaxN];

inline int Read(){
	int num = 0, op = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') op = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		num = num * 10 + ch - '0';
		ch = getchar();
	}
	return num * op;
}

inline int QuickPower(int a, int b){
	int ans = 1;
	while(b){
		if(b&1) ans = ans * a % Mod;
		a = a * a % Mod;
		b >>= 1;
	}
	return ans;
}

inline void Init(){
	fac[0] = 1;
	for(int i=1; i<MaxD; i++)
		fac[i] = fac[i-1] * i % Mod;
	inv[MaxD-1] = QuickPower(fac[MaxD-1], Mod-2);
	for(int i=MaxD-2; i>=0; i--)
		inv[i] = inv[i+1] * (i+1) % Mod;
	return;
}

inline int C(int n, int m){
	return fac[n] * inv[m] % Mod * inv[n-m] % Mod;
}

signed main(){
	Init();
	n = Read(), d = Read();
	for(int i=1; i<=n; i++)
		r[i] = Read();
	sort(r+1, r+1+n);
	f[0][0][0] = 1;
	for(int i=0; i<=n; i++){
		for(int j=0; j<=i; j++){
			for(int k=0; k<MaxN*MaxN; k++){
				f[i+1][j+1][k+1] = (f[i+1][j+1][k+1] + f[i][j][k]) % Mod;
				if(j>0) f[i+1][j][k+r[i+1]] = (f[i+1][j][k+r[i+1]] + 2 * j * f[i][j][k]) % Mod;
				if(j>1) f[i+1][j-1][k+2*r[i+1]-1] = (f[i+1][j-1][k+2*r[i+1]-1] + j * (j-1) * f[i][j][k]) % Mod;
			}
		}
	}
	for(int i=0; i<=min(d, MaxN*MaxN); i++)
		ans = (ans + C(d-i+n,n) * f[n][1][i] % Mod) % Mod;
	printf("%lld", ans);
	return 0;
}