【P7967 [COCI2021-2022#2] Magneti】题解

· · 题解

PS：这题做得真是一波三折。

为了方便 \text{dp} 先让半径 r_i 减一，即 r_i := r_i-1，因为这样两个相邻的磁铁 r_i,r_j 为了互不吸引，之间的最小空位数就是 \max\{r_i,r_j\}，下文默认磁铁的半径指的是减一后的半径。

考虑现在固定磁铁们的一个排列，使得第 i 个磁铁的半径为 s_i，所以 \{s_i\} 是 \{r_i\} 的重排，并设

S=\sum_{i=1}^{n-1}\max\{s_i,s_{i+1}\}

那么这样的排列至少要占据 S+n 个空位，我们还剩 l-(S+n) 个空位可以随意插入到这 n 个磁铁之间的缝隙和两侧之中，经过一些组合技巧可以算出方案数为 {l-S\choose n}，而这个式子中的变量只有 S，于是一个基本的思路就是想办法算出每一种 S 有多少排列，记为 g(S)，则最终答案为

ans=\sum_{k=0}^{l-n}{l-k\choose n}\cdot g(k)

接下来称某一磁铁排列的 S 为该磁铁排列的直径。

算法一、状压dp

用状压 \text{dp} 处理排列数是一个很常见的套路

设 f(t,i,k) 表示当前排列中的磁铁集合为 t，最后一个是第 i 个磁铁，且目前磁铁排列的直径为 k 时的方案数，则转移方程是

f(t,i,k)=\sum_{j\in t\wedge j\neq i} f(t-\{i\},j,k-\max\{r_j,r_i\})

则有

g(k)=\sum_{t}\sum_{i\in t}f(t,i,k)

总时间复杂度为 O(l\cdot n^2\cdot 2^n)。

算法二、容斥优化dp

状压 \text{dp} 时间复杂度高的关键在于其状态中包含了一个集合信息，用来表征哪些元素已经使用过，不能再使用了。

一种优化思路是想办法把这个限制去掉，也就是把集合这一信息去掉，但是这样 \text{dp} 的话就会出现元素重复使用的非法排列，但可以用容斥技巧来将非法排列去掉，只留下每个元素仅使用一次的合法方案。

具体做法是，现在我们只使用集合 T （T 为磁铁全集的某个子集）中的磁铁（可重复使用）去占据排列中的 n 个位置，然后得到磁铁排列的直径为某值下的方案数。

于是在只使用集合 T 中的磁铁的情况下，设 f_T(d,j,k) 表示现在排列中有 d 个磁铁，最末尾的磁铁是第 i 个磁铁（一定满足 i\in T），当前排列的直径为 k 时的方案数，则有转移

f_T(d,i,k)=\sum_{j\in T} f_T(d-1,j,k-\max\{r_i,r_j\})

对于单个 T，时间复杂度为 O(l\cdot n\cdot|T|^2)。

利用容斥原理则有

g(k)=\sum_{T}(-1)^{|T|}\sum_{i\in T}f_T(n,i,k)

然而我们仍然需要以 O(2^n) 枚举集合 T，所以总时间复杂度为 O(l\cdot n^3\cdot 2^n)，反而更差了，这个技巧失败。

这个技巧的来源：P3349 [ZJOI2016]小星星。

算法三、从插入的角度处理排列

首先考虑 n 个元素的排列的种类数 n! 是怎么来的，设 f(i) 表示使用元素 1 到 i 所组成的排列数，则每次加入新的元素时，新的元素可以插入到这 i 个元素之间的缝隙和两侧，一共 (i-1)+2 个可插入的位置，所以转移方程为

f(i+1)=f(i)\cdot (i+1)

因为是将元素以一定顺序依次插入，所以不需要已使用元素的集合信息，也不需要容斥。

于是不妨试试从插入的角度看看有什么突破口，插入的顺序一般有从小到大，也有从大到小，根据这题的性质，半径大的磁铁的 r 一定会覆盖半径小的磁铁的 r，插入半径大的磁铁时不必考虑半径小的磁铁的半径具体是多少，所以我们选择将磁铁按照半径从小到大插入，于是程序的一开始我们可以对 r_i 进行排序使得 r_{i-1}\le r_i。

设 f(i,k) 表示已经插入了前 i 个磁铁，且当且磁铁排列的直径为 k 的方案数。

假设现在的排列已经有了 i-1 个磁铁，当前要插入的磁铁是第 i 个磁铁。

如果选择插入在两侧，则磁铁排列的直径的增加量一定是 r_i，这时候就容易转移。

2f(i-1,k)\rightarrow f(i,k+r_i)

然而在选择插入到 i-1 个磁铁之间的间隙时我们又遇到了困难，设插入的间隙两边的磁铁分别为 r_j 和 r_k，则磁铁排列的直径不单单会增加 r_i，还会减少 \max\{r_j,r_k\}，这又涉及到具体信息了，所以这个 \text{dp} 还是太 \text{naive} 了。

这就代表这个技巧一定失败了吗？未必，在哪遇到什么困难就努力解决什么困难，我们想办法设计一个不会引起磁铁排列直径减少的 \text{dp}。

设 f(i,j,k) 表示当前已经插入了前 i 个磁铁，且这些磁铁组成了 j 个团（每个团都是一个磁铁排列），且当前不同团的磁铁排列的直径之和为 k 时的方案数。

考虑在插入第 i 个磁铁时转移 f(i-1,j,k)，有三种转移方式：

（1）从 j 个团中选一个团，并把第 i 个磁铁加入到团的两侧。

2j\cdot f(i-1,j,k)\rightarrow f(i,j,k+r_i)

（2）第 i 个磁铁独立成团。

f(i-1,j,k)\rightarrow f(i,j+1,k)

（3）从 j 个团中合并两个团，第 i 个磁铁用来缝合。

2{j\choose 2}\cdot f(i-1,j,k)\rightarrow f(i,j-1,k+2r_i)

其中乘 2 是因为这两个被选择的团之间的顺序也要考虑到。

于是转移方程可以写成

f(i,j,k)=\sum\left\{\begin{aligned} &2f(i-1,j,k-r_i)&(k\ge r_i\wedge j\le i-1)\\ &f(i-1,j-1,k)&(j>1)\\ &2(j+1)j\cdot f(i-1,j+1,k-2r_i)&(k\ge 2r_i\wedge j+1\le i-1)\\ \end{aligned}\right.

边界条件为

f(1,1,0) = 1,\quad f(1,j,k)=0\ ((j,k)\neq (1,0))\\

则有

g(k)=f(n,1,k)

总时间复杂度为 O(l\cdot n^2)，空间上可以用滚动数组优化掉第一维，空间复杂度为 O(l\cdot n)。

这个技巧的来源：P5825 排列计数。

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

#define re register
#define sf scanf
#define pf printf
#define nl() putchar('\n')
#define ms(x, val) memset(x, val, sizeof(x))
#define ll long long
#define _for(i, a, b) for(re int (i) = (a); (i) < (b); ++(i))
#define _rfor(i, a, b) for(re int (i) = (a); (i) <= (b); ++(i))
#define maxn 53
#define maxm 10005 
#define mod 1000000007ll

int iv[maxm], ivf[maxm], fct[maxm], f[2][maxn][maxm], r[maxm];

int C(re int n, re int m){ return (ll)fct[n]*ivf[m]%mod*ivf[n-m]%mod; }

void init(re int n){
    ms(f, 0); f[0][1][0] = 1;
    iv[1] = fct[0] = fct[1] = ivf[0] = ivf[1] = 1;
    _rfor(i, 2, n){
        iv[i] = (ll)iv[mod%i]*(mod-mod/i)%mod;
        fct[i] = (ll)fct[i-1]*i%mod;
        ivf[i] = (ll)ivf[i-1]*iv[i]%mod;
    }
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("sample.in", "r", stdin);
    //freopen("sample.out", "w", stdout);
    #endif

    re int n, l;
    sf("%d %d", &n, &l);
    _rfor(i, 1, n) sf("%d", r[i]), --r[i];
    sort(r+1, r+n+1);
    init(l);

    re int cur = 0;
    _rfor(i, 2, n){
        _rfor(j, 1, i) _rfor(k, 0, l-n){
            f[cur^1][j][k] = (
                (j <= i-1 && k >= r[i] ? (ll)2*j*f[cur][j][k-r[i]] : 0ll) + 
                (j > 1 ? f[cur][j-1][k] : 0ll) +
                (j+1 <= i-1 && k >= 2*r[i] ? (ll)(j+1)*j*f[cur][j+1][k-2*r[i]] : 0ll)
            )%mod;
        }
        cur ^= 1;
    }

    re int ans = 0;
    _rfor(k, 0, l-n) if (f[cur][1][k])
        ans = (ans + (ll)C(l-k, n)*f[cur][1][k])%mod;
    pf("%d\n", ans);

    return 0;
}