RandomWalkOnGrid | Topcoder Archive

Problem Statement

The two-dimensional plane is divided into a grid of unit square cells. A token is placed onto the cell (x0, y0). You are playing a very simple game with the token. The game consists of exactly t moves.

Each move looks as follows: You choose one of the four cardinal directions (up, down, left, or right) uniformly at random, and you move the token one cell in the chosen direction.

You are given the ints x0, y0, and t. You are also given ints n and m that are used to compute your score at the end of the game. Your score is computed as (x^n * y^m), where (x, y) are the coordinates of the cell that contains the token at the end of the game.

Let E be the expected value of your score. Compute and return the following value: (E * 4^t) modulo 1,000,000,007.

Definition

Class:: RandomWalkOnGrid
Method:: getExpectation
Parameters:: int, int, int, int, int
Returns:: int
Method signature:: int getExpectation(int x0, int y0, int t, int n, int m)
(be sure your method is public)

Constraints

x0 and y0 will be between -1,000,000,000 and 1,000,000,000, inclusive.
t will be between 0 and 1,000,000,000, inclusive.
n and m will be between 1 and 100, inclusive.

Examples

```
2
```
```
2
```
```
1
```
```
1
```
```
1
```
```
Returns: 16
```
The token starts in the cell (2, 2). As t=1, you move it exactly once. Hence, with equal probability the token will end in one of the following four cells: (1, 2), (2, 1), (2, 3), and (3,2). The scores for these cells are 2, 2, 6, and 6. Thus, the expected score is E = (2+2+6+6)/4 = 4. This means that you should return the value (4 * 4^1) modulo 1,000,000,007 = 16.
```
2
```
```
2
```
```
2
```
```
1
```
```
1
```
```
Returns: 64
```
```
1
```
```
2
```
```
3
```
```
1
```
```
2
```
```
Returns: 352
```
```
123456
```
```
1654321
```
```
20
```
```
20
```
```
20
```
```
Returns: 860242008
```
```
0
```
```
0
```
```
1000000000
```
```
1
```
```
10
```
```
Returns: 0
```

-1000000000

-1000000000

1000000000

Returns: 623291020

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.