LOSER求救
查看原帖
LOSER求救
693585
QWVnbGVzZWVrZXI3D楼主2024/11/20 18:16

WA49, 觉得是统计重复了但又想不出来

/*

f[i][j][k]表示第i层, j个节点, 当前层安排了k个节点
if f[i][j][k] != 0
    f[i + 1][j + a * 2][a * 2] += f[i][j][k] + C(k, a);
*/
#include <iostream>
using namespace std;
const int MOD = 9901;
const int N = 210, K = 110;
int n, k;
int f[K][N][N];
int C[N][N];

void init()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (j == 0)
                C[i][j] = 1;
            else
                C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
        }
    }
}

int main()
{
    init();
    cin >> n >> k;
    f[1][1][1] = 1;
    for (int i = 1; i < k; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= n; k++)
            {
                if (f[i][j][k] != 0)
                {
                    for (int a = 1; a <= k; a++)
                    {
                        if (j + a * 2 > n)
                        {
                            break;
                        }
                        else
                        {
                            f[i + 1][j + a * 2][a * 2] = (f[i + 1][j + a * 2][a * 2] +  f[i][j][k] + C[k][a] - 1) % MOD;
                        }
                    }
                }
            }
        }
    }
    int tot = 0;
    for (int i = 1; i * 2 <= n; i++)
    {
        tot += f[k][n][i * 2];
    }
    cout << tot;
    return 0;
}
2024/11/20 18:16
加载中...