TopCoder Statistics - Problem Statement

Problem Statement

Two sequences A and B are called similar if they have the same length and have the following property: we can obtain two identical sequences by deleting at most two elements of A and at most two elements of B. (The elements deleted from A don't have to have the same indices as the elements deleted from B. The order of the remaining elements in each sequence has to be preserved.)

You are given ints N and bound. Consider all the sequences with length N such that each element is an integer between 1 and bound, inclusive. Compute the number of ordered pairs of such sequences that are similar. Return this count modulo 1,000,000,009.

Definition

Class:: SimilarSequencesAnother
Method:: getCount
Parameters:: int, int
Returns:: int
Method signature:: int getCount(int N, int bound)
(be sure your method is public)

Constraints

N will be between 1 and 100, inclusive.
bound will be between 1 and 1,000,000,000, inclusive.

Examples

2

10

Returns: 10000

Any two 2-element sequences are similar. There are (10^2)^2 = 10,000 pairs of such sequences.
3

3

Returns: 687

In this case, two sequences are similar if they have at least one element in common. In other words, the two sequences are similar if there is a value that occurs in each of them. Let's count the pairs of sequences that are not similar. There are two possibilities: Each sequence contains the same value three times. For example, one sequence could be {1,1,1} and the other {3,3,3}. There are 6 such pairs. One sequence contains the same value three times, and the other contains the other two values, each of them at least once. For example, one sequence could be {2,3,2} and the other {1,1,1}. There are 2 * 3 * (2^3 - 2) = 36 such pairs. Thus, the total number of pairs of similar sequences is 3^6 - 6 - 36 = 687.
8

1

Returns: 1
100

123456789

Returns: 439681851
1

1

Returns: 1
1

2

Returns: 4
1

3

Returns: 9
1

4

Returns: 16
2

1

Returns: 1
2

2

Returns: 16
2

3

Returns: 81
2

4

Returns: 256
3

1

Returns: 1
3

2

Returns: 62
3

3

Returns: 687
3

4

Returns: 3676
4

1

Returns: 1
4

2

Returns: 234
4

3

Returns: 5343
4

4

Returns: 44524
100

1

Returns: 1
100

2

Returns: 217914523
100

3

Returns: 484211440
100

4

Returns: 679809206
100

5

Returns: 502551462
100

818395109

Returns: 404273259
99

756991212

Returns: 830642202
98

689860839

Returns: 847637721
97

943103013

Returns: 340414540
96

828895810

Returns: 882284188
95

691034647

Returns: 493638054
94

755719020

Returns: 359199298
93

483585463

Returns: 718729268
1

342136417

Returns: 784081955
2

122273295

Returns: 871833043
3

584150777

Returns: 906354115
4

850794159

Returns: 775966753
5

425899179

Returns: 366222125
6

179674399

Returns: 535318194
7

708938584

Returns: 796369975
8

252367977

Returns: 319823228
100

14158914

Returns: 793951634
100

365497827

Returns: 462703330
100

626580757

Returns: 489649654
100

907065911

Returns: 517442713
100

871160468

Returns: 247584739
10

226179342

Returns: 287634341
30

213358028

Returns: 947356867
50

23133551

Returns: 38333137
70

831509073

Returns: 307885020
90

21205922

Returns: 12756903
100

1000000000

Returns: 598436627
1

1000000000

Returns: 81
99

1251234

Returns: 815115868
100

555555555

Returns: 298174317

Statistics

Problem Statement for "SimilarSequencesAnother"

Problem Statement

Definition

Constraints

Examples