Farm Game (Codeforces 1942E)
Tags: Others, games

Lunatic Princess - Touhou⠀Farmer Nhoj has brought his cows over to Farmer John's farm to play a game! FJ's farm can be modeled by a number line with walls at points $$$0$$$ and $$$l + 1$$$. On the farm, there are $$$2n$$$ cows, with $$$n$$$ of the cows belonging to FJ and the other $$$n$$$ belonging to FN. They place each of their cows at a distinct point, and no two FJ's cows nor FN's cows are adjacent. Two cows are adjacent if there are no other cows between them. Formally, if $$$a_1, a_2, \ldots, a_n$$$ represents the positions of FJ's cows and $$$b_1, b_2, \ldots, b_n$$$ represents the positions of FN's cows, then either $$$0 < a_1 < b_1 < a_2 < b_2 < \ldots < a_n < b_n < l + 1$$$ or $$$0 < b_1 < a_1 < b_2 < a_2 < \ldots < b_n < a_n < l + 1$$$.In one move, a farmer chooses a number $$$k$$$ $$$(1 \leq k \leq n)$$$ and a direction (left or right). Then, that farmer chooses $$$k$$$ of his cows and moves them one position towards the chosen direction. A farmer cannot move any of his cows onto the walls or onto another farmer's cow. If a farmer cannot move any cows, then that farmer loses. FJ starts the game, making the first turn.Given $$$l$$$ and $$$n$$$, find the number of possible game configurations for Farmer John to win if both farmers play optimally. It may be the case that the game will continue indefinitely, in which no farmer wins. A configuration is different from another if there is any $$$i$$$ such that $$$a_i$$$ or $$$b_i$$$ is different. Output the answer modulo $$$998\,244\,353$$$.

Input: The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.Each test case contains two integers $$$l$$$ and $$$n$$$ ($$$2 \leq l \leq 10^6, 1 \leq n \leq \lfloor \frac{l}{2} \rfloor$$$) — the length of the number line and the number of cows each farmer will place.It is guaranteed the sum of $$$l$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case output an integer: the number of game configurations where Farmer John wins if both farmers play optimally, modulo $$$998\,244\,353$$$.

Note: Let J denote FJ's cow, N denote FN's cow, and _ denote an empty space.For the first test case, the two possible configurations are JN or NJ. In both cases, since FJ makes the first turn and cannot make any moves, he cannot win.For the second case there are two possible configurations for FJ to win: N_J and J_N.

Sample Inputs:
3
2 1
3 1
420 69

Sample Outputs:
0
2
870279412

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def comb(n, r):
    return fact[n] * inv[r] % mod * inv[n - r] % mod if n >= r >= 0 else 0
t = int(input())
ans = []
mod = 998244353
l = 2 * pow(10, 6) + 5
fact = [1] * (l + 1)
for i in range(1, l + 1):
    fact[i] = i * fact[i - 1] % mod
inv = [1] * (l + 1)
inv[l] = pow(fact[l], mod - 2, mod)
for i in range(l - 1, -1, -1):
    inv[i] = (i + 1) * inv[i + 1] % mod
for _ in range(t):
    (l, n) = map(int, input().split())
    ans0 = comb(l, 2 * n)
    m = l - n
    for i in range(l):
        ans0 -= comb(m, n) * comb(n + i - 1, i) % mod
        m -= 2
    ans0 = 2 * ans0 % mod
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys
input = sys.stdin.readline
MOD = 998244353
N = 10 ** 6 + 5
fact = [1] * N
inv = [1] * N
fact_inv = [1] * N
for i in range(2, N):
    fact[i] = i * fact[i - 1] % MOD
    inv[i] = -(MOD // i) * inv[MOD % i] % MOD
    fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD

def cmb(n, k, m):
    if k < 0 or k > n:
        return 0
    return fact[n] * fact_inv[k] % m * fact_inv[n - k] % m

def solve():
    (l, n) = map(int, input().split())
    ans = cmb(l, 2 * n, MOD)
    for x in range(0, (l - 2 * n) // 2 + 1):
        rest = l - 2 * n - 2 * x
        ans -= cmb(x + n - 1, x, MOD) * cmb(rest + n, rest, MOD) % MOD
        ans %= MOD
    ans *= 2
    ans %= MOD
    return ans
T = int(input())
out = [solve() for _ in range(T)]
print('\n'.join(map(str, out)))

Solution (Python):
import heapq
import sys
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())
MOD = 998244353
MAXN = 2 * 10 ** 6 + 5
fac = [1] * MAXN
inv_fac = [1] * MAXN
for i in range(1, MAXN):
    fac[i] = fac[i - 1] * i % MOD
inv_fac[MAXN - 1] = pow(fac[MAXN - 1], -1, MOD)
for i in range(MAXN - 2, -1, -1):
    inv_fac[i] = inv_fac[i + 1] * (i + 1) % MOD

def combination(n, k):
    return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD

def permutation(n, k):
    return fac[n] * inv_fac[n - k] % MOD
t = inp()
for _ in range(t):
    (l, n) = inlt()
    ans = 2 * combination(l, 2 * n) % MOD
    for s in range(0, l - 2 * n + 1, 2):
        ans = (ans - combination(s // 2 + n - 1, n - 1) % MOD * 2 * combination(l - s - n, n) % MOD) % MOD
    print(ans)