1391 字
7 分钟
贡献法应用

贡献法应用#

贡献法适用于答案由大量方案、区间或组合共同构成的情形。直接枚举这些整体对象通常会产生重复计算;更有效的方式是选择一个更小的基本对象,统计它在多少个整体答案中出现,并把“出现次数 ×\times 单次贡献”累加。

本文的两道题都属于这一类:数组差异题把贡献对象选为排序后的数对或单个元素;函数题把贡献对象选为差分数组中的某个位置。

问题 E:数组差异#

题目重述#

给定 nn 个数,从中选择 kk 个数组成新数组。一个数组的差异度定义为其中任意两数差值的绝对值之和。要求所有 (nk)\binom n k 种选择方案的差异度总和,并对 109+710^9+7 取模。

关键观察#

将数组排序为

s[1]≤s[2]≤⋯≤s[n].s[1]\le s[2]\le \cdots \le s[n].

排序后任意一对下标 i<ji<j 的差值为 s[j]−s[i]s[j]-s[i]。固定这对数后,若一个 kk 元选择方案包含它们,则这对数向该方案的差异度贡献 s[j]−s[i]s[j]-s[i]。剩余 k−2k-2 个数可从其余 n−2n-2 个位置中选择,因此该数对被计入

(n−2k−2)\binom{n-2}{k-2}

次。

也可以进一步按单个元素统计。固定 s[i]s[i]:

  • 它作为较大值时,与前面 i−1i-1 个数形成正贡献;
  • 它作为较小值时,与后面 n−in-i 个数形成负贡献。

因此 s[i]s[i] 的系数为 (i−1)−(n−i)(i-1)-(n-i)。

解析#

根据上面的计数,答案为

ans=(n−2k−2)∑i=1n((i−1)−(n−i))s[i].\text{ans} = \binom{n-2}{k-2} \sum_{i=1}^{n}\bigl((i-1)-(n-i)\bigr)s[i].

组合数通过阶乘和逆元预处理。由于模数 109+710^9+7 为质数,使用快速幂计算 xp−2x^{p-2} 得到乘法逆元。

时间复杂度为 O(nlog⁡n)O(n\log n),瓶颈在排序;空间复杂度为 O(n)O(n)。

代码#

#include <bits/stdc++.h>
#include <iomanip>
#define ll long long
#define N 200005
using namespace std;
ll ans;
ll n, k;
ll t;
const ll mod = 1e9 + 7;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
vector<ll> s(n + 5, 0);
vector<ll> fact(n + 5, 0);
vector<ll> fact_inv(n + 5, 0);
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
sort(s.begin() + 1, s.begin() + n + 1);
auto qp = [&](ll x, ll k) {
ll res = 1;
while (k) {
if (k & 1)
res = (res * x) % mod;
x = (x * x) % mod;
k >>= 1;
}
return res;
};
auto init = [&]() {
fact[0] = 1;
fact_inv[0] = 1;
for (int i = 1; i <= n; i++) {
fact[i] = (fact[i - 1] * i) % mod;
fact_inv[i] = (fact_inv[i - 1] * i) % mod;
}
fact_inv[n] = qp(fact[n], mod - 2);
for (int i = n - 1; i >= 1; i--) {
fact_inv[i] = ((i + 1) * fact_inv[i + 1]) % mod;
}
};
init();
auto c = [&](ll n, ll m) { return (fact[n] * fact_inv[m] % mod * fact_inv[n - m] % mod); };
ll res = 0;
for (int i = 1; i <= n; i++) {
res = (res + (i - 1 - (n - i)) * s[i]) % mod;
}
res = (res * c(n - 2, k - 2)) % mod;
cout << res;
return 0;
}

问题 C:函数#

题目重述#

给定长度为 nn 的序列 v[1..n]v[1..n] 和 qq 次询问。对于每个区间 [l,r][l,r],要求所有连续子序列 v[x..y]v[x..y](l≤x<y≤rl\le x<y\le r)的 Lipschitz 常数之和。

序列 v[x..y]v[x..y] 的 Lipschitz 常数定义为满足

∣v[a]−v[b]∣≤K∣a−b∣|v[a]-v[b]|\le K|a-b|

的最小整数 KK,其中 x≤a<b≤yx\le a<b\le y。

关键观察#

令相邻差分为

d[i]=∣v[i+1]−v[i]∣.d[i]=|v[i+1]-v[i]|.

对任意 a<ba<b,由三角不等式可得

∣v[a]−v[b]∣≤∑i=ab−1∣v[i+1]−v[i]∣≤(b−a)max⁡a≤i<bd[i].|v[a]-v[b]| \le \sum_{i=a}^{b-1}|v[i+1]-v[i]| \le (b-a)\max_{a\le i<b}d[i].

因此 K=max⁡a≤i<bd[i]K=\max_{a\le i<b}d[i] 一定满足 Lipschitz 条件。

另一方面,若 d[p]d[p] 是区间内的最大相邻差分,取相邻两点 a=p,b=p+1a=p,b=p+1,则

∣v[p]−v[p+1]∣=d[p]≤K.|v[p]-v[p+1]|=d[p]\le K.

所以任意合法的 KK 都不能小于最大相邻差分。两边合并,连续子序列 v[x..y]v[x..y] 的 Lipschitz 常数恰好等于差分区间 d[x..y−1]d[x..y-1] 的最大值。

Lipschitz 常数与相邻差分最大值

解析#

询问 [l,r][l,r] 被转化为:求差分数组 d[l..r−1]d[l..r-1] 的所有非空连续子数组最大值之和。

对每个差分位置 ii 计算其作为最大值的贡献。设:

  • left[i]\text{left}[i] 为 ii 左侧最近的、满足 d[left[i]]>d[i]d[\text{left}[i]]>d[i] 的位置;若不存在,则为 l−1l-1;
  • right[i]\text{right}[i] 为 ii 右侧最近的、满足 d[right[i]]≥d[i]d[\text{right}[i]]\ge d[i] 的位置;若不存在,则为 rr。

左侧使用严格大于、右侧使用大于等于,是为了处理相等最大值。若一个子数组中最大值出现多次,这种边界定义会固定由其中一个位置承担贡献,避免重复计数。

当 d[i]d[i] 作为某个差分子数组的最大值时,左端点可选

i−left[i]i-\text{left}[i]

种,右端点可选

right[i]−i\text{right}[i]-i

种。因此 d[i]d[i] 的总贡献为

d[i]⋅(i−left[i])⋅(right[i]−i).d[i]\cdot(i-\text{left}[i])\cdot(\text{right}[i]-i).

每次询问用两遍单调栈求出左右边界,再累加所有位置的贡献。由于 q≤100q\le 100,按询问逐个线性处理区间即可通过。

单次询问复杂度为 O(r−l+1)O(r-l+1),总时间复杂度为 O(nq)O(nq),空间复杂度为 O(n)O(n)。

代码#

#include <bits/stdc++.h>
#include <iomanip>
#include <utility>
#define ll long long
#define N 200005
using namespace std;
ll ans;
ll n, k, m, q;
ll t;
#define pr pair<ll, ll>
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
vector<ll> s(n + 5, 0);
vector<ll> diff(n + 5, 0);
for (int i = 1; i <= n; i++) {
cin >> s[i];
diff[i - 1] = abs(s[i] - s[i - 1]);
}
vector<int> left(n + 5, 0);
vector<int> right(n + 5, 0);
while (q--) {
ll l, r;
cin >> l >> r;
if (l == r) {
cout << 0 << '\n';
continue;
}
r--;
stack<int> sta;
for (int i = l; i <= r; i++) {
while (sta.size() && diff[sta.top()] <= diff[i]) {
sta.pop();
}
left[i] = sta.empty() ? l - 1 : sta.top();
sta.push(i);
}
while (sta.size())
sta.pop();
for (int i = r; i >= l; i--) {
while (sta.size() && diff[sta.top()] < diff[i]) {
sta.pop();
}
right[i] = sta.empty() ? r + 1 : sta.top();
sta.push(i);
}
ll res = 0;
for (int i = l; i <= r; i++)
res += diff[i] * (i - left[i]) * (right[i] - i);
cout << res << '\n';
}
return 0;
}
贡献法应用
https://sanzenin.top/posts/obsidian/贡献法应用/
作者
Sanzenin 凪
发布于
2026-11-16
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取