题目描述

n 个问题的分值满足如下关系：$1≤A_1≤A_2≤…≤A_n≤n$。不同的问题可以具有相同的分值。 对于任何解决了 $k$（$1≤k≤n-1$）个问题的参赛者，其分数总和一定要小于解决了任何 $k + 1$ 个问题的参赛者的分数总和。

输入

整数 $n$ 和 $m$，其中 $2≤n≤5000$，$m$ 为素数。

输出

分值分配的方案数对 $m$ 取余后的数字。

样例输入

3 998244353

样例输出

7

样例说明：

3 个题的分值分配有 7 种方案：(1,1,1), (1,2,2), (1,3,3), (2,2,2), (2,2,3), (2,3,3), (3,3,3)。

求助说明

写了极其暴力的DFS，可以输出方案，但怎么想不到如何用DP表示去表示状态和进行状态计算，被这道题困扰了好久，最终鼓足勇气求助大佬。

DFS代码如下：

#include <iostream>
using namespace std;

const int N = 10000;
int f[N], a[N];
int n, res = 0;

bool check(int a[])
{
    int cnt = 1;
    for(int i = 0; i < n - 1; i ++)
    {
        int sum1 = a[0], sum2 = a[n - 1];
        
        for(int j = 1; j <= cnt; j ++)
            sum1 += a[j];
        for(int j = 1; j < cnt; j ++)
            sum2 += a[n - 1 - j];
        if(sum1 <= sum2) return false;
        cnt ++;
    }
    
    return true;
}

void dfs(int t, int x)
{
    if(t == n)
    {
        if(!check(a)) 
        {
            return;
        }
        for(int i = 0; i < t; i ++)
            cout << a[i] << ' ';
        cout << endl;
        res ++;
        return;
    }
    
    for(int i = x; i <= n; i ++)
    {
        a[t] = i;
        dfs(t + 1, i);
    }
}

int main()
{
    int m;
    cin >> n >> m;
    dfs(0, 1); 
    cout << res << endl;
    return 0;
}