I helped run a local high school contest earlier this year. For the last problem of the practice contest, I wanted to write a meme problem that was ridiculously "hard" (really just a knowledge check that's not appropriate for the participants, but would stimulate some conversation among them before the actual contest). I did not know it at the time, but this is actually similar to (albeit a bit easier than) a previous problem: [problem:1103E]↵
↵
If anyone wants to try it, here is what it was:↵
↵
Finally, Fouring Time!↵
------------------↵
↵
You've just received a phone call from Dr. Phoughrierre! The mad doctor tells you that he's currently on the surface of↵
a rather high-dimensional torus. He said something unintelligible along the lines of ↵
''they can't catch me here on $(\mathbb{R}/4\mathbb{Z})^n$.'' ↵
You're not sure what that means, but you know that you were supposed to be practicing dancing with him right about now. ↵
↵
Luckily, you're in space that has the same number of dimensions $n$ as Dr. Phoughrierre, so you can just practice your dances↵
remotely with him! However, while you can move any distance in any direction at any time, Dr. Phoughrierre loops back around↵
whenever he steps 4 units along any of the coordinate axes. Since you don't want him to get lost, right now you can only↵
practice dances that take him back to where he started. A ''dance move'' is a sequence of $n$ integers between 0 and 3,↵
corresponding to the amount of distance moved along each of the $n$ coordinate axes. A ''dance'' is a sequence of $k$↵
dance moves corresponding to the steps in the routine. Two dances are considered different if any of their moves is different.↵
↵
### Input↵
The first line will consist of three space-separated integers: the number of dimensions $n$ ($1 \leq n \leq 10$),↵
the number of known dance moves $d$ ($1 \leq d \leq 4^n$), and the number of moves in a dance $k$ ($1 \leq k \leq 10^{18}$). ↵
↵
The next $d$ lines contain one dance move each. A dance move is written as a sequence of $n$ digits from 0 through 3.↵
All known dance moves are guaranteed to be distinct. ↵
↵
### Output↵
Let $D$ be the number of dances of length $k$ that do not displace Dr. Phoughrierre. Since $D$ can be quite large, print↵
on one line the remainder when $D$ is divided by $999\,999\,937$. ↵
↵
### Samples↵
↵
#### Sample input 1↵
```↵
3 4 2↵
202↵
022↵
220↵
111↵
```↵
#### Sample output 1↵
```↵
3↵
```↵
#### Sample input 2↵
```↵
3 4 3↵
202↵
022↵
220↵
111↵
```↵
#### Sample output 2↵
```↵
6↵
```↵
#### Sample input 3↵
```↵
1 1 1↵
3↵
```↵
#### Sample output 3↵
```↵
0↵
```↵
#### Sample input 4↵
```↵
1 2 1000↵
2↵
0↵
```↵
#### Sample output 4↵
```↵
128930244↵
```↵
↵
It is not impossible that I did not copy the samples/formatting correctly into codeforces, so please let me know if there are any glaring errors.↵
↵
I will spare you folks the image of a trollface stick figure walking on a torus that was present in the actual PDF of the problem. ↵
↵
Also, I will have to write a quick solution guide for this soon anyway, so I will update this post when that is done.
↵
If anyone wants to try it, here is what it was:↵
↵
Finally, Fouring Time!↵
------------------↵
↵
You've just received a phone call from Dr. Phoughrierre! The mad doctor tells you that he's currently on the surface of↵
a rather high-dimensional torus. He said something unintelligible along the lines of ↵
''they can't catch me here on $(\mathbb{R}/4\mathbb{Z})^n$.'' ↵
You're not sure what that means, but you know that you were supposed to be practicing dancing with him right about now. ↵
↵
Luckily, you're in space that has the same number of dimensions $n$ as Dr. Phoughrierre, so you can just practice your dances↵
remotely with him! However, while you can move any distance in any direction at any time, Dr. Phoughrierre loops back around↵
whenever he steps 4 units along any of the coordinate axes. Since you don't want him to get lost, right now you can only↵
practice dances that take him back to where he started. A ''dance move'' is a sequence of $n$ integers between 0 and 3,↵
corresponding to the amount of distance moved along each of the $n$ coordinate axes. A ''dance'' is a sequence of $k$↵
dance moves corresponding to the steps in the routine. Two dances are considered different if any of their moves is different.↵
↵
### Input↵
The first line will consist of three space-separated integers: the number of dimensions $n$ ($1 \leq n \leq 10$),↵
the number of known dance moves $d$ ($1 \leq d \leq 4^n$), and the number of moves in a dance $k$ ($1 \leq k \leq 10^{18}$). ↵
↵
The next $d$ lines contain one dance move each. A dance move is written as a sequence of $n$ digits from 0 through 3.↵
All known dance moves are guaranteed to be distinct. ↵
↵
### Output↵
Let $D$ be the number of dances of length $k$ that do not displace Dr. Phoughrierre. Since $D$ can be quite large, print↵
on one line the remainder when $D$ is divided by $999\,999\,937$. ↵
↵
### Samples↵
↵
#### Sample input 1↵
```↵
3 4 2↵
202↵
022↵
220↵
111↵
```↵
#### Sample output 1↵
```↵
3↵
```↵
#### Sample input 2↵
```↵
3 4 3↵
202↵
022↵
220↵
111↵
```↵
#### Sample output 2↵
```↵
6↵
```↵
#### Sample input 3↵
```↵
1 1 1↵
3↵
```↵
#### Sample output 3↵
```↵
0↵
```↵
#### Sample input 4↵
```↵
1 2 1000↵
2↵
0↵
```↵
#### Sample output 4↵
```↵
128930244↵
```↵
↵
It is not impossible that I did not copy the samples/formatting correctly into codeforces, so please let me know if there are any glaring errors.↵
↵
I will spare you folks the image of a trollface stick figure walking on a torus that was present in the actual PDF of the problem. ↵
↵
Also, I will have to write a quick solution guide for this soon anyway, so I will update this post when that is done.
