bomb 题解

· · 个人记录

n=2 提示我们其实真正的条件是 |p_i-p_j|>\max\{r_i,r_j\}，我们只需要确定 n 个炸弹的顺序，我们就可以用一点组合数学来解决

既然只需要考虑顺序，那么每两个炸弹之间只需要考虑他们最小距离就够了，D 这么大就是吓唬人的，其实有用的只有 \sum r\le 2500

然后我们要为最后统计答案的过程准备数据，我们需要两组值，对于每一种状态，考虑这两个值：

  1. 这些炸弹占用了多少格子（包括炸弹本身以及炸弹之间的间隔，即 \max\{r_i,r_j\} 占用的位置）

  2. 这些炸弹占用这么些格子的方案数（注意这里只考虑他们一个挨着一个紧凑排列的情况，非紧凑排列的情况统计答案时考虑了）

这是一个关于炸弹顺序的算法，容易想到状压 dp，但是这里显然不行，我们可以优化状态，因为我们不用考虑具体顺序，这个状态只需要能维护用了多少格子就够了，于是我们设计出一个状态 f[i][j] 表示前 i 个状态占用 j 个格子的方案数

然后我们很快发现这这样很难转移，有两个问题：

  1. 不知道每个炸弹添加进来的时候该离其他炸弹多远

  2. 位置关系不明确，比如我在 a，b 之间插入了炸弹 c，这个时候我再在 c，b 之间插入炸弹 d，这个时候就难以处理 b，c 的关系

第一个问题我们把 r[] 排序就行

关于第二个问题，考虑添加一维状态，我们让这 i 个炸弹逐次合并，f[i][j][k] 表示前 i 个炸弹，目前合并成了 j 个炸弹块，占用了 k 个格子

转移有三种：

  1. 新炸弹自己成为一个新的炸弹块

  2. 新炸弹添加到原来的一个炸弹块中

  3. 新炸弹插入到原来的两个炸弹块中间并且合并三者

然后就做完了

code：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define cmin(a, b) (a)=min((a), (b))
#define cmax(a, b) (a)=max((a), (b))
#define mem(a, x) memset(a, x, sizeof(a))
#define rps(i, b, e) for(int i=(b);i<=(e);i++)
#define prs(i, e, b) for(int i=(e);i>=(b);i--)
#define rpg(i, g, x) for(int i=g.head[x];i;i=g.e[i].nxt)
#define opf(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
using namespace std;
template<class T>
inline void read(T &x) {
    x=0;
    bool f=false;
    char c=getchar();
    while(!isdigit(c))f|=(c=='-'), c=getchar();
    while(isdigit(c))x=x*10+(c-'0'), c=getchar();
    if(f)x=-x;
}
const int NR=55, SR=2505, MOD=1e9+7;
int d, n, r[NR], f[NR][NR][SR];
inline int pls(int a, int b) {
    return (a+b>=MOD ? a+b-MOD : a+b);
}
inline int mul(int a, int b) {
    return 1ll*a*b%MOD;
}
int qp(int a, int b) {
    int res=1;
    while(b) {
        if(b&1)res=mul(res, a);
        a=mul(a, a), b>>=1;
    }
    return res;
}
inline int comb(int n, int m) {
    int res=1;
    rps(i, n-m+1, n)res=mul(res, i);
    rps(i, 1, m)res=mul(res, qp(i, MOD-2));
    return res;
}
int main() {
    read(d), read(n);
    rps(i, 1, n)read(r[i]);
    sort(r+1, r+n+1);
    f[0][0][0]=1;
    rps(i, 0, n-1)rps(j, 0, i)rps(k, 0, n*r[n]) {
        int tmp=f[i][j][k];
        if(tmp==0)continue;
        f[i+1][j+1][k+1]=pls(f[i+1][j+1][k+1], mul(tmp, j+1));
        f[i+1][j][k+1+r[i+1]]=pls(f[i+1][j][k+1+r[i+1]], mul(tmp, 2*j));
        if(j>1)f[i+1][j-1][k+1+2*r[i+1]]=pls(f[i+1][j-1][k+1+2*r[i+1]], mul(tmp, j-1));
    }
    int ans=0;
    rps(k, 0, n*r[n])
        ans=pls(ans, mul(f[n][1][k], comb(d-k+n+1 -1, n+1 -1)));
    printf("%d\n", ans);
    return 0;
}