图算法和图模型(六)

spfa判负环，差分约束系统
状态图，隐式图等等
图论最短路算法中一些比较精彩的应用

差分约束

$\textbf{algorithm:}\ \text{system of diffrence constraints}$

• $\forall i, j , \quad x_j - x_i \leqslant b_k$
  $\Longrightarrow w(i, j) = b_k$
  $\textbf{let} \ \text{src, } \forall u \in V(G), w(src, u) = 0$

• $\text{run } \textbf{spfa}()$
  $\textbf{if} \ \text{negative cycle exists, } \text{solution}=\emptyset$
  $\textbf{if} \ \text{no nega-cycle, } \text{solution = } [\cdots]$

$\textbf{proof}$
$\forall e(u, v), \quad l(v) > l(u) + w(u, v)$
$\sum l(v) > \sum l(u) + \sum w(u, v) , \quad \sum w(u, v) < 0$
$~~~~~~$$\Rightarrow \sum l(v) = \sum l(u)$

$\forall u \in V(G), \text{bellman-Ford never stop, no solution}$

$\textbf{problem}$
以 $v$ 为终点的边权值减小 $k$, 以 $v$ 为起点的边权值增加 $k$
变化后所有边的权值非负，并且尽量大

$$\begin{gathered} \forall e(a, b), \quad w(a, b) + \sum_{k \rightarrow a}(k)(a)- \sum_{k \rightarrow b} (k)(b) \geqslant x \\ \ \\ \text{target:=} x_{\max} \end{gathered}$$

• $\textbf{consider} \ x \text{ value range, } x \text{ is non-negative}$
  $x \geqslant 1$
• $\text{system of} \ \textbf{difference} \ \textbf{constraints}$
  $\sum_{k\rightarrow b} (k)(b) - \sum_{k \rightarrow a}(k)(a) \leqslant w(a, b) - x$
  $w(a, b) - x_{\max} \leqslant w(a, b) - x \leqslant w(a, b) - x_{\min}$
  $\lim_{lhs} (\textbf{not} \ \textbf{satisfy}) \longleftrightarrow \lim_{rhs} (\textbf{satisfy})$
  不等式右边比左边，更趋向于满足差分约束系统
  $x \in [1, \max\{w(a, b)\}]$

$\textbf{algorithm:} \ \textbf{binary-search}$
$\text{satisfy system, spfa() return true}$
$\text{not satisfy system, spfa() return false}$
$\textbf{if} \ \textbf{and} \ \textbf{only} \ \textbf{if} \ \text{no} \text{ nega-Cycle, satisfy}$

• $\text{if} \ \textbf{spfa}(x_{\max} + 1)=\text{true, solution} = \infty$
• $\text{if} \ \textbf{spfa}(x_{\min}) = \text{false, solution} = \emptyset$
  $\text{check} \ \textbf{mid}(x_{\min}, x_{\max}) \Leftrightarrow \textbf{mid}(L, R)$
  $~~~~~~$$\text{if} \ \textbf{mid} \ \text{satisfy }, L = \text{mid}, \ \textbf{mid} \ \uparrow$
  $~~~~~~$$\text{else } R = \textbf{mid}, \ \textbf{mid} \ \downarrow$

思路还是常见的二分，如果中间值满足
就尝试增加中间值，让它尽可能往 $\textbf{not} \ \textbf{satisfy}$ 方向靠
直到不满足为止

否则，就减小中间值，让它更容易 $\textbf{satisfy}$

UVA11478

const int maxn = 500 + 10;
const int inf = 0x3f3f3f3f;
int n, m;

// == Graph definition ==
vector<int> G[maxn];

class Edge {
public:
    int to, weight;
    Edge() {}
    Edge(int t, int w) : to(t), weight(w) {}
};

vector<Edge> edges;

void initG() {
    edges.clear();
    _for(i, 0, maxn) G[i].clear();
}

void addEdge(int u, int v, int w) {
    edges.push_back(Edge(v, w));
    G[u].push_back(edges.size() - 1);
}
// == Graph finished ==
int cnt[maxn], inq[maxn];
int D[maxn];

void initSPFA() {
    Set(cnt, 0);
    Set(inq, 0);
    Set(D, inf);
}

// true: nega-cycle
// false: non-negaCycle
int spfa() {
    initSPFA();
    queue<int> que;
    _rep(i, 1, n) {
        D[i] = 0;
        que.push(i);
        inq[i] = true;
    }

    while (!que.empty()) {
        int x = que.front();
        que.pop();
        inq[x] = 0;

        _for(i, 0, G[x].size()) {
            const Edge& e = edges[G[x][i]];
            int y = e.to;

            if(D[y] > D[x] + e.weight) {
                D[y] = D[x] + e.weight;
                if(!inq[y]) {
                    que.push(y);
                    inq[y] = true;

                    if(++cnt[y] > n) return true;
                }
            }
        }
    }
    return false;
}

bool check(int x) {
    _for(i, 0, edges.size()) {
        edges[i].weight -= x;
    }
    bool ret = spfa();
    _for(i, 0, edges.size()) {
        edges[i].weight += x;
    }

    return !ret;
}

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

        // build graph
        int ud = 0;
        _for(i, 0, m) {
            int u, v, d;
            scanf("%d%d%d", &u, &v, &d);
            addEdge(u, v, d);
            ud = max(ud, d);
        }
        // build finished
        // x in [1, ud]
        //debug(ud);

        if(check(ud + 1)) printf("Infinite\n");
        else if(!check(1)) printf("No Solution\n");
        else {
            int ans = 1;
            int L = 2, R = ud;

            while (L <= R) {
                int mid = (L + R) >> 1;
                //debug(mid);
                if(check(mid)) {
                    ans = mid;
                    L = mid + 1;
                }
                else R = mid - 1;
            }
            printf("%d\n", ans);
        }
    }
}

状态图编码问题

以 $\textbf{colored} \ \textbf{cubes} \ \textbf{为例}$

群运算观点下的图形变换

POJ2741

$\text{change posture of cubes}$
改变 $\text{cubes}$ 的 $\textbf{posture}$
本质是一个$\textbf{置换(permutation)}$

由 $\Omega \rightarrow \Omega$ 的变换组成的集合称为置换
$S_n = S(\Omega)$

• $S_n \text{ 的单位元定义: } \forall \pi \in S_n, \ \pi e = \pi = e\pi$
  $~~~~~~$$e:= \textbf{for} \ \forall i \in [1, n]$
  $~~~~~~~~~~$$A(i) = i$

• $\pi: i \mapsto \pi(i), i = 1, 2, \cdots, n$

$$\begin{gathered} \pi:\left(\begin{array}{ccc} 1 & 2 & \ldots & n \\ i_{1} & i_{2} & \ldots & i_{n} \end{array}\right) \\ \ \\ i_k \in \{1, 2, \cdots, n\} \end{gathered}$$

$~~~~~~$其本质是构成了一个全排列映射

$$\begin{gathered} \pi:\left(\begin{array}{ccc} 1 & 2 & \ldots & n \\ \downarrow & \downarrow & \ & \downarrow \\ i_{1} & i_{2} & \ldots & i_{n} \end{array}\right) \end{gathered}$$

• $S_n$ 上的乘法运算其实是置换的合成
  构成了 $n$ 元对称群

$\textbf{example}$

$\textbf{algorithm1}$
$\textbf{permutation} \ \textbf{groups}$

• $\textbf{for} \ \forall i \in [1, n], e:\Rightarrow A(i) = i$

$$\begin{gathered} \pi_{\text{left}} A= D \Rightarrow \\ \ \\ \textbf{trans} = \pi_{\text{left}}, \quad \textbf{rot}\text{(trans, A):} \end{gathered}$$

$~~~~~~$$\textbf{for} \ \forall i \in [1, n], \textbf{let} \ e = [A(i)]$
$~~~~~~~~~~$$\text{eg: }\quad \pi_{\text{left}}(i) = p$
$~~~~~~~~~~$$D=\pi^{k} = (\pi_k\pi_{k-1}\cdots \pi_2\pi_1) e$
$~~~~~~~~~~$$D(i) = \textbf{trans(A(i))}, \text{ return } D$

$\textbf{algorithm2} \ \textbf{逆运算}$

$$\begin{gathered} (\pi_1 \pi_2 \cdots \pi_k) A = D \Longrightarrow \\ \ \\ A = (\pi_k^{-1})(\pi_{k-1}^{-1}) \cdots (\pi_1^{-1})D \end{gathered}$$

$\textbf{permutation} \ \textbf{inversion}$
$~~~~~~$$\textbf{for} \ \forall x \in [1, n]$
$~~~~~~~~~~$$\pi(x) = p$
$~~~~~~~~~~$$\textbf{do} \ A(p) \gets A(x)$

$\textbf{main} \ \textbf{algorithm}$

$\textbf{check()}$
$\text{get inversion: } ori(i) \gets cube(i)$

$\textbf{for} \ \forall k \in \textbf{faces}[0, 1, \cdots, 5], \textbf{tot} = 0$
$~~~~~~$$\text{get } \ \textbf{Max-color}$
$~~~~~~$$\textbf{for} \ \forall i \in \text{ori}[1, \cdots, n]$
$~~~~~~~~~~$$\textbf{Max-color=} \max(\textbf{Max-color}, \ \textbf{cnt}(ori(i, k)))$
$~~~~~~$$\text{tot} = \sum (n - \textbf{colored-Max-face})$
$\textbf{ans} \ \text{=} \ \min(\textbf{ans,} \ \textbf{tot})$

$\textbf{dfs}(d)$
$~~~~~~$$\textbf{for} \ \forall i \in [0, 23)$
$~~~~~~~~~~$$\text{cube(d) shapes as } \textbf{posture} \ R(d) = i$
$~~~~~~~~~~$$\textbf{dfs}(d + 1)$

// == enumerate permutation ==
/*
int LEFT[] = {4, 0, 2, 3, 5, 1};
int UP[] = {2, 1, 5, 0, 4, 3};

void rot(int *trans, int *A) {
    int q[6];
    memcpy(q, A, sizeof(q));
    _for(i, 0, 6) A[i] = trans[q[i]];
}

void enumerate() {
    int E[6] = {0, 1, 2, 3, 4, 5};

    _for(i, 0, 6) {
        int A[6];
        memcpy(A, E, sizeof(E));
        if(i == 0) rot(UP, A);
        if(i == 1) {
            rot(LEFT, A);
            rot(UP, A);
        }
        if(i == 3) {
            rot(UP, A);
            rot(UP, A);
        }
        if(i == 4) {
            rot(LEFT, A);
            rot(LEFT, A);
            rot(LEFT, A);
            rot(UP, A);
        }
        if(i == 5) {
            rot(LEFT, A);
            rot(LEFT, A);
            rot(UP, A);
        }

        _for(k, 0, 4) {
            printf("{%d, %d, %d, %d, %d, %d},\n", A[0], A[1], A[2], A[3], A[4], A[5]);
            rot(LEFT, A);
        }
    }
}
// == enumerate finsihed ==

int main() {
    freopen("out.txt", "w", stdout);
    enumerate();
}
*/

/*
{2, 1, 5, 0, 4, 3},
{2, 0, 1, 4, 5, 3},
{2, 4, 0, 5, 1, 3},
{2, 5, 4, 1, 0, 3},
{4, 2, 5, 0, 3, 1},
{5, 2, 1, 4, 3, 0},
{1, 2, 0, 5, 3, 4},
{0, 2, 4, 1, 3, 5},
{0, 1, 2, 3, 4, 5},
{4, 0, 2, 3, 5, 1},
{5, 4, 2, 3, 1, 0},
{1, 5, 2, 3, 0, 4},
{5, 1, 3, 2, 4, 0},
{1, 0, 3, 2, 5, 4},
{0, 4, 3, 2, 1, 5},
{4, 5, 3, 2, 0, 1},
{1, 3, 5, 0, 2, 4},
{0, 3, 1, 4, 2, 5},
{4, 3, 0, 5, 2, 1},
{5, 3, 4, 1, 2, 0},
{3, 4, 5, 0, 1, 2},
{3, 5, 1, 4, 0, 2},
{3, 1, 0, 5, 4, 2},
{3, 0, 4, 1, 5, 2},
*/


const int D[24][6] = {
        {2, 1, 5, 0, 4, 3},
        {2, 0, 1, 4, 5, 3},
        {2, 4, 0, 5, 1, 3},
        {2, 5, 4, 1, 0, 3},
        {4, 2, 5, 0, 3, 1},
        {5, 2, 1, 4, 3, 0},
        {1, 2, 0, 5, 3, 4},
        {0, 2, 4, 1, 3, 5},
        {0, 1, 2, 3, 4, 5},
        {4, 0, 2, 3, 5, 1},
        {5, 4, 2, 3, 1, 0},
        {1, 5, 2, 3, 0, 4},
        {5, 1, 3, 2, 4, 0},
        {1, 0, 3, 2, 5, 4},
        {0, 4, 3, 2, 1, 5},
        {4, 5, 3, 2, 0, 1},
        {1, 3, 5, 0, 2, 4},
        {0, 3, 1, 4, 2, 5},
        {4, 3, 0, 5, 2, 1},
        {5, 3, 4, 1, 2, 0},
        {3, 4, 5, 0, 1, 2},
        {3, 5, 1, 4, 0, 2},
        {3, 1, 0, 5, 4, 2},
        {3, 0, 4, 1, 5, 2}
};

// D[r[i]] get posture of ith cube

int n;
const int maxn = 4;
int ori[maxn][6];
int cube[maxn][6];
int r[maxn];
int ans;
vector<string> data;

void init() {
    ans = n * 6;
    data.clear();
    Set(r, 0);
}

inline int getID(const char *name) {
    string str(name);
    _for(i, 0, data.size()) {
        if(data[i] == str) return i;
    }
    data.push_back(str);
    return data.size() - 1;
}

// == check ==
void inv(int ori[][6], const int cube[][6]) {
    _for(i, 0, n) _for(j, 0, 6) {
        int p = D[r[i]][j];
        ori[i][p] = cube[i][j];
    }
}

void check() {
    inv(ori, cube);

    int tot = 0;
    _for(k, 0, 6) {
        int Max = 0;
        int cnt[maxn * 6];
        Set(cnt, 0);
        _for(i, 0, n) Max = max(Max, ++cnt[ori[i][k]]);
        tot += n - Max;
    }
    ans = min(ans, tot);
}
// == check finished ==

// == dfs ==
void dfs(int d) {
    if(d == n) check();
    else {
        _for(i, 0, 24) {
            r[d] = i;
            dfs(d + 1);
        }
    }
}
// == dfs finished ==

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d", &n) == 1 && n) {
        init();

        // get data of cubes
        _for(i, 0, n) _for(j, 0, 6) {
            char name[30];
            scanf("%s", name);
            cube[i][j] = getID(name);
        }

        dfs(1);

        printf("%d\n", ans);
    }
}

状态空间建图

UVALive4128

• $\textbf{state} \ \textbf{transition} \ \textbf{equation}$
  

$\textbf{ii)} \ \textbf{start} \ \textbf{and} \ \textbf{end} \ \textbf{state}$

$\textbf{algorithm}$

• $\textbf{hash-coding} \ \textbf{for} \ \textbf{every} \ \textbf{state}$
  $\textbf{for} \ \forall dir, \quad \textbf{add(0,} \ \textbf{Hash}(r_1, c_1, dir, 1), cost)$
  $\textbf{for} \ \forall \text{r, c}, \text{ according to equation}$
  $~~~~~~$$\textbf{u}(r,c), \textbf{v}(nr, nc)$
  $~~~~~~$$\textbf{add}(\textbf{Hash}(\textbf{u}, dir, doubled), \textbf{Hash}(\textbf{v}, nDir, nDoubled), cost)$

• $\textbf{run} \ Dijkstra()$
  $~~~~~~$$\textbf{for} \ \forall dir \in[0, 4), \forall doubled \in [0,2)$
  $~~~~~~~~~~$$\text{get } \min\textbf{D}(\text{Hash}(\text{end},dir, double))$

const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, -1, 0, 1};
const int UP = 0, LEFT = 1, DOWN = 2, RIGHT = 3;
const int inv[] = {2, 3, 0, 1};

const int maxn = 100 + 5;
int R, C, r1, c1, r2, c2;
int cost[maxn][maxn][4];
int N;
const int maxN = maxn * maxn * 8 + 5;
const int inf = 0x3f3f3f3f;

inline int read() {
    int x;
    scanf("%d", &x);
    return x;
}

// == Graph defintion ==
vector<int> G[maxN];

class Edge {
public:
    int from, to, weight;
    Edge() {}
    Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
};

vector<Edge> edges;

class Node {
public:
    int u, dist;
    bool operator< (const Node& rhs) const {
        return dist > rhs.dist;
    }

    Node() {}
    Node(int u, int d) : u(u), dist(d) {}
};

void initG() {
    edges.clear();
    _for(i, 0, maxN) G[i].clear();
}

void addEdge(int u, int v, int w) {
    edges.push_back(Edge(u, v, w));
    G[u].push_back(edges.size() - 1);
}
// == Graph finsihed ==

// == build data ==
int id[maxn][maxn][4][2];
int tot = 0;

inline int ID(int r, int c, int dir, int doubled) {
    int& x = id[r][c][dir][doubled];
    if(x != 0) return x;
    x = ++tot;
    return x;
}

void init() {
    tot = 0;
    Set(id, 0);
}
// [1, R], [1, C]
inline bool valid(int r, int c, int dir) {
    if(r <= 0 || r > R || c <= 0 || c > C) return false;
    return cost[r][c][dir] > 0;
}
// == data finished ==

// == build graph ==
void build() {
    _for(dir, 0, 4) if(valid(r1, c1, dir)) {
        int u = ID(r1+dr[dir], c1+dc[dir], dir, 1);
        assert(u >= 1);
        int w = cost[r1][c1][dir] * 2;
        addEdge(0, u, w);
    }

    _rep(r, 1, R) _rep(c, 1, C) _for(dir, 0, 4) if(valid(r, c, inv[dir])) {
        _for(nDir, 0, 4) if(valid(r, c, nDir)) {
            _for(doubled, 0, 2) {
                int nr = r + dr[nDir];
                int nc = c + dc[nDir];
                int w = cost[r][c][nDir];
                int nDoubled = 0;

                if(nDir != dir) {
                    nDoubled = 1;
                    if(!doubled) w += cost[r][c][inv[dir]];
                    w += cost[r][c][nDir];
                }

                addEdge(ID(r, c, dir, doubled), ID(nr, nc, nDir, nDoubled), w);
            }
        }
    }
}
// == build finsihed ==

// == dijkstra ==
int D[maxN], vis[maxN];

void initDij(int st) {
    Set(D, inf);
    D[st] = 0;
    Set(vis, 0);
}

void dijkstra(int st) {
    initDij(st);
    priority_queue<Node> que;
    que.push(Node(st, 0));

    while (!que.empty()) {
        int x = que.top().u;
        que.pop();
        if(vis[x]) continue;
        vis[x] = 1;

        _for(i, 0, G[x].size()) {
            const Edge& e = edges[G[x][i]];
            int y = e.to;

            if(D[y] > D[x] + e.weight) {
                D[y] = D[x] + e.weight;
                que.push(Node(y, D[y]));
            }
        }
    }
}
// == dijkstra finsihed ==

// == solve ==
void solve(int& ans) {
    _for(dir, 0, 4) _for(doubled, 0, 2) {
        int ed = ID(r2, c2, dir, doubled);
        int res = D[ed];
        if(!doubled) res += cost[r2][c2][inv[dir]];
        ans = min(ans, res);
    }
}
// == solve finsihed ==

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    while (scanf("%d%d%d%d%d%d", &R, &C, &r1, &c1, &r2, &c2) == 6 && R) {
        init();
        initG();

        // input grid data
        _rep(r, 1, R) {
            _rep(c, 1, C - 1) cost[r][c][RIGHT] = cost[r][c+1][LEFT] = read();
            if(r != R) {
                _rep(c, 1, C)  cost[r][c][DOWN] = cost[r+1][c][UP] = read();
            }
        }
        N = R*C*8 + 1;

        // build graph
        build();

        // run dijkstra
        dijkstra(0);

        // solve
        int ans = inf;
        solve(ans);

        printf("Case %d: ", ++kase);
        if(ans == inf) printf("Impossible\n");
        else printf("%d\n", ans);
    }
}

差分dp

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

Problem Scores

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

$\textbf{algorithm1:} \ \text{dp()}$

• $\textbf{0-1} \ \text{背包}$

  • $$\begin{gathered} 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. \end{gathered}$$

  • $(i-1) \xrightarrow{update()} (i)$
  • $\textbf{for} \ \forall j = n \ \textbf{downto} \ V_i$

• $\textbf{完全背包}$

  • $$\begin{gathered} 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. \end{gathered}$$

  • $(i) \xrightarrow{update()} (i\textbf{th} \ \textbf{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)}$

$$\begin{gathered} \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) \end{gathered}$$

$$\begin{gathered} \text{根据序列的单调性，} k < \lfloor \frac{n}{2}\rfloor \\ \ \\ \text{相当于} (\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{ 不等式仍然成立} \end{gathered}$$

$\text{所以只要有 } k = \lfloor \frac{n}{2} \rfloor \text{ 成立，所有情况都成立}$

$\textbf{ii)} \ \textbf{差分数组的构造}$

$$\begin{gathered} \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 \end{gathered}$$

• $\textbf{if} \ n = \textbf{odd} \ \textbf{number}, \lfloor \frac{n}{2} \rfloor = \frac{n-1}{2}$

$$\begin{gathered} \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{\text{两边+}} \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{gathered} 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{gathered}\right. \end{gathered}$$

• $\textbf{if} \ n = \textbf{even} \ \textbf{number}, \lfloor \frac{n}{2} \rfloor = \frac{n}{2}$

$$\begin{gathered} \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{gathered} n-i+1 && i>\frac{n}{2} +1\\ i-2&& i \leqslant \frac{n}{2} \\ n-i && i = \frac{n}{2}+1 \end{gathered}\right. \end{gathered}$$

$$\begin{gathered} i = \frac{n}{2} + 1 \Rightarrow C_i = \frac{n}{2}-1 \Rightarrow C_i = i - 2 \\ \ \\ C_{i}=\left\{\begin{gathered} n-i+1 && i>\frac{n}{2} +1\\ i-2&& i \leqslant \frac{n}{2}+1 \end{gathered}\right. \end{gathered}$$

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

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

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

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

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

$$\begin{gathered} \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} \end{gathered}$$

$\textbf{iv)}\ \textbf{algorithm}$

$$\begin{gathered} 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] \\ \ \\ \text{ans = } \sum_{i = 0}^{n-1} (n-i) \cdot f(i) \end{gathered}$$

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

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;
}