#include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; // dp[i][j]：前i题，第i题分值为j的合法方案数 // 用滚动数组优化空间（仅保留前一行） vector<long long> dp_prev(n + 1, 0); vector<long long> dp_curr(n + 1, 0); vector<long long> sum_prev(n + 1, 0); // 初始化i=1（第一题） for (int j = 1; j <= n; ++j) { dp_prev[j] = 1; sum_prev[j] = (sum_prev[j - 1] + dp_prev[j]) % m; } // 递推i从2到n for (int i = 2; i <= n; ++i) { // 计算前i题的总分约束：S_i > i*(i-1)/2 // S_i = S_{i-1} + j → S_{i-1} > i*(i-1)/2 - j long long min_S_prev = (1LL * i * (i - 1) / 2) - n; // 下界 if (min_S_prev < 0) min_S_prev = 0; // 遍历第i题的分值j for (int j = 1; j <= n; ++j) { // 前i-1题的总分S_{i-1}需满足：S_{i-1} > (i*(i-1)/2 - j) // S_{i-1} = sum_{k=1}^{i-1} A_k，其中A_{i-1}=k → S_{i-1} ≥ sum_{t=1}^{i-2} 1 + k = (i-2)(i-1)/2 + k long long threshold = (1LL * i * (i - 1) / 2) - j; long long min_k = threshold - (1LL * (i - 2) * (i - 1) / 2); if (min_k < 1) min_k = 1; // 累加前i-1题分值k≤j且k≥min_k的方案数 if (min_k > j) { dp_curr[j] = 0; } else { dp_curr[j] = (sum_prev[j] - sum_prev[min_k - 1] + m) % m; } } // 计算当前行的前缀和 sum_prev[0] = 0; for (int j = 1; j <= n; ++j) { sum_prev[j] = (sum_prev[j - 1] + dp_curr[j]) % m; } // 滚动数组更新 dp_prev = dp_curr; fill(dp_curr.begin(), dp_curr.end(), 0); } // 最终答案：前n题分值≤n的所有方案数 cout << sum_prev[n] % m << endl; return 0; }