AGC041D Problem Scores

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

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

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

\sum_{i = 1}^{⌊ \frac{n}{2} ⌋ + 1} \sum_{j = 1}^{i} Δ a_{j} \geq \sum_{i = n - ⌊ \frac{n}{2} ⌋ + 1}^{n} \sum_{j = 1}^{i} Δ a_{j}

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

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

\sum_{i = 1}^{\frac{n + 1}{2}} \sum_{j = 1}^{i} Δ a_{j} \geq \sum_{i = \frac{n + 1}{2} + 1}^{n} \sum_{j = 1}^{i} Δ a_{j}

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

2 \sum_{i = 1}^{\frac{n + 1}{2}} \sum_{j = 1}^{i} Δ a_{j} \geq \sum_{i = 1}^{n} \sum_{j = 1}^{i} Δ a_{j}

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

2 \sum_{i = 1}^{\frac{n + 1}{2}} (\frac{n + 1}{2} - i + 1) Δ a_{i} \geq \sum_{i = 1}^{n} (n - i + 1) Δ a_{i}

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

\sum_{i = 1}^{n} c_{i} Δ a_{i} \leq 0

其中

c_{i} = {\begin{cases} i - 2 & i \leq \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} Δ a_{j} \geq \sum_{i = \frac{n}{2} + 2}^{n} \sum_{j = 1}^{i} Δ a_{j}

补一补：

2 \sum_{i = 1}^{\frac{n}{2}} \sum_{j = 1}^{i} Δ a_{j} \geq \sum_{i = 1}^{n} \sum_{j = 1}^{i} Δ a_{j} - \sum_{i = 1}^{\frac{n}{2} + 1} Δ a_{i}

拆个 $Σ$ ：

2 \sum_{i = 1}^{\frac{n}{2}} (\frac{n}{2} - i + 1) Δ a_{i} \geq \sum_{i = 1}^{n} (n - i + 1) Δ a_{i} - \sum_{i = 1}^{\frac{n}{2} + 1} Δ a_{i}

写成 $\sum c_{i} Δ a_{i} \leq 0$ 的形式，可以得到：

c_{i} = {\begin{cases} i - 2 & i \leq \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 \leq \frac{n}{2} + 1 \\ n - i + 1 & i > \frac{n}{2} + 1 \end{cases}

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

\sum_{i = 1}^{n} c_{i} Δ a_{i} \leq 0

其中

c_{i} = {\begin{cases} i - 2 & i \leq ⌊ \frac{n}{2} ⌋ + 1 \\ n - i + 1 & i > ⌊ \frac{n}{2} ⌋ + 1 \end{cases}

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

于是我们考虑确定 $a_{2} \sim a_{n}$ 的值，然后回过头来看看有多少个符合条件的 $a_{1}$ 。

我们发现只有两个条件：

{\begin{cases} a_{1} \leq n - 1 - \sum_{i = 2}^{n} a_{i} \\ a_{1} \geq \sum_{i = 2}^{n} c_{i} a_{i} \end{cases}

于是满足条件的 $a_{1}$ 个数就是：

max (0, n - \sum_{i = 2}^{n} (c_{i} + 1) a_{i})

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

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

于是复杂度 $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