A29401. 漂亮的序列
填空题
较难
知识点
题目描述
漂亮的序列
题目描述
时间限制：6000 内存限制：65536
对于给定的整数 m，我们称一个序列是“漂亮”的，如果它包含至少 2 个整数，并且有 2 个相邻数字的差不超过m。你的任务是计算一个给定的 n 个正整数的序列中，有多少个子序列是漂亮的。
输入
输入第一行给出 2 个正整数 n 和 m (2 ≤ n ≤ 105, 1 ≤ m ≤ 103)，随后一行给出序列中 n 个不超过 105 的正整数。同行数字间以空格分隔。
输出
输出原始序列中漂亮子序列的个数。因为答案可能非常大，所以你需要输出对 1000000007 (109 + 7) 取模后的结果。
样例输入
4 2
5 3 8 6样例输出
8提示
样例解释：
1、子序列下标为 {1, 2}, 对应值为 {5, 3}；
2、子序列下标为 {1, 4}, 对应值为 {5, 6}；
3、子序列下标为 {3, 4}, 对应值为 {8, 6}；
4、子序列下标为 {1, 2, 3}, 对应值为 {5, 3, 8}；
5、子序列下标为 {1, 2, 4}, 对应值为 {5, 3, 6}；
6、子序列下标为 {1, 3, 4}, 对应值为 {5, 8, 6}；
7、子序列下标为 {2, 3, 4}, 对应值为 {3, 8, 6}；
8、子序列下标为 {1, 2, 3, 4}, 对应值为 {5, 3, 8, 6}。
参考答案
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
class FenwickTree {
private:
vector<int> tree;
int n;
public:
FenwickTree(int size) : n(size) {
tree.assign(n + 2, 0); // 索引从1到n+1
}
void update(int idx, int val) {
idx++; // 树状数组从1开始
if (idx > n) return; // 超出范围的不处理
while (idx <= n) {
tree[idx] = (tree[idx] + val) % MOD;
idx += idx & -idx;
}
}
int query(int idx) {
idx++; // 转换为树状数组的索引
if (idx < 0) return 0;
int res = 0;
while (idx > 0) {
res = (res + tree[idx]) % MOD;
idx -= idx & -idx;
}
return res;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int max_a = *max_element(a.begin(), a.end());
int max_val = max_a + m;
FenwickTree bit(max_val);
long long sum_dp = 0;
int total_sum = 0;
for (int ai : a) {
int left = ai - m - 1;
int sum_left = bit.query(left);
int right = ai + m;
int sum_right = (total_sum - bit.query(right) + MOD) % MOD;
int dp_i = (sum_left + sum_right + 1) % MOD;
sum_dp = (sum_dp + dp_i) % MOD;
bit.update(ai, dp_i);
total_sum = (total_sum + dp_i) % MOD;
}
long long S = (sum_dp - n + MOD) % MOD;
// 计算2^n mod MOD
auto powmod = [](long long a, int b, int mod) {
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
};
long long T = (powmod(2, n, MOD) - 1 - n + MOD) % MOD;
long long ans = (T - S + MOD) % MOD;
cout << ans << '\n';
return 0;
}
上一题
下一题