Connection Status:
Competition Arena > SplittingFoxes

SplittingFoxes

SRM 544 · 2011-11-22 · by cgy4ever

SRM 544 · 2011-11-22 · by cgy4ever · Advanced Math
Class Name: SplittingFoxes
Return Type: int
Method Name: sum
Arg Types: (long long, int, int, int)
Problem Statement

Problem Statement

Fox Ciel learned a new skill of splitting! She can split into (S + L + R) foxes each time. Now she is practicing this skill on an infinite horizontal plane. At the beginning, Fox Ciel is the only fox on the plane. She stands at the point (0,0) and she is facing the point (1,0).


There will be n steps. In each step, each fox on the plane will split into exactly (S + L + R) foxes. Out of those foxes:
  • S will make a step forward, moving exactly one unit of distance in the direction they are facing.
  • L will stay in the same place and rotate 90 degrees to the left. (So for example if the original fox was facing the point (1,0), there will be L new foxes facing the point (0,1).)
  • R will stay in the same place and rotate 90 degrees to the right.
The score of a fox standing at the point (x,y) is x*y. Note that the score of a fox may be zero or even negative. The total score is the sum of the scores of all foxes on the plane. You are given the long n and the ints S, L, and R. Return the total score of all foxes after n steps, modulo 1,000,000,007 (10^9 + 7).

Notes

  • Note that you should return a number between 0 and 1,000,000,006, inclusive.
  • E.g., if the answer is -1, you should return 1,000,000,006 instead of -1.

Constraints

  • n will be between 1 and 10^18, inclusive.
  • S will be between 0 and 10^9, inclusive.
  • L will be between 0 and 10^9, inclusive.
  • R will be between 0 and 10^9, inclusive.
Examples
0)
58
2
0
0
Returns: 0

After step 1: there are 2^1 foxes at (1, 0), After step 2: there are 2^2 foxes at (2, 0), ... After step 58: there are 2^58 foxes at (58, 0). For each fox at (58, 0), her score is 58 * 0 = 0, so the answer is 0.

1)
3
1
1
0
Returns: 1

There will be 8 foxes at the end. The fox at (1,1) has score 1. Each of the other 7 foxes has score 0.

2)
5
1
3
2
Returns: 34
3)
5
1
2
3
Returns: 999999973

The answer is (-34) % 1,000,000,007.

4)
123456789
987654321
544
544
Returns: 0

By symmetry, if L = R, then the answer will be zero.

Submissions are judged against all 120 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SplittingFoxes with a public method int sum(long long n, int S, int L, int R) · 120 test cases · 2 s / 256 MB per case

Submitting as anonymous