题目概述
题目链接：https://www.luogu.com.cn/problem/CF1288C。
长度为 \(m\) 的序列 \(a,b\)，值域为 \([1,n]\)，求 \((a,b)\) 的数量满足：
- \(a\) 单调不降。
- \(b\) 单调不升。
- 对于每个 \(i\)，满足 \(a_i\leq b_i\)。
\(1\leq n\leq 1000,1\leq m\leq 10\)。
分析
这道题目直接前缀和优化 \(dp\) 就行了，但是还有更优的做法。
注意到：
- \(a_1\leq a_2\leq a_3\leq \dots\leq a_m\)
- \(b_1\geq b_2\geq b_3\geq \dots\geq b_m\)
- 对于每个 \(i\)，有 \(a_i\leq b_i\)
那么显然只需满足：\(b_1\geq a_m\)。
那么我们把他们拼在一起，变成 \(b_m,b_{m-1},\dots,b_1,a_1,a_2,\dots,a_m\)。
那么这个序列就变成了 \(2m\) 个元素，单调不上升的。
设 \(x_j\) 表示数字 \(j\) 这上面出现的次数。
那么只需要满足：
\[\sum_{i=1}^n x_i=m(x_i\geq 0)
\]
这是一个很经典的问题，直接插板就行了，答案为 \(C_{2m+n-1}^{n-1}\)。
代码
时间复杂度 \(\mathcal{O}(n+m)\)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#define int long long
#define N 1005
#define M 15
#define K 1035
using namespace std;
const int mod = 1e9 + 7;
int n,m,jc[K],inv[K];
int C(int a,int b) {if (a < 0 || b < 0 || a < b) return 0;return jc[a] * inv[b] % mod * inv[a - b] % mod;
}
signed main(){cin >> n >> m;jc[0] = jc[1] = inv[0] = inv[1] = 1;for (int i = 2;i <= n + 2 * m;i ++) jc[i] = jc[i - 1] * i % mod,inv[i] = (mod - mod / i) * inv[mod % i] % mod;for (int i = 2;i <= n + 2 * m;i ++) inv[i] = inv[i - 1] * inv[i] % mod;cout << C(2 * m + n - 1,n - 1);return 0;
}