問題描述

藍橋杯 C++青少組的比賽有 n n n 個問題，現在請你給這 n n n 個問題分配分值， n n n 個問題已經按從簡單到困難排好序，第 i 個問題的分值是 A i A_i Ai?， n n n 個問題的分值滿足如下關系： 1 ≤ A 1 ≤ A 2 ≤ … ≤ A n ≤ n 1≤A_1≤A_2≤…≤A_n≤n 1≤A1?≤A2?≤…≤An?≤n，不同的問題可以具有相同的分值，

主辦方希望：解決更多問題的參賽者的排名更高， 因此，對于任何解決了 k （ 1 ≤ k ≤ n ? 1 ） k（1≤k≤n-1） k（1≤k≤n?1）個問題的參賽者，其分數總和一定要小于解決了任何 k + 1 k + 1 k+1 個問題的參賽者的分數總和，

你有幾種分配分值的方法？ 將答案對素數 m 取余后輸出，

輸入格式

整數 n n n 和 m m m， m m m 為素數，

資料范圍

2 ≤ n ≤ 5000 2≤n≤5000 2≤n≤5000,
9 × 1 0 8 < m < 1 0 9 9×10^8<m<10^9 9×108<m<109

輸出格式

分值分配的方案數對 m m m 取余后的數字

輸入樣例 1

2 998244353

輸出樣例 1

3

樣例1 說明： 2 2 2 個題的分值分配有 3 3 3 種方案： ( 1 , 1 ) , ( 1 , 2 ) , ( 2 , 2 ) (1,1), (1,2), (2,2) (1,1),(1,2),(2,2)，

輸入樣例 2

3 998244353

輸出樣例 2

7

樣例 2 說明： 3 3 3 個題的分值分配有 7 7 7 種方案： ( 1 , 1 , 1 ) , ( 1 , 2 , 2 ) , ( 1 , 3 , 3 ) , ( 2 , 2 , 2 ) , ( 2 , 2 , 3 ) , ( 2 , 3 , 3 ) , ( 3 , 3 , 3 ) (1,1,1), (1,2,2), (1,3,3), (2,2,2), (2,2,3), (2,3,3),(3,3,3) (1,1,1),(1,2,2),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3)，

演算法思想（動態規劃）

狀態表示

f [ n ] f[n] f[n]表示包含 n n n個問題的合法方案數，

狀態計算

根據題目描述，有 n n n個問題，每個問題的分值為 A i A_i Ai?，且必須滿足 1 ≤ A 1 ≤ A 2 ≤ … ≤ A n ≤ n 1≤A_1≤A_2≤…≤A_n≤n 1≤A1?≤A2?≤…≤An?≤n，即最低為 1 1 1分，最高為 n n n分，要計算 n n n個問題的方案數 f [ n ] f[n] f[n]，可以將符合條件的集合分為兩類：

一、 不包含分值n的情況

對于 n n n個問題來說，在 n ? 1 n - 1 n?1個問題的合法方案中，添加一個相同的分數，就可以組成一個包含 n n n個問題的合法方案，例如，當 n = 3 n = 3 n=3時，對于 2 2 2個問題的合法方案有 ( 1 , 1 ) , ( 1 , 2 ) , ( 2 , 2 ) (1,1),(1,2),(2,2) (1,1),(1,2),(2,2)，那么 ( 1 , 1 , 1 ) , ( 1 , 2 , 2 ) , ( 2 , 2 , 2 ) (1,1,1),(1,2,2),(2,2,2) (1,1,1),(1,2,2),(2,2,2)就是包含 3 3 3個問題的合法方案，

因此，不包含分值 n n n的情況下： f [ n ] = f [ n ? 1 ] f[n] = f[n - 1] f[n]=f[n?1]

二、 包含分值n的情況

此時，可以根據第一個問題的分值將集合劃分為下面 n n n種情況：

• 第一個問題的分數值為 1 1 1分，此時滿足條件的方法只有1種情況：
  • 1 , n , n , . . . n 1,n,n,...n 1,n,n,...n
• 第一個問題的分數值為 2 2 2分，此時滿足條件的方法有2種情況：
  • 2 , n , n . . . n 2,n,n...n 2,n,n...n
  • 2 , n ? 1 , n , . . . n 2,n-1,n,...n 2,n?1,n,...n
• 第一個問題的分數值為 3 3 3分，此時滿足條件的方法只有3種情況
  • 3 , n , n . . . n 3,n,n...n 3,n,n...n
  • 3 , n ? 1 , n , . . . n 3,n-1,n,...n 3,n?1,n,...n
  • 3 , n ? 1 , n ? 1 , n . . . , n 3,n-1,n-1,n...,n 3,n?1,n?1,n...,n
• …
• 第一個問題的分數值為 n ? 1 n-1 n?1分，此時滿足條件的方案有n-1種情況：
  • n ? 1 , n , n . . . n n-1,n,n...n n?1,n,n...n
  • n ? 1 , n ? 1 , n . . . n n-1,n-1,n...n n?1,n?1,n...n
  • …
  • n ? 1 , n ? 1 , n ? 1... , n ? 1 , n n-1,n-1,n-1...,n-1,n n?1,n?1,n?1...,n?1,n
• 第一個問題的分數值為 n n n分，此時滿足條件的方案有1種情況：
  • n , n , n , . . . n n,n,n,...n n,n,n,...n

因此，包含分值為 n n n的問題的情況下： f [ n ] = 1 + 2 + 3 + . . . + n ? 1 + 1 f[n] = 1 + 2 + 3 + ... + n - 1 + 1 f[n]=1+2+3+...+n?1+1

那么，對于 n n n個問題符合條件的方案數 f [ n ] = f [ n ? 1 ] + 1 + 2 + 3 + . . . + n ? 1 + 1 f[n] = f[n - 1] + 1 + 2 + 3 + ... + n - 1 + 1 f[n]=f[n?1]+1+2+3+...+n?1+1，

初始狀態

f [ 1 ] = 1 f[1] = 1 f[1]=1

時間復雜度

需要計算 2 ～ n 2\sim n 2～n的每種情況下的方案數 f [ i ] f[i] f[i]；在計算每個 f [ i ] f[i] f[i]時，還需要累加 1 ～ i ? 1 1\sim i-1 1～i?1，所以時間復雜度為 O ( n 2 ) O(n^2) O(n2)，

代碼實作

#include <iostream>
using namespace std;

const int N = 10000;
int f[N];

int main()
{
    int n, m;
    cin >> n >> m;
    f[1] = 1;
    for(int i = 2; i <= n; i ++)
    {
        f[i] = f[i - 1]; //不包含分值n的情況
        //累加包含分值i的情況
        for(int j = 1; j < i; j ++)
            f[i] = (f[i] + j) % m;
        f[i] = (f[i] + 1); //加上全是分值i的情況
    }
    cout << f[n] << endl;
    return 0;
}