StO Kubic 神

發現主要限制在第三個限制，考慮變形一下限制要求，問題轉化為要求序列的 \(k = \lfloor \dfrac{n}{2} \rfloor\)，的前 \(k + 1\) 項的和，大于后 \(k\) 項的和。

動態設前 \(k + 1\) 個的和與后 \(k\) 個和的差為 \(\triangle\)，初始為 \(n\)。

每次都對一個前綴整體 \(-1\)，然后算出對每個前綴操作的時候，對 \(\triangle\) 的影響。

問題就轉化為了背包，總容量為 \(n\)，\(n\) 個物品，每個物品有 \(w_i\) 的重量，要求放物品使得總重量不超過 \(n- 1\) 的方案數。

直接背包就好了。

// 德麗莎你好可愛德麗莎你好可愛德麗莎你好可愛德麗莎你好可愛德麗莎你好可愛
// 德麗莎的可愛在于德麗莎很可愛，德麗莎為什么很可愛呢，這是因為德麗莎很可愛！
// 沒有力量的理想是戲言，沒有理想的力量是空虛
#include <bits/stdc++.h>
#define LL long long
using namespace std;
char ibuf[1 << 15], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 15, stdin), p1==p2) ? EOF : *p1++)
inline int read() {
  char ch = getchar();  int x = 0, f = 1;
  while (ch < '0' || ch > '9')  {  if (ch == '-')  f = -1;  ch = getchar();  }
  while (ch >= '0' && ch <= '9')  x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return x * f;
}
void print(LL x) {
  if (x > 9)  print(x / 10);
  putchar(x % 10 + '0');
}
template<class T> bool chkmin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool chkmax(T &a, T b) { return a < b ? (a = b, true) : false; }
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define repd(i, l, r) for (int i = (l); i >= (r); i--)
#define REP(i, l, r)  for (int i = (l); i < (r); i++)
const int N = 5005;
int n, mod, dp[N], w[N];
void solve() {
  cin >> n >> mod;
  rep (i, 1, (n + 1) / 2)  w[i] = i;
  rep (i, 1, (n / 2))  w[n - i + 1] = i;
  dp[n] = 1;
  rep (i, 1, n) {
    repd (j, n, w[i]) {
      dp[j - w[i]] = (dp[j] + dp[j - w[i]]) % mod;
    }
  }
  int ans = 0;
  rep (i, 1, n)  ans += dp[i] , ans %= mod;
  cout << ans;
}
signed main () {
#ifdef LOCAL_DEFINE
  freopen("1.in", "r", stdin);
  freopen("1.ans", "w", stdout);
#endif
  int T = 1;  while (T--)  solve();
#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}