题解：CF2127F Hamed and AghaBalaSar

_Ink · 2025-08-09 00:39:16 · 题解

题解

Part 1.

首先要搞清楚 f(a) 在干嘛，是怎么算的，这个其实不困难。我们设 a_n = M，且不妨令 a_0 = M，有以下式子：

f(a) = \sum_{i=1}^{n-1} [a_i < M \land a_{i-1} = M](M - a_i)

也就是说，只要某个位置 i 前一个数是最大值而当前位置严格小于最大值，就会贡献 M-a_i。

所以我们可以只考虑某个位置产生的贡献，探究其总共能产生多少贡献。由于每一个位置产生贡献是相互独立的，所以只需要计算每个位置的贡献，然后相加即可得到答案。

Part 2.

记 F(L, S, M) 为一类数组的个数，其长度为 L，总和为 S，最大值为 M。

这是个经典问题，利用容斥原理可以计算得：

F(L,S,M)=\sum_{j=0}^{\lfloor \frac{S}{M+1} \rfloor} (-1)^j {L \choose j} {S+L-1-j(M+1) \choose L-1}

:::info[怎么求的？] 可以先阅读 OI Wiki-容斥原理，下面只作一些简单说明，为了通俗易懂，尽量避免了使用一些集合术语。

如果没有最大值的限制，那么是好求的。这本质是个“球盒模型”：把 S 个相同小球放入 L 个不同盒子中，允许盒空的方案数。利用插板法可算得方案数为：S+L-1 \choose L-1。

考虑最大值的限制，要计算所有数都小等于 M 的方案数，直接求是困难的，所以考虑计算存在数大等于 M+1 的方案数，再用总方案减去即可。

而存在数大等于 M+1 的所有方案其实是至少存在 1 个数，至少存在 2 个数，...，至少存在 \lfloor \frac{S}{M+1} \rfloor 个数大等于 M+1 这些方案的并集。容斥恰好就可以求这个东西。

至少存在 j 个数大等于 M+1 的方案数是好算的，记为 g(j)，则

g(j) = {L \choose j}{S+L-1-j(M+1) \choose L-1}

其含义即为，在 L 个位置中选了 j 个位置，让其先赋值为 M+1，此时总和剩下了 S-j(M+1)，再将这些总和任意分配给 L 个位置。

那么根据容斥原理，其存在数大等于 M+1 的总方案数即为：

\sum_{j=1}^{\lfloor \frac{S}{M+1} \rfloor} (-1)^{j-1} g(j)

而全集为 S+L-1 \choose L-1，两者相减即得到最终结果：

F(L,S,M)=\sum_{j=0}^{\lfloor \frac{S}{M+1} \rfloor} (-1)^j {L \choose j} {S+L-1-j(M+1) \choose L-1}

:::

Part 3.

大力推式子环节。

考虑一个产生贡献的位置，这个位置可以是 0 \sim M-1 的任意一个数，若剩下的位置个数为 L，可用总和为 S，最大值为 M。其贡献有：

\begin{aligned} && &\sum_{x=0}^{M-1}(M-x)F(L,S-x,M) \\ &\Rightarrow& &\sum_{x=0}^{M-1}(M-x)\sum_{j=0}^{\lfloor \frac{S-x}{M+1} \rfloor} (-1)^j {L \choose j} {S+L-1-j(M+1)-x \choose L-1} \\ &\Rightarrow& &\sum_{j=0}^{\lfloor \frac{S}{M+1} \rfloor} (-1)^j {L \choose j} \sum_{x=0}^{M-1}(M-x){S+L-1-j(M+1)-x \choose L-1} \end{aligned}

这个式子看起来有点变态，我们稍微化简一下，令 A=S+L-1-j(M+1)，B=L-1，然后拆一下式子，可以得到：

\sum_{j=0}^{\lfloor \frac{S}{M+1} \rfloor} (-1)^j {L \choose j} \Bigg[ \sum_{x=0}^{M-1}M{A-x \choose B} - \sum_{x=0}^{M-1}x{A-x \choose B} \Bigg]

下面我们来分别讨论中括号中的两个式子：

1. 上指标求和

上指标求和指的是：

\sum_{k=m}^{n} {k \choose m} = {n+1 \choose m+1}

我们定义一个 G(m,L,R)，有：

G(m,L,R) = \sum_{k=L}^{R} {k \choose m} ={R+1 \choose m+1} - {L \choose m+1}

2. 左式

显然有：

\sum_{x=0}^{M-1}M{A-x \choose B} = M \cdot G(B,A-M+1,A)

3. 右式

稍微推一下，可以得到：

\begin{aligned} && &\sum_{x=0}^{M-1}x{A-x \choose B} \\ &\Rightarrow& &\sum_{k=1}^{M-1}\sum_{x=k}^{M-1}{A-x \choose B} \\ &\Rightarrow& &\sum_{k=1}^{M-1} \Bigg[ {A-k+1 \choose B+1} - {A-M+1 \choose B+1} \Bigg] \\ &\Rightarrow& &G(B+1,A-M+2,A) - (M-1){A-M+1 \choose B+1} \\ \end{aligned}

将左右两式合并一下，最后的结果可以得到以下式子：

\begin{aligned} \sum_{j=0}^{\left\lfloor \frac{S}{M+1} \right\rfloor} (-1)^j {L \choose j} \Bigg[ & \; M \cdot G(B, A-M+1, A) \\ & - \Big( G(B+1, A-M+2, A) - (M-1){A-M+1 \choose B+1} \Big) \Bigg] \end{aligned}

（看起来好丑）

Part 4.

令:

A(L,S,M) = \displaystyle\sum_{x=0}^{M-1}(M-x)F(L,S-x,M)

我们现在可以很快地计算这个东西。考虑枚举最大值 M = 1\dots m，在确定 L 和 S 的情况下，对于一个最大值 M 只需要枚举 \lfloor \frac{S}{M+1} \rfloor 次，这部分是一个调和级数，总复杂度是 O(m \log m) 的。

现在考虑确定 L 和 S 的值。产生贡献的位置 i 有两种情况：

在 i=1，仅有一个这样的位置，除去该位置以及 a_n，剩下 L=n-2，S=m-M，所以其贡献为 A(n-2,m-M,M)。
在 i=2,3,\dots,n-1，有 n-2 个这样的位置，该位置前一个位置必须为 M，所以除去该位置，其前一个位置以及 a_n，剩下 L=n-3，S=m-2\cdot M，所以其贡献为 (n-2) \cdot A(n-3,m-2 \cdot M,M)。

所以答案即为：

Ans = \sum_{M=1}^{m} \bigg[ A(n-2,m-M,M) + (n-2) \cdot A(n-3,m-2 \cdot M,M) \bigg]

Code

constexpr int MOD = 1e9 + 7;
using Z = MInt<MOD>; //自动取模类

namespace comb {
    ...
} // namespace comb

Z G(int m, int l, int r)
{
    return comb::binom(r + 1, m + 1) - comb::binom(l, m + 1);
}

Z A(int l, int s, int m)
{
    Z sum = 0;
    for(int j = 0, p = 1; j <= s / (m + 1); j ++, p = -p){
        int A = s + l - 1 - j * (m + 1), B = l - 1;
        Z c1 = G(B, A - m + 1, A);
        Z c2 = G(B + 1, A - m + 2, A) - comb::binom(A - m + 1, B + 1) * (m - 1);
        sum += p * comb::binom(l, j) * (m * c1 - c2);
    }
    return sum;
}

void solve()
{
    int n, m; cin >> n >> m;
    Z sum = 0;
    for(int i = 1; i <= m; i ++){
        Z c1 = A(n - 2, m - i, i);
        Z c2 = A(n - 3, m - 2 * i, i);
        sum += c1 + (n - 2) * c2;
    }
    cout << sum << endl;
}

CF 评测记录