[PAT顶级1030] 美丽子序列–树状数组dp
题目描述
一个正整数序列,所有元素不超过 $10^5$ , 定义美丽的子序列为:子序列存在一对相邻的元素,两者之差不大于 $m$ (也是个给定的正整数),求美丽子序列个数对 $10^9+7$ 取模。
样例
样例输入 #1
4 2
5 3 8 6
样例输出 #1
8
样例解释
(1) Indices {1, 2}, values {5, 3}
(2) Indices {1, 4}, values {5, 6}
(3) Indices {3, 4}, values {8, 6}
(4) Indices {1, 2, 3}, values {5, 3, 8}
(5) Indices {1, 2, 4}, values {5, 3, 6}
(6) Indices {1, 3, 4}, values {5, 8, 6}
(7) Indices {2, 3, 4}, values {3, 8, 6}
(8) Indices {1, 2, 3, 4}, values {5, 3, 8, 6}
思路
直接容斥,总非空子序列减去不存在相邻两数不大于 $m$ 的子序列就行了。非空子序列个数显然是 $2^n-1$
设 $dp[i]$ 为以第 $i$ 个元素为结尾,且不存在相邻两数不大于 $m$ 的子序列,那显然有 :
$$ dp[i]=\sum_{1\le j\text{<} i, |a[j]-a[i]|\text{>}m} dp[j] + 1 $$
其中那个 $1$ 就是只有他自己,只有一个数的子序列显然满足该条件。这个式子很显然,关于值域构造一个树状数组就能优化
那么最终的答案就是 $2^n-1-\sum_{i=1}^n dp[i]$ ,然后注意取模即可。
代码
#include <stdio.h>
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define N 100000
const int mod = 1000000007;
int add(int a, int b) { return (a + b >= mod) ? (a + b - mod) : (a + b); }
int sub(int a, int b) { return (a < b) ? (a - b + mod) : (a - b); }
int mul(int a, int b) { return 1ll * a * b % mod; }
int quick_pow(int x, int p)
{
int ans = 1;
while (p)
{
if (p & 1)
ans = mul(ans, x);
x = mul(x, x);
p >>= 1;
}
return ans;
}
int n, m;
int a[N + 10], dp[N + 10];
int tr[N + 10];
void bit_add(int k, int x)
{
for (; k <= N; k += (k & (-k)))
tr[k] = add(tr[k], x);
}
int bit_sum(int k)
{
int ret = 0;
for (; k; k -= (k & (-k)))
ret = add(ret, tr[k]);
return ret;
}
int bit_query(int l, int r) { return r >= l ? sub(bit_sum(r), bit_sum(l - 1)) : 0; }
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i)
{
dp[i] = add(add(bit_query(1, a[i] - m - 1), bit_query(a[i] + m + 1, N)), 1);
bit_add(a[i], dp[i]);
}
int reduce = 0;
for (int i = 1; i <= n; ++i)
reduce = add(reduce, dp[i]);
int ans = sub(sub(quick_pow(2, n), 1), reduce);
printf("%d", ans);
}