Camp room assignment
Source: aizu

Camp room assignment
Problem Statement

In the JAG country, there are a total of $m$ universities, and we plan to invite $2n$ students to a training camp. Each student is affiliated with one of the $m$ universities. During the training camp, the students will be accommodated in $n$ twin rooms, meaning that each room will be assigned to exactly two students.

To promote diverse interactions among the students, our goal is to achieve a "good room assignment". A room assignment is considered good if and only if the students sharing the same room come from different universities.

Here, we are wondering how often a good room assignment is feasible. There are $m^{2n}$ possible sequences of universities to which each student belongs, and please find for how many of them there is a good room assignment.

Actually, we don't yet know how many rooms we can provide. Therefore, for each of $n = 1, 2, ..., m$, please find for how many of the sequences of universities there is a good room assignment.

Since the answer may be huge, print the answers modulo $998,244,353$.

Input

The input is a single line containing an integer $m$ between $1$ and $200,000$, inclusive.

Output

Output $m$ lines. In the $i$-th line, you should output the answer for $n = i$.

Sample Input 1
3

Sample Output 1
6
54
510

Sample Input 2
5

Sample Output 2Sample Output 2
20
540
14300
370300
9454620

Sample Input 3
20

Sample Output 3
380
158460
63889400
636003875
443532759
163564701
433390846
160318339
979712600
445802634
862134704
374397421
898644169
181404073
884138261
856576908
608198482
349239556
724235122
812173715


C++ solution:
// AOJ #3614
// Camp room assignment 2025.2.1

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 998244353;

#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)

int Cin() {   // 非負整数の入力
    int n = 0; int c = gc();
    do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
    return n;
}

void Cout(int n) { // 非負整数の表示（出力）
    char b[30];
    if (!n) pc('0');
    else {
        //      if (n < 0) pc('-'), n = -n;
        int i = 0; while (n) b[i++] = n % 10 + '0', n /= 10;
        while (i--) pc(b[i]);
    }
    pc('\n');
}

ll modexp(ll base, ll exp, ll mod=MOD) {
    ll res = 1;
    base %= mod;
    while(exp > 0) {
        if(exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}
 
void precomputeFactorials(int n_max, vector<ll>& fact, vector<ll>& invfact) {
    fact.resize(n_max+1);
    invfact.resize(n_max+1);
    fact[0] = 1;
    for (int i = 1; i <= n_max; i++)
        fact[i] = fact[i-1] * i % MOD;
    invfact[n_max] = modexp(fact[n_max], MOD-2, MOD);
    for (int i = n_max; i > 0; i--)
        invfact[i-1] = invfact[i] * i % MOD;
}
 
ll binom(int n, int k, const vector<ll>& fact, const vector<ll>& invfact) {
    if(k < 0 || k > n) return 0;
    return fact[n] * ((invfact[k] * invfact[n-k]) % MOD) % MOD;
}
 
// Main function
int main(){
    int m = Cin();
    int M = 2 * m;
    vector<ll> fact, invfact;
    precomputeFactorials(M, fact, invfact);
 
    ll x = ((ll)m - 1) % MOD;
    if(x < 0) x += MOD;
 
    int maxPow = m + 1;
    vector<ll> powX(maxPow+1, 0);
    powX[0] = 1;
    for (int i = 1; i <= maxPow; i++)
        powX[i] = (powX[i-1] * x) % MOD;
 
    ll mm2 = ((ll)m * m) % MOD;
    vector<ll> powM2(m+1, 0);
    powM2[0] = 1;
    for (int i = 1; i <= m; i++)
        powM2[i] = (powM2[i-1] * mm2) % MOD;
 
    ll onePlusX = (1 + x) % MOD;
    ll c = (onePlusX * onePlusX) % MOD;
 
    vector<ll> A(m+1, 0);
    A[1] = 1;
    for (int n = 1; n < m; n++){
        ll term1 = binom(2*n, n, fact, invfact);
        ll term2 = binom(2*n, n-1, fact, invfact);
        ll add1 = (term1 * powX[n]) % MOD;
        ll add2 = (term2 * powX[n+1]) % MOD;
        ll nextA = ( c * A[n] ) % MOD;
        nextA = ( nextA + add1 ) % MOD;
        nextA = ( nextA + MOD - add2 ) % MOD;
        A[n+1] = nextA;
    }
    for (int n = 1; n <= m; n++){
        ll ans = ( powM2[n] + MOD - ( (ll)m * A[n] ) % MOD ) % MOD;
        Cout(ans);
    }
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
)

const MOD = 998244353

func main() {
	// Initialize fast I/O
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	// Read input
	var m int
	fmt.Fscan(in, &m)

	// Handle edge case
	if m == 0 {
		return
	}

	// Precompute factorials and inverse factorials
	maxN := 2 * m
	fact := make([]int64, maxN+1)
	invFact := make([]int64, maxN+1)
	fact[0] = 1
	for i := 1; i <= maxN; i++ {
		fact[i] = (fact[i-1] * int64(i)) % MOD
	}
	invFact[maxN] = modExp(fact[maxN], MOD-2)
	for i := maxN; i > 0; i-- {
		invFact[i-1] = (invFact[i] * int64(i)) % MOD
	}

	// Precompute powers
	x := (int64(m) - 1) % MOD
	if x < 0 {
		x += MOD
	}

	powX := make([]int64, m+2)
	powX[0] = 1
	for i := 1; i <= m+1; i++ {
		powX[i] = (powX[i-1] * x) % MOD
	}

	mm2 := (int64(m) * int64(m)) % MOD
	powM2 := make([]int64, m+1)
	powM2[0] = 1
	for i := 1; i <= m; i++ {
		powM2[i] = (powM2[i-1] * mm2) % MOD
	}

	// Compute A[n] values
	A := make([]int64, m+1)
	A[1] = 1
	onePlusX := (1 + x) % MOD
	c := (onePlusX * onePlusX) % MOD

	for n := 1; n < m; n++ {
		term1 := binom(2*n, n, fact, invFact)
		term2 := binom(2*n, n-1, fact, invFact)
		add1 := (term1 * powX[n]) % MOD
		add2 := (term2 * powX[n+1]) % MOD
		nextA := (c * A[n]) % MOD
		nextA = (nextA + add1) % MOD
		nextA = (nextA + MOD - add2) % MOD
		A[n+1] = nextA
	}

	// Generate and print results
	results := make([]int64, m)
	for n := 1; n <= m; n++ {
		results[n-1] = (powM2[n] + MOD - (int64(m)*A[n])%MOD) % MOD
	}

	for _, res := range results {
		fmt.Fprintln(out, res)
	}
}

func modExp(base, exp int64) int64 {
	var res int64 = 1
	base %= MOD
	for exp > 0 {
		if exp&1 == 1 {
			res = (res * base) % MOD
		}
		base = (base * base) % MOD
		exp >>= 1
	}
	return res
}

func binom(n, k int, fact, invFact []int64) int64 {
	if k < 0 || k > n {
		return 0
	}
	return fact[n] * ((invFact[k] * invFact[n-k]) % MOD) % MOD
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    private static final long MOD = 998244353;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);

        int m = Integer.parseInt(br.readLine());
        if (m < 1 || m > 200000) {
            pw.close();
            return;
        }

        // Precompute factorials and inverse factorials
        int maxFact = 2 * m;
        long[] fact = new long[maxFact + 1];
        long[] invFact = new long[maxFact + 1];
        
        fact[0] = 1;
        for (int i = 1; i <= maxFact; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
        
        invFact[maxFact] = modInverse(fact[maxFact], MOD);
        for (int i = maxFact; i > 0; i--) {
            invFact[i - 1] = invFact[i] * i % MOD;
        }

        long x = (m - 1) % MOD;
        if (x < 0) x += MOD;

        // Precompute powers of x
        long[] powX = new long[m + 2];
        powX[0] = 1;
        for (int i = 1; i <= m + 1; i++) {
            powX[i] = powX[i - 1] * x % MOD;
        }

        // Precompute powers of m^2
        long mSquared = ((long)m * m) % MOD;
        long[] powMSquared = new long[m + 1];
        powMSquared[0] = 1;
        for (int i = 1; i <= m; i++) {
            powMSquared[i] = powMSquared[i - 1] * mSquared % MOD;
        }

        long onePlusX = (1 + x) % MOD;
        long c = (onePlusX * onePlusX) % MOD;

        long[] A = new long[m + 1];
        A[1] = 1;

        for (int n = 1; n < m; n++) {
            long term1 = comb(2 * n, n, fact, invFact);
            long term2 = comb(2 * n, n - 1, fact, invFact);
            long add1 = term1 * powX[n] % MOD;
            long add2 = term2 * powX[n + 1] % MOD;
            long nextA = c * A[n] % MOD;
            nextA = (nextA + add1) % MOD;
            nextA = (nextA - add2 + MOD) % MOD;
            A[n + 1] = nextA;
        }

        for (int n = 1; n <= m; n++) {
            long ans = (powMSquared[n] - (m * A[n]) % MOD + MOD) % MOD;
            pw.println(ans);
        }

        pw.close();
    }

    private static long modInverse(long a, long mod) {
        return modPow(a, mod - 2, mod);
    }

    private static long modPow(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = result * base % mod;
            }
            base = base * base % mod;
            exp >>= 1;
        }
        return result;
    }

    private static long comb(int n, int k, long[] fact, long[] invFact) {
        if (k < 0 || k > n) return 0;
        return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
    }
}

JavaScript solution:
const MOD = 998244353n;

function modExp(base, exp, mod) {
    let result = 1n;
    base = BigInt(base) % mod;
    while (exp > 0n) {
        if (exp % 2n === 1n) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp = exp >> 1n;
    }
    return result;
}

function precomputeFactorials(max, mod) {
    const fact = new Array(max + 1).fill(0n);
    const invFact = new Array(max + 1).fill(0n);
    fact[0] = 1n;
    for (let i = 1; i <= max; i++) {
        fact[i] = (fact[i - 1] * BigInt(i)) % mod;
    }
    invFact[max] = modExp(fact[max], mod - 2n, mod);
    for (let i = max; i > 0; i--) {
        invFact[i - 1] = (invFact[i] * BigInt(i)) % mod;
    }
    return { fact, invFact };
}

function binom(n, k, fact, invFact, mod) {
    if (k < 0 || k > n) return 0n;
    return (fact[n] * invFact[k] % mod) * invFact[n - k] % mod;
}

function main() {
    const readline = require('readline');
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });

    rl.on('line', (input) => {
        const m = parseInt(input);
        const M = 2 * m;
        const { fact, invFact } = precomputeFactorials(M, MOD);

        const x = (BigInt(m) - 1n) % MOD;
        const maxPow = m + 1;
        const powX = new Array(maxPow + 1).fill(0n);
        powX[0] = 1n;
        for (let i = 1; i <= maxPow; i++) {
            powX[i] = (powX[i - 1] * x) % MOD;
        }

        const mm2 = (BigInt(m) * BigInt(m)) % MOD;
        const powM2 = new Array(m + 1).fill(0n);
        powM2[0] = 1n;
        for (let i = 1; i <= m; i++) {
            powM2[i] = (powM2[i - 1] * mm2) % MOD;
        }

        const onePlusX = (1n + x) % MOD;
        const c = (onePlusX * onePlusX) % MOD;

        const A = new Array(m + 1).fill(0n);
        A[1] = 1n;
        for (let n = 1; n < m; n++) {
            const term1 = binom(2 * n, n, fact, invFact, MOD);
            const term2 = binom(2 * n, n - 1, fact, invFact, MOD);
            const add1 = (term1 * powX[n]) % MOD;
            const add2 = (term2 * powX[n + 1]) % MOD;
            let nextA = (c * A[n]) % MOD;
            nextA = (nextA + add1) % MOD;
            nextA = (nextA + MOD - add2) % MOD;
            A[n + 1] = nextA;
        }

        for (let n = 1; n <= m; n++) {
            const ans = (powM2[n] + MOD - (BigInt(m) * A[n]) % MOD) % MOD;
            console.log(ans.toString());
        }

        rl.close();
    });
}

main();

Python solution:
import sys
MOD = 998244353

def main():
    m = int(sys.stdin.readline())
    M = 2 * m
    
    # Precompute factorials and inverse factorials modulo MOD up to M
    fact = [1] * (M + 1)
    inv_fact = [1] * (M + 1)
    for i in range(1, M + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact[M] = pow(fact[M], MOD-2, MOD)
    for i in range(M-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    def comb(n, k):
        if k < 0 or k > n:
            return 0
        return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD
    
    x = (m - 1) % MOD
    
    max_pow = m + 1
    pow_x = [1] * (max_pow + 1)
    for i in range(1, max_pow + 1):
        pow_x[i] = pow_x[i-1] * x % MOD
    
    mm2 = (m * m) % MOD
    pow_m2 = [1] * (m + 1)
    for i in range(1, m + 1):
        pow_m2[i] = pow_m2[i-1] * mm2 % MOD
    
    one_plus_x = (1 + x) % MOD
    c = (one_plus_x * one_plus_x) % MOD
    
    A = [0] * (m + 1)
    A[1] = 1
    for n in range(1, m):
        term1 = comb(2 * n, n)
        term2 = comb(2 * n, n - 1)
        add1 = term1 * pow_x[n] % MOD
        add2 = term2 * pow_x[n + 1] % MOD
        next_A = c * A[n] % MOD
        next_A = (next_A + add1) % MOD
        next_A = (next_A - add2) % MOD
        A[n + 1] = next_A
    
    for n in range(1, m + 1):
        ans = (pow_m2[n] - m * A[n] % MOD) % MOD
        print(ans)

if __name__ == '__main__':
    main()

Ruby solution:
MOD = 998244353

def modexp(base, exp, mod = MOD)
  res = 1
  base %= mod
  while exp > 0
    if exp & 1 == 1
      res = (res * base) % mod
    end
    base = (base * base) % mod
    exp >>= 1
  end
  res
end

def precompute_factorials(n_max)
  fact = Array.new(n_max + 1, 1)
  invfact = Array.new(n_max + 1, 1)
  (1..n_max).each do |i|
    fact[i] = fact[i-1] * i % MOD
  end
  invfact[n_max] = modexp(fact[n_max], MOD - 2)
  (n_max - 1).downto(0) do |i|
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
  end
  [fact, invfact]
end

def binom(n, k, fact, invfact)
  return 0 if k < 0 || k > n
  fact[n] * invfact[k] % MOD * invfact[n - k] % MOD
end

m = gets.to_i
max_n = m
M = 2 * max_n

fact, invfact = precompute_factorials(M)

x = (m - 1) % MOD

max_pow = m + 1
pow_x = Array.new(max_pow + 1, 1)
(1..max_pow).each do |i|
  pow_x[i] = pow_x[i-1] * x % MOD
end

mm2 = m * m % MOD
pow_m2 = Array.new(m + 1, 1)
(1..m).each do |i|
  pow_m2[i] = pow_m2[i-1] * mm2 % MOD
end

one_plus_x = (1 + x) % MOD
c = one_plus_x * one_plus_x % MOD

a = Array.new(m + 1, 0)
a[1] = 1

(1...m).each do |n|
  term1 = binom(2 * n, n, fact, invfact)
  term2 = binom(2 * n, n - 1, fact, invfact)
  add1 = term1 * pow_x[n] % MOD
  add2 = term2 * pow_x[n + 1] % MOD
  next_a = c * a[n] % MOD
  next_a = (next_a + add1) % MOD
  next_a = (next_a - add2) % MOD
  next_a += MOD if next_a < 0
  next_a %= MOD
  a[n + 1] = next_a
end

(1..m).each do |n|
  ans = (pow_m2[n] - m * a[n] % MOD) % MOD
  ans += MOD if ans < 0
  puts ans
end