算法标签

• 动态规划
• 组合计数

题目分析

这是一个计数类动态规划问题。我们需要将数组划分为若干三元组，每个三元组要么是三个相同数字，要么是三个连续数字。

关键思路

1. 状态设计
   设 dp[i][j] 表示考虑数字 1..i，并且有 j 个连续三元组在数字 i 处开始（即形如 (i, i+1, i+2) 的三元组，当前只确定了第一个数字 i，还需要 i+1 和 i+2）。

2. 状态转移
   对于数字 i，设它在数组中出现的次数为 cnt[i]。我们需要分配这些 i 到三种用途：

   • 完成从 i-1 开始的连续三元组（需要消耗 j 个 i）
   • 新开从 i 开始的连续三元组（消耗 k 个 i）
   • 剩下的组成同数字三元组 (i,i,i)

3. 转移方程
   剩余数量 rem = cnt[i] - j - k 必须是非负的 3 的倍数。
   同数字三元组数量为 rem/3。
   新开的三元组数量 k 会成为下一状态 dp[i+1][k] 的 j。

4. 组合系数
   在分配时，我们需要考虑多重组合数：从可用的 i 中选择哪些用于完成旧三元组，哪些用于新开三元组，哪些用于同数字三元组。

题解代码

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 5005;

int n, m;
int cnt[MAXN];
long long dp[MAXN][MAXN];
long long C[MAXN][MAXN];

void precompute_comb() {
    for (int i = 0; i < MAXN; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    precompute_comb();
    
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    
    dp[0][0] = 1;
    
    for (int i = 1; i <= m; i++) {
        for (int prev_j = 0; prev_j <= n/3; prev_j++) {
            if (dp[i-1][prev_j] == 0) continue;
            
            // prev_j 个连续三元组需要当前数字 i 来完成
            int available = cnt[i];
            
            for (int new_k = 0; new_k <= available; new_k++) {
                int used_for_prev = prev_j;
                int total_used = used_for_prev + new_k;
                if (total_used > available) break;
                
                int rem = available - total_used;
                if (rem % 3 != 0) continue;
                
                int triple_same = rem / 3;
                
                // 多重组合数：从 available 个 i 中选出 used_for_prev 个给之前的三元组，
                // 再从剩下的选出 new_k 个给新的三元组，剩下的自动组成同数字三元组
                // 这等价于：C[available][used_for_prev] * C[available - used_for_prev][new_k]
                // 但还要考虑同数字三元组内部的排列（已经自动处理）
                
                long long ways = dp[i-1][prev_j];
                ways = ways * C[available][used_for_prev] % MOD;
                ways = ways * C[available - used_for_prev][new_k] % MOD;
                
                // 同数字三元组：rem 个数字分成 triple_same 组，每组3个相同的
                // 分组方式有：rem! / (3!)^triple_same / triple_same!
                // 但这里 rem 个相同的 i，分成 triple_same 组每组3个，方案数 = 1
                // 因为数字相同，分组方式唯一
                
                dp[i][new_k] = (dp[i][new_k] + ways) % MOD;
            }
        }
    }
    
    cout << dp[m][0] << endl;
    
    return 0;
}

更简洁的实现

实际上，组合数可以简化，因为数字相同，分配方式唯一：

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 5005;

int n, m, cnt[MAXN];
long long dp[MAXN][MAXN], fact[MAXN], inv_fact[MAXN];

long long mod_pow(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    inv_fact[MAXN-1] = mod_pow(fact[MAXN-1], MOD-2);
    for (int i = MAXN-2; i >= 0; i--) {
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    }
}

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    precompute();
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        cnt[x]++;
    }
    
    dp[0][0] = 1;
    
    for (int i = 1; i <= m; i++) {
        for (int prev = 0; prev <= n/3; prev++) {
            if (dp[i-1][prev] == 0) continue;
            
            int avail = cnt[i];
            for (int nxt = 0; nxt <= avail; nxt++) {
                int need = prev + nxt;
                if (need > avail) break;
                int rem = avail - need;
                if (rem % 3 != 0) continue;
                
                // 分配方式：从avail个中选prev个给旧三元组，nxt个给新三元组
                long long ways = nCr(avail, prev) * nCr(avail - prev, nxt) % MOD;
                dp[i][nxt] = (dp[i][nxt] + dp[i-1][prev] * ways) % MOD;
            }
        }
    }
    
    cout << dp[m][0] << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：$O(m \cdot (n/3)^2)$，最坏 $5000 \times 1667^2$ 较大，但实际循环会提前退出
• 空间复杂度：$O(m \cdot n)$

算法优化

对于大数据范围，可以进一步优化：

1. 限制 j 的范围（不超过 cnt[i]）
2. 使用滚动数组优化空间
3. 预处理组合数