题解 | 【模板】记忆化搜索

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000007;
const int MAX = 101; // 假设a,b,c的最大值为100，根据实际情况调整

// 三维DP数组
long long dp[MAX][MAX][MAX];

void precomputeDP() {
    // 初始化边界条件：当任一参数<=0时，结果为1
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            for (int k = 0; k < MAX; k++) {
                if (i <= 0 || j <= 0 || k <= 0) {
                    dp[i][j][k] = 1;
                }
            }
        }
    }
    
    // 自底向上计算DP数组
    for (int i = 1; i < MAX; i++) {
        for (int j = 1; j < MAX; j++) {
            for (int k = 1; k < MAX; k++) {
                if (i < j && j < k) {
                    dp[i][j][k] = (dp[i][j][k-1] + dp[i][j-1][k-1] - dp[i][j-1][k] + MOD) % MOD;
                } else {
                    dp[i][j][k] = (dp[i-1][j][k] + dp[i-1][j-1][k] + dp[i-1][j][k-1] - dp[i-1][j-1][k-1] + MOD) % MOD;
                }
            }
        }
    }
}

int main() {
    // 预计算所有可能的结果
    precomputeDP();
    
    int t;
    cin >> t;
    
    while (t--) {
        int a, b, c;
        cin >> a >> b >> c;
        
        // 确保不越界
        a = min(a, MAX-1);
        b = min(b, MAX-1);
        c = min(c, MAX-1);
        
        cout << dp[a][b][c] << endl;
    }
    
    return 0;
}