三等分的数组
题面
小 Y 有一个长度为 \(n\) 的数组，数组中的每个数都是一个 \(1 \sim m\) 之间的正整数。
小 Y 决定将这个数组分成若干个三元组：每个三元组要么由三个相同的数字组成，要么由三个连续的数字组成。换句话说，每个三元组的形式要么是 \((x, x, x)\)，要么是 \((x, x + 1, x + 2)\)，其中 \(x\) 是一个正整数。
求出将数组分成三元组的方案数，答案对 \(10^9 + 7\) 取模。
\(1 \le n \le 5000,\ 1 \leq a_i \leq m \leq 5000\)
其中 \(n\) 是 \(3\) 的倍数。
题解
我们可以直接考虑大小为 \(i\) 的所有整数而不是每个数字，这样显然更方便我们进行分组。
因为要考虑连续三个数分成一组的情况，所以我们要记录一下当前数字还剩多少以及上个数字还剩多少，从而转移到下一个数字。
设 \(f(i,j,k)\) 表示考虑了前 \(i\) 个数字，\(i - 2\) 以及更小的数字保证没有剩余，\(i - 1\) 还剩 \(j\) 个，\(i\) 还剩 \(k\) 个的方案数。初始 \(f(1, 0, c_1) = 1\)
有转移：
这个状态数好像很大，为 \(O(n^3)\)，但实际上远远到不了那么大，因为 \(\sum c_i = n\)
我们可以证明，其状态数不会超过 \(O(n^2)\)
设 \(A = \sum_{i \in odd} c_i,\ B = \sum_{i \in even},\ C = \sum_{i = 1}^{m - 1} c_i \times c_{i + 1}\)，其中 \(C\) 即为我们的状态数。
不难发现 \(A \times B > C, A + B = n\)。
由基本不等式可得 \(A + B \ge 2\sqrt{A \times B}\) ，所以 \(A \times B \le \frac {n^2} 4\)。
所以时间复杂度和空间复杂度都是对的，空间可以用 vector 或者滚动数组。
code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <vector>using namespace std;namespace michaele {typedef long long ll;const int N = 5e3 + 10;const int mod = 1e9 + 7;int n, m;int c[N];void solve () {cin >> n >> m;for (int i = 1; i <= n; i ++) {int x;cin >> x;c[x] ++;}vector <vector <vector <ll> > > f (m + 5, vector <vector <ll> > ());for (int i = 0; i <= m; i ++) {if (i) {f[i].resize (c[i - 1] + 5);for (int j = 0; j <= c[i - 1]; j ++) {f[i][j].resize (c[i] + 5);}} else {f[i].resize (10);}}f[1][0][c[1]] = 1;for (int i = 1; i < m; i ++) {for (int j = 0; j <= c[i - 1]; j ++) {for (int k = c[i]; k >= 0; k --) {auto now = f[i][j][k];if (k >= j && c[i + 1] >= j) {auto &nt = f[i + 1][k - j][c[i + 1] - j];nt += now;if (nt >= 1e18) {nt %= mod;}}if (k >= 3) {auto &nt = f[i][j][k - 3];nt += now;if (nt >= 1e18) {nt %= mod;}}}}}for (int k = c[m]; k >= 0; k --) {if (k >= 3) {f[m][0][k - 3] += f[m][0][k];if (f[m][0][k - 3] > 1e18) {f[m][0][k - 3] %= mod;}}}cout << f[m][0][0] % mod << endl;}}int main () {michaele :: solve ();return 0;
}