bzoj4498: 魔法的碰撞

时间：2023-03-08 22:08:49

首先，如果排列确定，那么就可以组合学解决了，不过排列数很多，显然不能枚举。

我们发现如果区间不能重叠的话，总长度减去所有区间长度就是能用的多余格子数。

然而相邻区间可以重叠较小区间一半的长度，因此这些长度就可以作为额外的多余格子！

因此，我们发现，确定排列的目的是确定有多少多余的格子能用。

考虑把魔法师按攻击范围从大到小排序，然后逐个插入

一开始有一个洞，每插一个可以减少一个洞、不变或增加一个洞（洞就表示还能再插）

令dp[i][j][k]表示现在插了i个，有j个洞，目前有k个额外的格子。

然后随便插一插搞一搞

答案即为dp[n][0][i]*C(L+i+n,n)的和

空间时间均为O(n^4+LlogP)

//我觉得我的复杂度应该有问题……TAT

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#define ll long long

#define N 43

#define M 1702

#define P 1000000007

using namespace std;

int fast_pow(int x,int y){

	int ret=1;

	while (y){

		if (y&1) ret=(ll)ret*x%P;

		x=(ll)x*x%P;

		y=y>>1;

	}

	return ret;

}

int n,d[N];

int dp[N][N][M];

int L;

int fact[1000006+M],inv[1000006+M];

int c(int n,int m){return (ll)fact[n]*inv[m]%P*inv[n-m]%P;}

int main(){

	scanf("%d%d",&L,&n);--L;

	for (int i=0;i<n;L-=2*d[i++]) scanf("%d",&d[i]);

	sort(d,d+n,greater<int>());

	memset(dp,0,sizeof(dp));

	dp[0][1][0]=1;

	for (int i=0;i<n;++i)

		for (int j=1;j<=n-i&&j<=i+1;++j)

			for (int k=0;k<=(i-j+1)*40;++k)if (dp[i][j][k]){

				(dp[i+1][j-1][k+2*d[i]]+=(ll)dp[i][j][k]*j%P)%=P;

				(dp[i+1][j][k+d[i]]+=(ll)dp[i][j][k]*j*2%P)%=P;

				(dp[i+1][j+1][k]+=(ll)dp[i][j][k]*j%P)%=P;

			}

	for (int i=fact[0]=1;i<=L+(n+2)*40;++i) fact[i]=(ll)fact[i-1]*i%P;

	for (int i=0;i<=L+(n+2)*40;++i) inv[i]=fast_pow(fact[i],P-2);

	int ans=0;

	for (int i=max(-L,0);i<=(n+1)*40;++i) (ans+=(ll)dp[n][0][i]*c(L+i+n,L+i)%P)%=P;

	printf("%d\n",ans);

	return 0;

}

　　

相关文章