TopCoder Statistics - Problem Statement

Problem Statement

The time limit for this problem is 3 seconds.

A bug lives on an N times N square grid. The distance between cells (r1,c1) and (r2,c2) in the grid is |r1-r2| + |c1-c2|.

The bug moves by making short jumps. You are given the int[] D containing small nonnegative integers that describe the bug's movement. The bug can jump from cell (r1,c1) to cell (r2,c2) if and only if their distance is an element of D.

Given are N, D and the number J of consecutive jumps the bug must make. The bug can start its journey anywhere on the grid. Count all possible paths of the bug, and return that count modulo 10^9 + 7. (Each path is a sequence of J+1 cells the bug stood on, and two paths are distinct if these sequences are distinct.)

Definition

Class:: ShortBugPaths
Method:: count
Parameters:: int, int[], int
Returns:: int
Method signature:: int count(int N, int[] D, int J)
(be sure your method is public)

Notes

The bug is not allowed to jump outside the grid.

Constraints

N will be between 1 and 10^9, inclusive.
D will be non-empty.
Elements of D will be between 0 and 10, inclusive.
Elements of D will be distinct.
J will be between 0 and 10, inclusive.

Examples

3

{1}

1

Returns: 24

The bug starts anywhere on the grid and then jumps to a neighboring cell.
123456789

{0}

3

Returns: 643499475

The bug starts anywhere on the grid and then jumps on the spot three times. The return value is (123456789 * 123456789) mod (10^9 + 7).
5

{0, 10, 2}

4

Returns: 38281

The answer would have been the same for D = {2, 0} because no two cells of this grid have distance 10.
1

{1}

0

Returns: 1
1

{1}

1

Returns: 0
5

{10}

10

Returns: 0
1000

{0,1}

1

Returns: 4996000

There are exactly 10^6 paths where the bug jumps on the spot, and slightly fewer than 4*10^6 paths where it hops to a neighboring cell.
989998989

{0,1,3,4,5,6,7,8,9,10}

10

Returns: 167959445
1000000

{0,1,3,4,5,6,7,8,9,10,2}

10

Returns: 723944135
47

{3}

6

Returns: 195354165
61641679

{2, 1, 6, 7, 4, 8}

10

Returns: 125569172
1

{1}

7

Returns: 0
137

{5, 2, 8, 9, 4, 6, 1, 0, 3}

2

Returns: 406136009
30758014

{0, 1, 4, 9, 6, 5}

9

Returns: 358084579
369

{7, 3, 4, 9, 10, 2}

9

Returns: 325545646
49357

{10, 3}

9

Returns: 171731479
521736534

{5, 7, 4, 2, 0, 10, 8, 6, 1}

10

Returns: 587539451
19

{3, 0, 8, 2, 9, 7}

2

Returns: 2251537
124989

{6, 4, 0, 1, 10, 8, 7, 2, 5, 3}

9

Returns: 514236015
202679

{5, 8, 4, 7, 6, 2, 9, 0, 1, 10}

9

Returns: 355359804
69508376

{0, 9, 10, 5, 8, 2, 1, 7, 3, 4}

6

Returns: 860979127
180692

{5, 6, 10, 4, 9, 7, 0, 1, 8, 2}

10

Returns: 214947459
225958

{7, 4, 8, 3, 0}

9

Returns: 102508171
163423242

{6, 4, 3, 8, 1}

1

Returns: 452648779
148920230

{6, 7, 5, 1, 0, 8, 3, 2, 9, 4}

2

Returns: 805774404
195

{4, 5, 3, 9, 6, 2, 7, 1, 0, 10}

5

Returns: 891192922
22148

{9, 3, 8, 1, 7, 0, 4, 10, 6}

9

Returns: 757755438
118028

{9, 0, 4, 2, 3, 10, 1}

1

Returns: 781601893
181148554

{10, 6}

10

Returns: 953049127
1238

{4, 9, 2, 10, 7, 3, 1, 6}

4

Returns: 958112514
693

{5, 10, 7, 1, 8, 0, 4, 6}

7

Returns: 413951674
1833120

{9, 6, 7, 0}

1

Returns: 55877288
4

{3, 8, 10, 6, 2, 1}

2

Returns: 2152
31170965

{7, 4, 0, 1, 9, 2, 8, 10, 6, 5}

8

Returns: 751397195
20939061

{3, 7, 10, 6, 2, 8, 5, 9, 4}

1

Returns: 696008510
783229648

{0, 6, 5, 10, 8, 2}

3

Returns: 385554823
22

{10, 6, 5, 9, 2, 8, 7, 1, 4, 3, 0}

7

Returns: 193227721
30779660

{5, 3, 4, 10, 8, 1, 9, 6, 2, 0}

5

Returns: 25794716
1

{3, 0, 1, 6, 7, 8, 10, 9, 5}

9

Returns: 1
561

{4, 1, 3, 5, 8, 9, 6, 2, 7, 0}

9

Returns: 683430013
75

{10, 0, 9, 8}

4

Returns: 301465902
5541

{1, 7, 4, 10, 8, 5, 3, 0, 6, 9, 2}

4

Returns: 490032282
362486

{0}

2

Returns: 396099279
84324595

{10, 8, 6, 3, 1, 7, 0, 9, 5}

1

Returns: 497588228
10

{2}

9

Returns: 823328595
785150168

{10, 6, 7, 9, 4}

1

Returns: 659814249
26516

{4, 9, 7}

6

Returns: 471620927
3

{9, 6, 2, 4, 5, 7, 0, 3}

2

Returns: 365
6907847

{0, 5, 2, 8, 1, 10, 9, 6}

2

Returns: 434745980
27555

{6, 4, 1, 7, 5}

2

Returns: 354347904
360743672

{7, 2, 4, 5, 1, 9, 6, 8, 3}

7

Returns: 77871770
14

{10, 4, 3, 2, 7, 9, 8, 0, 1, 6}

5

Returns: 561059813
724

{10, 8, 9, 2, 1, 6, 7, 4, 3, 5, 0}

0

Returns: 524176
1362944

{3, 8, 10, 7, 9}

1

Returns: 565565241
2534

{1, 6, 3, 9, 5, 4, 0}

1

Returns: 723888536
1655

{3, 5, 7, 8, 4, 1}

10

Returns: 913329046
12268

{4, 0, 10, 1, 3, 2, 9}

9

Returns: 212685491
4166753

{4, 8, 10, 0, 3, 5, 1, 9, 7, 6, 2}

1

Returns: 110768643
31131

{6}

4

Returns: 929262654
207

{3, 0, 1, 2, 7, 4, 5, 9, 10, 8}

0

Returns: 42849
468

{5, 7, 0, 9}

8

Returns: 144515319
22517

{7, 1, 0, 10}

3

Returns: 32542676
3993632

{6}

8

Returns: 147602826
24752

{1, 10, 6, 9, 8, 0, 3, 4, 7}

5

Returns: 941107058
51019235

{5, 1, 9, 4, 2, 0, 7, 10, 3}

8

Returns: 49458490
5

{5, 4, 2}

0

Returns: 25
21349294

{5, 6, 0, 1, 9, 8, 2, 10, 7}

3

Returns: 470557079
1

{5, 6, 0, 10, 4, 9, 1, 3, 8}

10

Returns: 1
104

{9, 6, 2, 8}

9

Returns: 559397799
43

{10, 0, 7, 4, 9, 1, 2}

8

Returns: 730380209
943391

{4, 0, 6, 7, 9}

9

Returns: 974178990
10494

{4, 2, 6, 5, 1, 8, 9, 10, 3}

1

Returns: 129712585
2309494

{8, 3, 2, 10, 0, 7, 4}

3

Returns: 798874286
399

{10, 5, 9}

9

Returns: 610318793
359

{7, 0, 5, 4, 1, 3}

8

Returns: 209667069
28

{7, 5, 10, 2, 9}

10

Returns: 981269683
2

{3, 1, 4, 2}

10

Returns: 236196
334358

{2, 7, 10, 1, 4, 3, 9, 0, 6}

3

Returns: 529544665
3

{5, 7, 3, 4, 8, 6, 10, 9, 1, 2, 0}

7

Returns: 43046721
64

{10, 0, 6, 1}

3

Returns: 991156192
58977

{5, 10, 6, 3, 0, 8, 2, 4}

8

Returns: 752460225
334

{10, 6, 0, 5, 2, 4, 8}

0

Returns: 111556
162

{0, 4, 8, 9}

3

Returns: 463968250
21

{5, 2}

6

Returns: 242243415
22

{1, 8, 10, 3, 7, 5, 2, 6, 9, 0, 4}

0

Returns: 484
84

{0, 6}

10

Returns: 652814193
108089

{8, 7, 2, 6, 0, 3}

8

Returns: 186318868
1

{2, 8, 6, 7}

8

Returns: 0
2

{9, 8, 7, 3, 6, 5, 4, 2}

3

Returns: 4
491

{1, 10, 8, 0, 5, 2, 3, 9}

7

Returns: 355758618
34915

{5, 1, 4}

6

Returns: 575999269
24

{5, 2, 8, 1, 6, 9, 4, 3, 0, 7, 10}

5

Returns: 590464613
14855

{8, 10, 5}

9

Returns: 66684293
9

{7, 6, 0, 10, 2, 3}

3

Returns: 4633617
119012766

{2}

1

Returns: 70375661
10

{7, 8}

5

Returns: 357937136
3

{9, 2, 1, 0, 6, 4, 5, 10, 7, 8, 3}

0

Returns: 9
7048448

{0, 4, 8}

0

Returns: 618860944
194

{2, 8, 4, 10, 5, 9}

6

Returns: 343319052
471703346

{9, 2, 7, 10, 0, 4, 5, 6}

9

Returns: 416192730
3

{9, 3, 10, 7, 1, 4}

0

Returns: 9
624950

{4, 1, 10, 3}

0

Returns: 562499770
15

{10, 3, 5, 9, 2, 0, 6, 8, 1, 4}

6

Returns: 177685356
1585

{2, 1, 6, 4, 3, 0, 10, 9, 8, 5}

2

Returns: 877391721
259

{2, 3, 6, 1, 5, 10, 4}

8

Returns: 731730407
107

{0, 2, 4, 10, 8, 9, 3, 6, 5}

6

Returns: 865726596
4

{0, 10, 4, 2, 3, 5}

8

Returns: 258411975
2089861

{1, 8, 3, 2, 10, 0, 9}

3

Returns: 452434135
1422

{0}

6

Returns: 2022084
234103

{2}

5

Returns: 806114399
199

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

10

Returns: 844080626
1000000000

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

10

Returns: 121827731
1000000

{1, 2, 3, 4, 5, 6, 7, 8 }

10

Returns: 114061553
1000000000

{1, 2, 3, 4, 5, 6, 7, 9, 10 }

10

Returns: 336376073
987123123

{1, 3, 4, 5, 6, 7, 8, 9, 10 }

10

Returns: 765279777

Statistics

Problem Statement for "ShortBugPaths"

Problem Statement

Definition

Notes

Constraints

Examples