ShortBugPaths | Topcoder Archive

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.
```
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.
```
47
```
```
{3}
```
```
6
```
```
Returns: 195354165
```

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.