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)$ 。

代码

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

Cite this post