算法杂记 2023/02/21
目录今天分享的是 Codeforce 上的一道 2000 分的 组合 + 计数 题。目前的目标是从紫冲橙。
D. Moving Dots 2000
题面翻译
定义 \(f(S)\) 为 \(S\) 中 每个点按照同一速度向距离他最近的点的方向移动，如果两边相等，则走左边。当所有点停下之后的不同坐标个数。
给定点全集 \(S\) ，求 $ \sum\limits_{T\in S,|T|>1}f(T)$。
\(n=|S|\leq 3000\)。
题目描述
We play a game with $ n $ dots on a number line.
The initial coordinate of the $ i $ -th dot is $ x_i $ . These coordinates are distinct. Every dot starts moving simultaneously with the same constant speed.
Each dot moves in the direction of the closest dot (different from itself) until it meets another dot. In the case of a tie, it goes to the left. Two dots meet if they are in the same coordinate, after that, they stop moving.
After enough time, every dot stops moving. The result of a game is the number of distinct coordinates where the dots stop.
Because this game is too easy, calculate the sum of results when we play the game for every subset of the given $ n $ dots that has at least two dots. As the result can be very large, print the sum modulo $ 10^9+7 $ .
输入格式
The first line contains one integer $ n $ ( $ 2 \leq n \leq 3000 $ ).
The next line contains $ n $ integers $ x_1, x_2, \ldots, x_n $ ( $ 1 \leq x_1 < x_2 < \ldots < x_n \leq 10^9 $ ), where $ x_i $ represents the initial coordinate of $ i $ -th dot.
输出格式
Print the sum of results modulo $ 10^9+7 $ .
样例 #1
样例输入 #1
4 1 2 4 6样例输出 #1
11样例 #2
样例输入 #2
5 1 3 5 11 15样例输出 #2
30提示
In the first example, for a subset of size $ 2 $ , two dots move toward each other, so there is $ 1 $ coordinate where the dots stop.
For a subset of size $ 3 $ , the first dot and third dot move toward the second dot, so there is $ 1 $ coordinate where the dots stop no matter the direction where the second dot moves.
For $ [1, 2, 4, 6] $ , the first and second dots move toward each other. For the third dot, initially, the second dot and the fourth dot are the closest dots. Since it is a tie, the third dot moves left. The fourth dot also moves left. So there is $ 1 $ coordinate where the dots stop, which is $ 1.5 $ .
Because there are $ 6 $ subsets of size $ 2 $ , $ 4 $ subsets of size $ 3 $ and one subset of size $ 4 $ , the answer is $ 6 \cdot 1 + 4 \cdot 1 + 1 = 11 $ .
In the second example, for a subset of size $ 5 $ (when there are dots at $ 1 $ , $ 3 $ , $ 5 $ , $ 11 $ , $ 15 $ ), dots at $ 1 $ and $ 11 $ will move right and dots at $ 3 $ , $ 5 $ , $ 15 $ will move left. Dots at $ 1 $ , $ 3 $ , $ 5 $ will eventually meet at $ 2 $ , and dots at $ 11 $ and $ 15 $ will meet at $ 13 $ , so there are $ 2 $ coordinates where the dots stop.
这题设计的非常巧妙。刚开始玩没思路，因为和子集有关的题只会想到位运算去枚举，碰到这种 \(n = 3e4\) 的题完全没有思路。
这题做出来之后感觉很经典，就是考虑最小的枚举单元。在这个问题中，最小的枚举单元是 \((i, j)\) 二元组，因为如果只有这两个单元组的话，他们一定会碰面。所以我们枚举所有的二元组 \((i, j)\) ，存在一个区间 \([l, r]\) 当且仅当 \([l, r]\) 之间不存在其他的点时，这个二元组能贡献一个答案。且：
- \(x[i] - x[l] > x[j] - x[i]\)
- \(x[r] - x[l] \ge x[j] - x[i]\)
也就是说 \(l\) 和 \(i\) 的距离大于 \(i\) 和 \(j\) 的距离， \(r\) 和 \(j\) 的距离大于等于 \(i\) 和 \(j\) 的距离。这样的话，二元组 \((i,j)\) 一定能贡献一个答案。
有两种方法来确定，一种是利用二分查找，这样需要 \(O(\log n)\) 的时间。
另一种方法是，由于我们发现 随着 \(j\) 的增长， \([l, r]\) 的区间具有单调性， \(l\) 总应该更小， \(r\) 总应该更大，我们可以使用双指针解决这个问题。这样就可以在枚举 \(j\) 的过程中完成 \([l,r]\) 区间的维护。
在确定区间 \([l, r]\) 之后，那么一共有 \((l+1) + (n -r)\) 这么多点不影响二元组的贡献，考虑到子集的数量那么对于答案的贡献是：\(ad d = 2^{(l+1)+(n-r)}\) 。
我们只需要预处理所有可能的 \(2^{i} \% p | p是模数\)。这样我们就可以在规定时间内 \(O(n^2)/O(n^2\log n)\) 的时间内完成。
#include <bits/stdc++.h>
using namespace std;
#define DEBUG 0
#define vt std::vector
#define rep(i, l, r) for (ll i = (l); i < (r); ++ i)
#define per(i, l, r) for (ll i = (l); i >= (r); -- i)
using ll = long long;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5 + 50;
inline ll add(ll x, ll y){
return (x + y) % mod;
}
inline ll mul(ll x, ll y){
return (x * y) % mod;
}
void solve(){
int n;
std::cin >> n;
vt<ll> x(n);
rep (i, 0, n) std::cin >> x[i];
vt<ll> p2(n + 1, 1);
rep (i, 1, n + 1)
p2[i] = mul(p2[i - 1], 2ll);
ll ans = 0;
rep (i, 0, n){
int l = i, r = i;
// l] i ~ j [r
rep (j, i + 1, n){
while (l >= 0 && x[i] - x[l] <= x[j] - x[i])
-- l;
while (r < n && x[r] - x[j] < x[j] - x[i])
++ r;
ans = add(ans, mul(p2[l+1], p2[n-r]));
}
}
std::cout << ans << "\n";
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
// std::cin >> t;
while (t--) solve();
return 0;
}