首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#13191

漂亮的序列 对于给定的整数 m,我们称一个序列是“漂亮”的,如果它包含至少 2 个整数,并且有 2 个相邻数字的差不超过m。你的任务是计算一个给定的 n 个正整…

漂亮的序列

对于给定的整数 m,我们称一个序列是“漂亮”的,如果它包含至少 2 个整数,并且有 2 个相邻数字的差不超过m。你的任务是计算一个给定的 n 个正整数的序列中,有多少个子序列是漂亮的。

时间限制:6000

内存限制:65536

输入

输入第一行给出 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}。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p>参考代码<br/></p><pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int MOD = 1000000007; class FenwickTree { private:     vector&lt;int&gt; 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 &gt; n) return; // 超出范围的不处理         while (idx &lt;= n) {             tree[idx] = (tree[idx] + val) % MOD;             idx += idx &amp; -idx;         }     }     int query(int idx) {         idx++; // 转换为树状数组的索引         if (idx &lt; 0) return 0;         int res = 0;         while (idx &gt; 0) {             res = (res + tree[idx]) % MOD;             idx -= idx &amp; -idx;         }         return res;     } }; int main() {     ios_base::sync_with_stdio(false);     cin.tie(nullptr);     int n, m;     cin &gt;&gt; n &gt;&gt; m;     vector&lt;int&gt; a(n);     for (int i = 0; i &lt; n; ++i) {         cin &gt;&gt; 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 &gt; 0) {             if (b &amp; 1) res = res * a % mod;             a = a * a % mod;             b &gt;&gt;= 1;         }         return res;     };     long long T = (powmod(2, n, MOD) - 1 - n + MOD) % MOD;     long long ans = (T - S + MOD) % MOD;     cout &lt;&lt; ans &lt;&lt; '\n';     return 0; }</pre>
这道题暂未补解析。