LibreOJ 3276 「JOISC 2020 Day2」遗迹

考虑对于给定的起始如何求最终状态。
按编号从大到小依次考虑每一根石柱，设 usedi 表示目前是否有石柱的最终高度为 i。
则第 i 根石柱的最终高度为 max1≤j≤hi,¬usedjj。

考虑模拟这个过程进行 DP。

设 fi,j 表示 [i,2N] 的最终高度中已知出现了 [1,j] 中的每一个整数，且 j 是极大的。
考虑从 fi+1 转移到 fi：

• 若 i∉A： 则显然有 1≤hi≤j，否则便可以取到 j+1 作为最终状态。
  然而并不清楚 [1,j] 中还有哪些可以用，因为难以得知使用的次数。
  此时考虑将问题转化为同一种高度的石柱之间有区别。
  则可以取的值有 j−in，其中 in=2N∑j=i[j∈A]。
• 若 i∈A： 则假定 i 的最终状态为 j+1；若不是，也会存在另一个状态统计到其贡献。
  考虑枚举 k 表示确定了 hi 之后使极长前缀达到了 [1,j+k]。
  那么显然可以使用的高度有 in−j 种，要在其中选 k−1 种。
  接着需要求出将这 k−1 个位置的最终状态恰好填为 [j+2,j+k] 的方案数。需要注意的是，这些位置的初始高度仅能使用 [j+2,j+k] 内的值。
  注意到这可以表示为 coek−1，等会再讨论。
  最后，hi 能取到的值，有 j+1 处的两个，和 [j+2,j+k] 剩下的 k−1 个，共 k+1 个。

接下来考虑 coek。
注意到一个方案合法，当且仅当对于任意 1≤i≤k 都满足不超过 i 的元素个数不超过 i（套娃警告）。
那么便可以借助这个性质，设 gi,j 表示在 j 个位置中填不超过 i 的元素，且满足上述条件的方案数。
分别考虑用 0,1,2 个 i，可得 gi,j=gi−1,j+gi−1,j−1⋅2j+gi−1,j−2⋅j(j−1)

又有 coek=gk,k。

代码：

#include <cstdio>
#define add(x,y) (x + y >= mod ? x + y - mod : x + y)
#define dec(x,y) (x < y ? x - y + mod : x - y)
using namespace std;
const int N = 1200;
const int mod = 1e9 + 7;
const int inv = 5e8 + 4;
int n,vis[N + 5];
int f[N + 5][N + 5],c[N + 5][N + 5],coe[N + 5][N + 5];
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int main()
{
    scanf("%d",&n),f[(n << 1) | 1][0] = 1;
    for(register int i = 0;i <= n;++i)
    {
        c[i][0] = coe[i][0] = 1;
        for(register int j = 1;j <= i;++j)
            c[i][j] = add(c[i - 1][j - 1],c[i - 1][j]),
            coe[i][j] = (coe[i - 1][j] + 2LL * j * coe[i - 1][j - 1]) % mod,
            j >= 2 && (coe[i][j] = (coe[i][j] + (long long)coe[i - 1][j - 2] * j * (j - 1)) % mod);
    }
    int x;
    for(register int i = 1;i <= n;++i)
        scanf("%d",&x),vis[x] = 1;
    for(register int i = n << 1,in = 0;i;in += vis[i--])
        if(vis[i])
            for(register int j = 0;j <= in;++j)
            {
                f[i][j] = add(f[i][j],f[i + 1][j]);
                for(register int k = 1;j + k <= in + 1;++k)
                    f[i][j + k] = (f[i][j + k] + (long long)c[in - j][k - 1] * coe[k - 1][k - 1] % mod * (k + 1) % mod * f[i + 1][j]) % mod;
            }
        else
            for(register int j = 0;j <= in;++j)
                f[i][j] = (long long)f[i + 1][j] * (j - (n << 1) + i + in) % mod;
    printf("%lld\n",(long long)f[1][n] * fpow(inv,n) % mod);
}