题解：炼石计划9 T2

题目链接

题意简述

将 n 栋互不相同，且高度为 \([1, n]\) 的建筑放置在数轴上的整数位置 \([1, X]\) 上，满足任意两栋建筑之间的距离至少为两者中较高的高度。

分析

我们这里考虑如果我们知道了这个排列是什么样子的，那他有几种放法。

显然是说我先拿出一定量的空，满足这个排列是合法的，然后再将剩下的随便插进去。

比如我令 \(S = \sum_{i = 2}^{n} max(h_i, h_{i - 1})\)，一共还剩 \(X - S - 1\) 个空，插板一下，那么答案就是 $$ \binom{X - S - 1 + n}{n} $$

那么我们考虑对于一个 S 有多少种合法排列。

显然的想法是状压，但显然过不了多少点。

我们这里引入一种 DP 形式，称之为连续段 DP，其主要解决答案与序列中相邻两点有关的问题。

其思想是根据权值统计方式，我们按一定顺序插入点，然后统计当前点再最终序列上的连续段个数，和当前答案。

比如在这道题中，我们要求 max 所以我们从小往大加入点，我们可以设计 \(f[i][S][k]\) 为当前插入了前 i 个点，答案是 S，段个数是 k （只是形成了这些个段，但是顺序不重要）的方案数。

那么有三种转移方式：

新插入一个段，则两边都比 i + 1 大：f[i + 1][S][k + 1] += f[i][S][k]

连接当前形成的两个段，则两边都比 i + 1 小：f[i + 1][S + 2 (i + 1)][k - 1] += f[i][S][k] * k * (k - 1)

贴在一个段一边，则一边大一边小：f[i + 1][S + i + 1][k] += f[i][S][k] * k * 2

code

#include

using namespace std;

//const int N =

#define int long long

typedef long long ll;

int n, X, P;

ll f[105][10005][105];

ll fac[1000005], inv[1000005];

ll qpow(ll a, int b) {

int res = 1;

while (b) {

if (b & 1) {

res *= a;

res %= P;

}

a *= a;

a %= P;

b >>= 1;

}

return res;

}

int C (int n, int m) {

if (m < 0 || n < 0 || m > n) return 0;

return fac[n] * inv[m] % P * inv[n - m] % P;

}

int ck (int len) {

if (len > X - 1) return 0;

int N = X - 1 - len, M = n + 1;

return C (N + M - 1, M - 1);

}

signed main() {

// freopen("build.in", "r", stdin);

// freopen("build.out", "w", stdout);

cin >> n >> X >> P;

fac[0] = inv[0] = 1;

for (int i = 1;i <= 1000000;i++) {

fac[i] = fac[i - 1] * i % P;

inv[i] = qpow(fac[i], P - 2);

}

int ind = 0;

f[ind][0][0] = 1;

for (int i = 0;i < n;i++, ind = 1 - ind) {

// cout <

for (int S = 0;S <= i * i;S++) {