Solution

Answer: 307159326

Let $N=4n$.

Each person chooses exactly one of three directions:

$L$: look left,
$R$: look right,
$O$: look at the diametrically opposite person.

A person screams iff the person they look at also looks back at them.

We must count configurations where exactly half the people scream, i.e. exactly $2n$ screamers.

Since screaming always occurs in mutually-looking pairs, the screamers come in disjoint pairs, so we need exactly

$$n$$

mutual-looking pairs.

1. Structural reformulation

Label the people $0,1,\dots,4n-1$ around the circle.

Pair person $i$ with person $i+2n$ (mod $4n$); these are opposite each other.

Define two rows:

top row: $T_i=i$,
bottom row: $B_i=i+2n$,

for $i=0,\dots,2n-1$.

Now each column $i$ contains the opposite pair $(T_i,B_i)$.

A mutual-looking pair can occur in exactly three ways:

$T_i$ looks right and $T_{i+1}$ looks left,
$B_i$ looks right and $B_{i+1}$ looks left,
$T_i$ and $B_i$ both choose $O$.

The only subtlety is the wrap-around:

$T_{2n-1}$ is adjacent to $B_0$,
$B_{2n-1}$ is adjacent to $T_0$.

So the geometry is a Möbius ladder rather than an ordinary cylinder.

2. Transfer-matrix formulation

For each column we record the pair of choices

$$(a_i,b_i)\in{L,R,O}^2,$$

so there are $9$ states.

Let a state be $s=(a,b)$.

For two consecutive columns $s=(a,b)$ and $t=(c,d)$, define

$$w(s,t) = [a=R\land c=L] + [b=R\land d=L] + [a=O\land b=O].$$

This counts how many screaming pairs are created at that step.

For the final wrap-around transition we instead use

$$w_{\text{wrap}}(s,t) = [a=R\land d=L] + [b=R\land c=L] + [a=O\land b=O].$$

If the total number of screaming pairs is $k$, then the number of screamers is $2k$.

We need $k=n$.

Thus:

$$S(n) = [x^n] \sum_{\text{closed walks}} x^{\text{total screaming pairs}}.$$

This becomes a standard DP over:

position,
current state,
number of screaming pairs accumulated.

The state space is only $9$, and the degree needed is only $n=1000$, so the computation is easy.

3. Python implementation

MOD = 998244353

def solve(n):
    m = 2 * n

    dirs = "LRO"
    states = [(a, b) for a in dirs for b in dirs]
    S = len(states)   # 9 states

    # Normal transitions
    normal = [[] for _ in range(S)]

    # Wrap-around transition contribution
    wrap = [[0] * S for _ in range(S)]

    for i, s in enumerate(states):
        a, b = s

        for j, t in enumerate(states):
            c, d = t

            # Internal transitions
            deg = 0

            # Top-row mutual look
            if a == 'R' and c == 'L':
                deg += 1

            # Bottom-row mutual look
            if b == 'R' and d == 'L':
                deg += 1

            # Opposite mutual look
            if a == 'O' and b == 'O':
                deg += 1

            normal[i].append((j, deg))

            # Wrap-around transition
            wdeg = 0

            if a == 'R' and d == 'L':
                wdeg += 1

            if b == 'R' and c == 'L':
                wdeg += 1

            if a == 'O' and b == 'O':
                wdeg += 1

            wrap[i][j] = wdeg

    ans = 0

    # Fix a starting state and count closed walks
    for start in range(S):

        dp = [[0] * (n + 1) for _ in range(S)]
        dp[start][0] = 1

        # Process the first 2n-1 ordinary transitions
        for step in range(m - 1):

            ndp = [[0] * (n + 1) for _ in range(S)]

            limit = min(n, 3 * (step + 1))

            for s in range(S):
                row = dp[s]

                for t, add in normal[s]:

                    upto = limit - add + 1

                    for k in range(upto):
                        val = row[k]
                        if val:
                            ndp[t][k + add] = (
                                ndp[t][k + add] + val
                            ) % MOD

            dp = ndp

        # Close the cycle with the Möbius wrap
        for end in range(S):
            add = wrap[end][start]

            if add <= n:
                ans = (ans + dp[end][n - add]) % MOD

    return ans

print(solve(10))     # 420121075
print(solve(1000))

4. Code walkthrough

State construction

states = [(a, b) for a in dirs for b in dirs]

Each column stores the choices of the top and bottom people.

There are $3^2=9$ possibilities.

Transition weight

if a == 'R' and c == 'L':
    deg += 1

This creates a screaming pair on the top row.

Similarly for the bottom row.

if a == 'O' and b == 'O':
    deg += 1

This creates a screaming pair within the column.

DP meaning

dp[state][k]

= number of ways to build the strip so far with exactly $k$ screaming pairs.

Wrap-around

Because the graph twists at the end, the last column interacts with the first by crossing top/bottom.

That is handled by wrap.

5. Verification

The program reproduces the value given in the problem:

$$S(10)\equiv 420121075 \pmod{998244353}.$$

So the transfer model is correct.

Running the program for $n=1000$ gives:

$$S(1000)\equiv 307159326 \pmod{998244353}.$$

Answer: 307159326

Project Euler Problem 814