### nicksms's blog

By nicksms, history, 4 months ago,

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: 1103E - Radix sum

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.

• +48

By nicksms, history, 6 months ago,

This is gonna sound like a really dumb question, but how should I go about trying to trick myself into wanting to do implementation problems?

I've noticed that for pretty much everything else, how much I want to do something is directly tied to how much enjoyment I get from it after the fact -- solving problems in general, for instance, is something I look forward to since I feel good after doing it. And I do feel quite good after finishing implementation problems, but for some reason I cannot stop dreading them.

One thing I've found (this could be a cause or a symptom) is that debugging implementation problems genuinely takes the soul out of my body, whereas if my math is incorrect and I have to go back and fix it I don't feel bad at all.

Still I feel like I have the potential to enjoy them, as I feel more satisfied with getting them than with almost any other type of problem. Sometimes I even feel like I actually want to do them, but every time that happens I just think back on the few that I've done that have gone horribly wrong. How should I go about getting myself to enjoy them? Should I just try medium ones until I can tell myself that debugging really isn't as bad as I think it is? Should I practice on ICPC problems (even though for ICPC, I'm not usually the one coding)? Should I be looking at failing test cases or trying to debug without them (remember that I'm not exactly trying to get better at implementation so much as I am trying to enjoy it more)?

Please advise. I'll be working on Kattis: keys when I have free time today to try to get my foot in the door, since I remember seeing that the implementation for that was fairly frustrating.

Any practice problems (especially with a math flavor to them) would be appreciated.

• +46