2014
03-23

# Counting Sequences

For a set of sequences of integers｛a1，a2，a3，…an｝, we define a sequence｛ai1,ai2,ai3…aik｝in which 1<=i1<i2<i3<…<ik<=n, as the sub-sequence of ｛a1，a2，a3，…an｝. It is quite obvious that a sequence with the length n has 2^n sub-sequences. And for a sub-sequence｛ai1,ai2,ai3…aik｝，if it matches the following qualities: k >= 2, and the neighboring 2 elements have the difference not larger than d, it will be defined as a Perfect Sub-sequence. Now given an integer sequence, calculate the number of its perfect sub-sequence.

Multiple test cases The first line will contain 2 integers n, d（2<=n<=100000，1<=d=<=10000000） The second line n integers, representing the suquence

Multiple test cases The first line will contain 2 integers n, d（2<=n<=100000，1<=d=<=10000000） The second line n integers, representing the suquence

4 2
1 3 7 5

4

#include <cstdio>
#include <cstring>
#include <algorithm>

const int mod = 9901;
const int maxn = 100000 + 100;

int a[maxn];
int val[maxn];
int c[maxn];
int N,D,num;

int binary_find1(int x,int l,int r)
{
int ans = r;
while(l <= r)
{
int mid = (l + r) / 2;
if(val[mid] <= x) l = mid + 1,ans = mid;
else r = mid - 1;
}

return ans;
}

int binary_find2(int x,int l,int r)
{
int ans = l;
while(l <= r)
{
int mid = (l + r) / 2;
if(val[mid] < x) l = mid + 1;
else r = mid - 1,ans = mid;
}
return ans;
}
int get_sum(int x)
{
int sum = 0;
while(x > 0)
{
sum += c[x];
sum = sum % mod;
x -= (x & (-x));
}

return sum;
}

void insert(int x,int v)
{
while(x < num)
{
c[x] += v;
c[x] = c[x] % mod;
x += (x & (-x));
}
}

int main()
{
while(scanf("%d%d",&N,&D) == 2)
{
for(int i = 1;i <= N;i ++)
{
scanf("%d",&a[i]);
val[i] = a[i];
}
std::sort(val + 1,val + N + 1);
num = 2;
for(int i = 2;i <= N; i ++)
{
if(val[i] != val[i -1])
val[num ++] = val[i];
}
memset(c,0,sizeof(c));
for(int i = 1;i <= N;i ++)
{
int k = binary_find1(a[i],1,num - 1);
int x = binary_find1(a[i]+ D,1,num -1);
int y = binary_find2(a[i] - D,1,num-1);
int ans = 1;
ans += get_sum(x);
ans -= get_sum(y - 1);
ans %= mod;
insert(k,ans);
}

printf("%d\n",((get_sum(num-1) - N)%mod +mod)%mod);
}

return 0;
}

1. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？