Bags with Balls (Codeforces 1716F)
Tags: Math, combinatorics

There are $$$n$$$ bags, each bag contains $$$m$$$ balls with numbers from $$$1$$$ to $$$m$$$. For every $$$i \in [1, m]$$$, there is exactly one ball with number $$$i$$$ in each bag.You have to take exactly one ball from each bag (all bags are different, so, for example, taking the ball $$$1$$$ from the first bag and the ball $$$2$$$ from the second bag is not the same as taking the ball $$$2$$$ from the first bag and the ball $$$1$$$ from the second bag). After that, you calculate the number of balls with odd numbers among the ones you have taken. Let the number of these balls be $$$F$$$.Your task is to calculate the sum of $$$F^k$$$ over all possible ways to take $$$n$$$ balls, one from each bag.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.Each test case consists of one line containing three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n, m \le 998244352$$$; $$$1 \le k \le 2000$$$).

Output: For each test case, print one integer — the sum of $$$F^k$$$ over all possible ways to take $$$n$$$ balls, one from each bag. Since it can be huge, print it modulo $$$998244353$$$.


Sample Inputs:
5
2 3 8
1 1 1
1 5 10
3 7 2000
1337666 42424242 2000

Sample Outputs:
1028
1
3
729229716
652219904

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]
mod = 998244353
m = 2010
S = [[0] * m for i in range(m)]
for n in range(1, m):
    for k in range(1, n + 1):
        if k == 1 or n == k:
            S[n][k] = 1
        else:
            S[n][k] = S[n - 1][k - 1] + k * S[n - 1][k]
            S[n][k] %= mod

def fpow(x, k):
    res = 1
    if k < 0:
        return 0
    while k:
        if k & 1:
            res = res * x % mod
        x = x * x % mod
        k >>= 1
    return res

def solve():
    (N, M, K) = map(int, input().split())
    ans = 0
    res = fpow(M, N)
    Minv = fpow(M, mod - 2)
    for i in range(1, K + 1):
        res *= (N - i + 1) * ((M + 1) // 2) % mod * Minv % mod
        res %= mod
        ans += res * S[K][i] % mod
        ans %= mod
    print(ans)
for _ in range(int(input())):
    solve()

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

def f(u, v):
    return u * l + v
t = int(input())
mod = 998244353
l = 2005
dp = [0] * (l * l)
dp[0] = 1
for i in range(1, l):
    for j in range(i + 1):
        dp[f(i, j)] = (dp[f(i - 1, j - 1)] + j * dp[f(i - 1, j)]) % mod
ans = []
for _ in range(t):
    (n, m, k) = map(int, input().split())
    ans0 = 0
    (x, y, z) = (1, 1, pow(m, n, mod))
    m2 = (m + 1) // 2
    inv = pow(m, mod - 2, mod)
    for i in range(k + 1):
        ans0 += dp[f(k, i)] * x % mod * y % mod * z % mod
        x = (n - i) * x % mod
        y = m2 * y % mod
        z = inv * z % mod
    ans0 %= mod
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
MOD = 998244353

def modmul(x, y, c=0):
    return (x * y + c) % MOD
mod_mul = modmul

def inv(x):
    return pow(x, MOD - 2, MOD)
MAX = 10 ** 5
fact = [1]
for i in range(1, MAX):
    fact.append(modmul(i, fact[i - 1]))
invfact = [1] * MAX
invfact[MAX - 1] = inv(fact[MAX - 1])
for i in range(MAX - 2, -1, -1):
    invfact[i] = modmul(i + 1, invfact[i + 1])

def comb(x, y):
    return modmul(fact[x], modmul(invfact[y], invfact[x - y]))

def invcomb(x, y):
    return modmul(invfact[x], modmul(fact[y], fact[x - y]))

def invs(x):
    return modmul(fact[x - 1], invfact[x])
ster = [[1]]
for i in range(2010):
    curr = ster[-1]
    nex = [1]
    for j in range(i):
        nex.append(modmul(curr[j + 1], j + 2, curr[j]))
    nex.append(curr[-1])
    ster.append(nex)
t = int(input())
for _ in range(t):
    (m, n, k) = map(int, input().split())
    out = 0
    a = (n + 1) // 2
    invn = inv(n)
    deriv = [pow(n, m, MOD)]
    for i in range(k + 5):
        deriv.append(modmul(deriv[-1], modmul(invn, modmul(m - i, a))))
    cs = ster[k - 1]
    for i in range(1, k + 1):
        out += cs[i - 1] * deriv[i]
        out %= MOD
    print(out)