#include <cstdio>
#include <algorithm>
using namespace std;
const int M = 105;
const int N = 1005;
const int MOD = 1e9+7;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,ans,a[M],f[M][M][N][3];
void add(int &x,int y) {x=(x+y)%MOD;}
signed main()
{
	n=read();m=read();
	if(n==1) {puts("1");return 0;}
	for(int i=1;i<=n;i++)
		a[i]=read();
	sort(a+1,a+1+n);
	f[0][0][0][0]=1;
	for(int i=0;i<n;i++) for(int j=0;j<=i;j++)
		for(int k=0;k<=m;k++) for(int d=0;d<=2;d++)
		{
			int kk=k+(2*j-d)*(a[i+1]-a[i]),t=f[i][j][k][d];
			if(kk>m || !t) continue;
			//Case1:insert an seg without forming boundary
			add(f[i+1][j+1][kk][d],t*(j+1-d));
			//Case2:merge two seg
			if(j) add(f[i+1][j-1][kk][d],t*(j-1));
			//Case3:add to a seg
			if(j) add(f[i+1][j][kk][d],t*(2*j-d));
			//Case4:insert an seg,forming boundary
			if(d<2) add(f[i+1][j+1][kk][d+1],t*(2-d));
			//Case5:add to a seg,forming boundary
			if(d<2 && j) add(f[i+1][j][kk][d+1],t*(2-d));
		}
	for(int i=0;i<=m;i++) add(ans,f[n][1][i][2]);
	printf("%lld\n",ans);
}

很套路的一道题。

题目大意

给定长为 $n$ 的序列 $a$，$a_i$ 互不相同。你要将其重排成 $f_1,f_2,\dots,f_n$，需要满足 $|f_1-f_2|+|f_2-f_3|+\dots+|f_{n-1}-f_n| \leq L$，求满足条件的重排方案数，对 $10^9+7$ 取模。

$1 \leq n \leq 100,1 \leq L,a_i \leq 1000$

题目分析

首先把重排后的序列 $f$ 拍到平面上，横坐标为下标，纵坐标为 $f_i$，如下图：

那么所要求的就是红线的（纵坐标差）长度和。容易想到从上往下扫，然后动态计算目前的折线长度和：

每次从大到小加入 $a_i$，那么新增加的折线就有 $2 \times$ 目前连续段数个（下图绿色部分）：

不过注意到当最后一个数已经插入时，后面不能再算贡献（绿色紫色虚线部分），同理，第一个数已经插入时前面不能再算贡献。于是设 $dp_{i,j,0/1,0/1}$ 表示目前已经有 $i$ 个连续段，答案为 $j$，第一个数/最后一个数有没有被加进去，答案就是 $dp_{1,\leq L,1,1}$。

转移的话大致有三种：

• 这个数新开了一个段，段数 $+1$。
• 这个数合并了两段，段数 $-1$。
• 这个数延续了其中一段，段数不变。

时间复杂度 $\mathcal O(n^2L)$，足以通过。

代码

#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
using namespace std;
ll n,lim,a[110],f[110][1010][2][2],g[110][1010][2][2],ans=0;
inline void inc(ll &x,ll y){
	((x+=y)>=mod)?(x-=mod):0;
}
int main(){
	scanf("%lld %lld",&n,&lim);
	fr(i,1,n) scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	reverse(a+1,a+n+1);//从大到小排序 
	fr(p,0,1) fr(q,0,1) f[1][0][p][q]=1;
	fr(i,2,n){
		fr(j,1,i-1) fr(k,0,lim) fr(p,0,1) fr(q,0,1) g[j][k][p][q]=f[j][k][p][q];
		fr(j,1,i-1) fr(k,0,lim) fr(p,0,1) fr(q,0,1) f[j][k][p][q]=0;
		fr(j,1,i-1){
			fr(k,0,lim){
				fr(p,0,1){
					fr(q,0,1){
						if(!g[j][k][p][q]) continue;
						ll kk=k+(2*j-p-q)*(a[i-1]-a[i]);
						if(kk>lim) continue;
						//新开一个段 
						if(j>1) inc(f[j+1][kk][p][q],(j-1)*g[j][k][p][q]%mod);//在中间开段 
						if(!p){//在最左边开段 
							inc(f[j+1][kk][0][q],g[j][k][p][q]);
							inc(f[j+1][kk][1][q],g[j][k][p][q]);
						}
						if(!q){//在最右边开段 
							inc(f[j+1][kk][p][0],g[j][k][p][q]);
							inc(f[j+1][kk][p][1],g[j][k][p][q]);
						}
						//延续一段 
						if(j>1) inc(f[j][kk][p][q],2*(j-1)*g[j][k][p][q]%mod);
						if(!p){
							inc(f[j][kk][0][q],g[j][k][p][q]);
							inc(f[j][kk][1][q],g[j][k][p][q]);
						}
						if(!q){
							inc(f[j][kk][p][0],g[j][k][p][q]);
							inc(f[j][kk][p][1],g[j][k][p][q]);
						}
						//合并两段 
						if(j>1) inc(f[j-1][kk][p][q],(j-1)*g[j][k][p][q]%mod);
					}
				}
			}
		}
	}
	fr(i,0,lim) ans=(ans+f[1][i][1][1])%mod;
	printf("%lld",ans);
}