# AGC041D Problem Scores

Author: Fanyi Pu

Published: 2020-03-04

Canonical: <https://pufanyi.com/blog/oi-icpc/atcoder/agc041-d>

AGC041D Problem Scores 题解。

问存在多少个长度为 $n\,(2\le n\le 5000)$ 的单调不减序列 $a$，满足 $1\le a_i\le n$，且对于任意 $k\,(1\le k<n)$，都有：对任意大小为 $k$ 的子集 $S$ 和大小为 $k+1$ 的子集 $T$，满足 $\sum_{x\in S}A_x<\sum_{x\in T}A_x$。答案对大质数 $m$ 取模。

首先需要发现一个性质，就是如果 $k=\left\lfloor\frac{n}{2}\right\rfloor$ 的时候满足了，那么其他的 $k$ 都能满足。为什么呢？首先是对于每个 $k$，显然如果满足了 $\sum_{i=1}^{k+1}a_i\ge \sum_{i=n-k+1}^na_i$，就满足所有的 $S$ 和 $T$ 了。然后如果满足了 $k=\left\lfloor\frac{n}{2}\right\rfloor$ 的情况，如果 $k>\left\lfloor\frac{n}{2}\right\rfloor$，考虑到序列单调不降，左边加上一个较大的数，右边加上一个较小的数，那么不等式肯定仍然成立。否则，如果 $k<\left\lfloor\frac{n}{2}\right\rfloor$，其实就是左边减去一个较小的数，右边加上一个较大的数，不等式也仍然成立。

那这个东西有什么用呢，我们考虑对一波式子。首先我们需要去掉一个单调性，我们构造一个差分数组 $\Delta a_i=a_i-a_{i-1}$，为了不让 $\Delta a_1$ 奇怪，我们就让 $a_0=1$，这样子其实就是 $a_i=1+\sum_{i=1}^n\Delta a_i$，然后我们的式子就变成了：

$$
\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor+1}\sum_{j=1}^i\Delta a_j\ge \sum_{i=n-\left\lfloor\frac{n}{2}\right\rfloor+1}^n\sum_{j=1}^i\Delta a_j
$$

这个下取整感觉很难受，我们就直接将 $n$ 奇偶讨论好了：

当 $n$ 是奇数时，$\left\lfloor\frac{n}{2}\right\rfloor=\frac{n-1}{2}$，也就是原式就变成了：

$$
\sum_{i=1}^{\frac{n+1}{2}}\sum_{j=1}^i\Delta a_j\ge \sum_{i=\frac{n+1}{2}+1}^n\sum_{j=1}^i\Delta a_j
$$

两边都加个 $\sum_{i=1}^{\frac{n+1}{2}}\sum_{j=1}^i\Delta a_j$ 把右边给补一下：

$$
2\sum_{i=1}^{\frac{n+1}{2}}\sum_{j=1}^i\Delta a_j\ge \sum_{i=1}^n\sum_{j=1}^i\Delta a_j
$$

根据套路，我们需要把前面的 $\Sigma$ 拆掉，于是我们拆掉它：

$$
2\sum_{i=1}^{\frac{n+1}{2}}\left(\frac{n+1}{2}-i+1\right)\Delta a_i\ge \sum_{i=1}^n\left(n-i+1\right)\Delta a_i
$$

考虑我们将 $a_i$ 差分的目的，其实就是想把左边的式子减过去，然后合并起来：

$$
\sum_{i=1}^nc_i\Delta a_i\le 0
$$

其中

$$
c_i=
\begin{cases}
i-2 & i\le \frac{n+1}{2}\\
n-i+1 & i>\frac{n+1}{2}
\end{cases}
$$

同样地，我们来考虑 $n$ 是偶数的情况：

$$
\sum_{i=1}^{\frac{n}{2}}\sum_{j=1}^i\Delta a_j\ge \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\ge \sum_{i=1}^n\sum_{j=1}^i\Delta a_j-\sum_{i=1}^{\frac{n}{2}+1}\Delta a_i
$$

拆个 $\Sigma$：

$$
2\sum_{i=1}^{\frac{n}{2}}\left(\frac{n}{2}-i+1\right)\Delta a_i\ge \sum_{i=1}^n\left(n-i+1\right)\Delta a_i-\sum_{i=1}^{\frac{n}{2}+1}\Delta a_i
$$

写成 $\sum c_i\Delta a_i\le 0$ 的形式，可以得到：

$$
c_i=
\begin{cases}
i-2 & i\le\frac{n}{2}\\
n-i & i=\frac{n}{2}+1\\
n-i+1 & i>\frac{n}{2}+1
\end{cases}
$$

不难发现当 $i=\frac{n}{2}+1$ 时，$n-i=\frac{n}{2}-1=i-2$，所以：

$$
c_i=
\begin{cases}
i-2 & i\le\frac{n}{2}+1\\
n-i+1 & i>\frac{n}{2}+1
\end{cases}
$$

综合奇偶两个式子，我们均可以得到：

$$
\sum_{i=1}^nc_i\Delta a_i\le 0
$$

其中

$$
c_i=
\begin{cases}
i-2 & i\le\left\lfloor\frac{n}{2}\right\rfloor+1\\
n-i+1 & i>\left\lfloor\frac{n}{2}\right\rfloor+1
\end{cases}
$$

我们回到题目，除了这个条件，我们再回过头来看看有什么缺的条件，仔细找了找好像只有 $\sum\Delta a_i+1\le n$ 了。

于是我们考虑确定 $a_2\sim a_n$ 的值，然后回过头来看看有多少个符合条件的 $a_1$。

我们发现只有两个条件：

$$
\begin{cases}
a_1\le n-1-\sum_{i=2}^na_i\\
a_1\ge \sum_{i=2}^nc_ia_i
\end{cases}
$$

于是满足条件的 $a_1$ 个数就是：

$$
\max\left(0, n-\sum_{i=2}^n\left(c_i+1\right)a_i\right)
$$

我们令 $f_i$ 表示 $\sum_{j=2}^n\left(c_j+1\right)a_j=i$ 的方案数，那么最终的答案就是 $\sum_{i=0}^{n-1} (n-i)\cdot f_i$。

我们最后要做的一件事情就是计算 $f_i$ 了，不难发现其实就是一个背包，第 $i$ 个物品重量 $c_i$，可以选 $a_i$ 个，直接大力 `dp` 过去即可。

于是复杂度 $\mathcal{O}(n^2)$。

[代码](https://atcoder.jp/contests/agc041/submissions/10518552)

```cpp
#define _CRT_SECURE_NO_WARNINGS

#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

inline char gc() {
    static const int L = 233333;
    static char sxd[L], *sss = sxd, *ttt = sxd;
    if (sss == ttt) {
        ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
        if (sss == ttt) {
            return EOF;
        }
    }
    return *sss++;
}

#ifndef _AT_HOME
#define dd c = gc()
#else
#define dd c = getchar()
#endif
inline char readalpha() {
    char dd;
    for (; !isalpha(c); dd);
    return c;
}

inline char readchar() {
    char dd;
    for (; c == ' '; dd);
    return c;
}

template <class T>
inline bool read(T& x) {
    bool flg = false;
    char dd;
    x = 0;
    for (; !isdigit(c); dd) {
        if (c == '-') {
            flg = true;
        } else if(c == EOF) {
            return false;
        }
    }
    for (; isdigit(c); dd) {
        x = (x * 10) + (c ^ 48);
    }
    if (flg) {
        x = -x;
    }
    return true;
}
#undef dd

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x < 10) {
        putchar(x | 48);
        return;
    }
    write(x / 10);
    putchar((x % 10) | 48);
}

template <class T>
inline void writesp(T x) {
    write(x);
    putchar(' ');
}

template <class T>
inline void writeln(T x) {
    write(x);
    puts("");
}

#define lowbit(x) (x & -x)

namespace dfcmd {

    typedef long long LL;

    const int maxn = 5005;

    int n, mod;

    int f[maxn];
    int xs[maxn];

    int Main() {
        read(n), read(mod);
        for (int i = 2, cntt = 1; i <= n; ++i, ++cntt) {
            xs[i] = cntt;
        }
        for (int i = n, cntt = 2; i >= 2; --i, ++cntt) {
            if (xs[i] <= cntt) {
                break;
            }
            xs[i] = cntt;
        }
        f[0] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = xs[i]; j < n; ++j) {
                f[j] += f[j - xs[i]];
                if (f[j] >= mod) {
                    f[j] -= mod;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += (LL) (n - i) * f[i] % mod;
            if (ans >= mod) {
                ans -= mod;
            }
        }
        writeln(ans);
        return 0;
    }
}

int main() {
    return dfcmd::Main();
}
```