差分dp

差分约束可以解决一系列有条件约束的dp问题
0/1 背包，完全背包等等
其他差分补充内容

Problem Scores

$\text{比如说从一类物品中，每次选一个物品}, \textbf{可以重复}$
$\text{问有多少种选择方法}$
$在此基础上，加入约束条件，就是差分约束dp$

$\textbf{algorithm1: dp()}$

$\textbf{0-1 背包}$
$$ f(i, j)=\max \left\{\begin{array}{l} f(i-1, j) && \text{do not use ith item} \\\ f\left(i-1, j-V_{i}\right)+w_{i} \quad n>j \geqslant V_{i} && \text{use ith item} \end{array}\right. $$
$(i-1) \xrightarrow{update()} (i)$
$\textbf{for } \forall j = n \textbf{ downto } V_i$

$\textbf{完全背包}$
$$ f(i, j)=\max \left\{\begin{array}{l} f(i-1, j) && \text{do not use ith} \\\ f\left(i, j-V_{i}\right)+w_{i} \quad V_i \leqslant j < n && \text{use ith} \end{array}\right. $$
$(i) \xrightarrow{update()} (i\textbf{th itself})$
$\textbf{for } \forall j = V_i \textbf{ to } n$

一个是用以前的阶段更新现在阶段
一个是用当前阶段更新当前
所以循环的顺序是不一样的

$\textbf{algorithm2}$
$1 \leqslant a_i \leqslant n, \forall k, 1 \leqslant k < n $
都有对任意大小为 $k$ 的子集 $S$ 和大小为 $k+1$ 的子集 $T$
$$ \sum_{x \in S} a_x < \sum_{x \in T} a_x $$
这样的集合有多少个？

$\textbf{i) }$
$$\textbf{if }\quad k = \lfloor \frac{n}{2} \rfloor \text{ meet the conditions } \\\ \ \\\ \sum_{i = 1}^{k+1}a_i \geqslant \sum_{i = n-k+1}^{n} a_i, \quad (n-k+1= k+1 \Rightarrow k = \lfloor \frac{n}{2}\rfloor) $$
$$ \text{根据序列的单调性，} k < \lfloor \frac{n}{2}\rfloor \\\ \ \\\ 相当于 (\sum_{i = 1}^{k+1}a_i)-\sum a_p \geqslant?? ( \sum_{i = n-k+1}^{n} a_i) + \sum a_q, \\\ \quad (\sum a_p < \sum a_q, \ p < q), \text{ 不等式仍然成立} $$
$\textbf{所以只要有 } k = \lfloor \frac{n}{2} \rfloor \textbf{ 成立，所有情况都成立}$

$\textbf{ii) 差分数组的构造}$
$$ \Delta a_i = a_i - a_{i-1} \\ \ \\ \Rightarrow \sum_{i = 1}^{\lfloor \frac{n}{2} \rfloor + 1} \sum_{j=1}^{i} \Delta a_j \geqslant \sum_{i = n - \lfloor \frac{n}{2} \rfloor +1}^{n} \sum_{j=1}^{i} \Delta a_j $$

$\textbf{if } n = \textbf{odd number}, \lfloor \frac{n}{2} \rfloor = \frac{n-1}{2}$
$$ \sum_{i = 1}^{\frac{n+1}{2}} \sum_{j=1}^{i} \Delta a_j \geqslant \sum_{i = \frac{n+1}{2}+1}^{n} \sum_{j=1}^{i} \Delta a_j \\\ \ \\\ \xrightarrow{\textbf{两边+}} \sum_{i = 1}^{\frac{n+1}{2}}\sum_{j = 1}^{i} \Delta a_j \Rightarrow 2\sum_{i = 1}^{\frac{n+1}{2}} \sum_{j=1}^{i} \Delta a_j \geqslant \sum_{i = 1}^{n} \sum_{j=1}^{i} \Delta a_j \\\ \ \\\ 2\sum_{i=1}^{\frac{n+1}{2}}(\frac{n+1}{2}-i+1)\Delta a_i \geqslant \sum_{i=1}^{n} (n-i+1) \Delta a_i \\\ \ \\\ (\sum_{i = 1}^{n}(n-i+1) - 2\sum_{i = 1}^{\frac{n+1}{2}}(\frac{n+1}{2}-i+1)) \Delta a_i \leqslant 0 \\\ \ \\\ \sum_{i = 1}^{n} C_i \Delta a_i \leqslant 0 \\\ \ \\\ C_{i}=\left\{\begin{array}{ll} n-i+1 && i>\frac{n+1}{2} \\\ (n-i+1)-2\left(\frac{n+1}{2}-i+1\right)= i-2&& i \leqslant \frac{n+1}{2} \end{array}\right. $$

$\textbf{if } n = \textbf{even number}, \lfloor \frac{n}{2} \rfloor = \frac{n}{2}$
$$ \sum_{i=1}^{\frac{n}{2}+1} \sum_{j=1}^{i} \Delta a_{j} \geqslant \sum_{i=\frac{n}{2}+1}^{n} \sum_{j=1}^{i} \Delta a_{j} \xrightarrow{\text{减掉}i = n/2+1 \text{这一项}} \\\ \ \\\ \sum_{i=1}^{\frac{n}{2}} \sum_{j=1}^{i} \Delta a_{j} \geqslant \sum_{i=\frac{n}{2}+2}^{n} \sum_{j=1}^{i} \Delta a_{j} \\\ \ \\\ 2\sum_{i=1}^{\frac{n}{2}} \sum_{j=1}^{i} \Delta a_{j} \geqslant \sum_{i=1}^{n} \sum_{j=1}^{i} \Delta a_{j} - \sum_{i=1}^{\frac{n}{2}+1} \Delta a_{i} \\\ \ \\\ 2 \sum_{i=1}^{\frac{n}{2}}\left(\frac{n}{2}-i+1\right)\Delta a_{i} \geqslant \sum_{i=1}^{n}(n-i+1) \Delta a_{i}-\sum_{i=1}^{\frac{n}{2}+1} \Delta a_{i} \\\ \ \\\ \sum_{i = 1}^{n} C_i \Delta a_i \leqslant 0 \\\ \ \\\ C_{i}=\left\{\begin{array}{ll} n-i+1 && i>\frac{n}{2} +1\\\ i-2&& i \leqslant \frac{n}{2} \\\ n-i && i = \frac{n}{2}+1 \end{array}\right. $$
$$ i = \frac{n}{2} + 1 \Rightarrow C_i = \frac{n}{2}-1 \Rightarrow C_i = i - 2 \\\ \ \\\ C_{i}=\left\{\begin{array}{ll} n-i+1 && i>\frac{n}{2} +1\\\ i-2&& i \leqslant \frac{n}{2}+1 \end{array}\right. $$

$\textbf{iii)}$
综上所述

$$ C_{i}=\left\{\begin{array}{ll} n-i+1 && i>\lfloor \frac{n}{2} \rfloor +1\\\ i-2&& i \leqslant \lfloor \frac{n}{2}\rfloor + 1 \end{array}\right. \\\ \ \\\ \sum_{i = 1}^{n} C_i \Delta a_i \leqslant 0 $$

$i = 1, C_1 = -1 <0$
$\sum \Delta a_i + 1 \leqslant n$

$$ \left\{\begin{array}{l} a_{1} \leqslant n-1-\sum_{i=2}^{n} a_{i} \\\ a_{1} \geqslant \sum_{i=2}^{n} a_{i} \end{array}\right. $$

由此原问题转换为求满足条件 $a_1$ 的个数

$$ \textbf{cnt} = ( n-1-\sum_{i=2}^{n} a_{i} ) - (\sum_{i = 2}^{n} C_ia_i) +1 \\ \ \\ = n-\sum_{i=2}^{n} (C_i+1)a_{i} $$

$\textbf{iv) algorithm} $
$$ f(i) :=\Rightarrow \sum_{i=2}^{n} (C_i+1)a_{i}=i \\\ \ \\\ \text{方案数} \\ \ \\ \max\{0, n-\sum_{i=2}^{n} (C_i+1)a_{i}\}, \quad i \in [0, n-1] \\\ \ \\\ \textbf{ans = } \sum_{i = 0}^{n-1} (n-i) \cdot f(i) $$
$\quad \textbf{ calculate } f(i), \textbf{使用完全背包}$
$\quad \text{ 此时从 } \forall i \in[2, n] \text{ 的物品中选 }$
$\quad \text{ 第 } i \text{ 个物品重量为 } B_i = C_i + 1$
$\quad \text{ 可以重复选, 每种物品可以选 } a_i \text{次}$
$\quad \text{ 其中背包总重量不超过 }n-1, \text{ 求方案数}$

const int maxn = 5000 + 10;
int n, m;
int f[maxn], C[maxn];

void initDP() {
    Set(f, 0);
    f[0] = 1;

    int mid = n >> 1;
    _rep(i, 2, mid + 1) C[i] = i - 1;
    _rep(i, mid + 2, n) C[i] = n - i + 2;
}

int dp() {
    initDP();

    _rep(i, 2, n) _rep(j, C[i], n - 1) {
        f[j] = (f[j] + f[j - C[i]]) % m;
    }

    ll ans = 0;
    _rep(i, 0, n - 1) {
        ans = ans + 1ll * (n - i) * f[i] % m;
        ans %= m;
    }
    return ans;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);

    int res = dp();
    cout << res << endl;
}