|
||||||||||
Counting SequencesTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/65536 K (Java/Others)Total Submission(s): 3708 Accepted Submission(s): 1258 Problem Description 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. Input 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 Output The number of Perfect Sub-sequences mod 9901 Sample Input
Sample Output
Source | ||||||||||
|