DP

$O(m^2n^2)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 105;

int f[N][N][N];
int t, m, n;

// 状态表示: f[i, j, k] 表示从前i个数中选，每个数可以选若干个，和为j，总数为k的方案数
// 属性: Count
// 状态计算: 
// (1)不选第i个数 f[i, j, k] = f[i - 1, j, k]
// (2)选若干第i个数 f[i, j, k] = f[i - 1, j - v[i], k - 1] + f[i - 1, j - 2 * v[i], k - 2] + ...
// + f[i - 1, j - t * v[i], k - t]

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &m, &n);
        memset(f, 0, sizeof(f));

        // 由于可以选0，故初始化有点特殊
        for(int k = 0; k <= n; k++) f[0][0][k] = 1;

        for(int i = 1; i <= m; i++){
            for(int j = 0; j <= m; j++){
                for(int k = 0; k <= n; k++){
                    for(int t = 0; j - t * i >= 0 && k - t >= 0; t++)
                        f[i][j][k] += f[i - 1][j - t * i][k - t];
                    }
                }
            }

        printf("%d\n", f[m][m][n]);
        }
    return 0;
}