G - Many LCS
Source: atcoder
Difficulty: 600

Problem Statement
You are given a lowercase English string
S
of length
N
and an integer
M
. For each
k=0,1,\ldots,N
, solve the following problem:
There are
26^M
lowercase English strings of length
M
. Among these, find the number, modulo
998244353
, of strings whose longest common subsequence with
S
has length exactly
k
.
Constraints
1\leq N\leq 10
1\leq M\leq 100
N
and
M
are integers.
S
is a lowercase English string of length
N
.
Input
The input is given from Standard Input in the following format:
N
M
S
Output
Let
\mathrm{ans}_i
be the answer for
k=i
. Print the answers in the following format:
\mathrm{ans}_0
\mathrm{ans}_1
\ldots
\mathrm{ans}_N
Sample Input 1
2 2
ab
Sample Output 1
576 99 1
The answers for
k=0,1,2
are as follows:
For
k=0
: Among length
2
lowercase English strings, those with a longest common subsequence of length
0
with
ab
include strings such as
cd
,
re
,
zz
, totaling
576
.
For
k=1
: Among length
2
lowercase English strings, those with a longest common subsequence of length
1
with
ab
include strings such as
ac
,
wa
,
ba
, totaling
99
.
For
k=2
: Among length
2
lowercase English strings, there is
1
string (
ab
) whose longest common subsequence with
ab
has length
2
.
Sample Input 2
3 4
aaa
Sample Output 2
390625 62500 3750 101
Sample Input 3
7 50
atcoder
Sample Output 3
309810541 226923474 392073062 146769908 221445233 435648037 862664208 238437587

C++ solution:
#include <bits/stdc++.h>

using i64 = long long;

template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
template<i64 P>
struct MLong {
    i64 x;
    constexpr MLong() : x{} {}
    constexpr MLong(i64 x) : x{norm(x % getMod())} {}

    static i64 Mod;
    constexpr static i64 getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(i64 Mod_) {
        Mod = Mod_;
    }
    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr i64 val() const {
        return x;
    }
    explicit constexpr operator i64() const {
        return x;
    }
    constexpr MLong operator-() const {
        MLong res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MLong inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MLong &operator*=(MLong rhs) & {
        x = mul(x, rhs.x, getMod());
        return *this;
    }
    constexpr MLong &operator+=(MLong rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MLong &operator-=(MLong rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MLong &operator/=(MLong rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MLong operator*(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MLong operator+(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MLong operator-(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MLong operator/(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
        i64 v;
        is >> v;
        a = MLong(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MLong lhs, MLong rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MLong lhs, MLong rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
i64 MLong<0LL>::Mod = i64(1E18) + 9;

template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}

    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
int MInt<0>::Mod = 998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 998244353;
using Z = MInt<P>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M;
    std::cin >> N >> M;

    std::string S;
    std::cin >> S;

    auto get = [&](int mask, int go) {
        std::vector<int> pre(N + 1);
        for (int i = 0; i < N; i++) {
            pre[i + 1] = pre[i] + (mask >> i & 1);
        }
        std::vector<int> f(N + 1);
        for (int i = 0; i < N; i++) {
            if (S[i] == go + 'a') {
                f[i + 1] = pre[i] + 1;
            } else {
                f[i + 1] = std::max(f[i], pre[i + 1]);
            }
        }
        int ans = 0;
        for (int i = 0; i < N; i++) {
            ans += (f[i + 1] - f[i]) << i;
        }
        return ans;
    };

    std::vector f(1 << N, std::vector<int>(26));

    for (int i = 0; i < 1 << N; i++) {
        for (int j = 0; j < 26; j++) {
            f[i][j] = get(i, j);
        }
    }

    std::vector<Z> dp(1 << N);
    dp[0] = 1;
    for (int t = 0; t < M; t++) {
        std::vector<Z> g(1 << N);
        for (int i = 0; i < 1 << N; i++) {
            if (dp[i] == 0) {
                continue;
            }
            for (int j = 0; j < 26; j++) {
                g[f[i][j]] += dp[i];
            }
        }
        dp = g;
    }

    std::vector<Z> ans(N + 1);
    for (int i = 0; i < 1 << N; i++) {
        ans[__builtin_popcount(i)] += dp[i];
    }

    for (int i = 0; i <= N; i++) {
        std::cout << ans[i] << " \n"[i == N];
    }

    return 0;
}

Go solution:
package main

import (
	. "fmt"
	"io"
	"math/bits"
	"os"
)

// https://github.com/EndlessCheng
func run(in io.Reader, out io.Writer) {
	const mod = 998244353
	var n, m int
	var s []byte
	Fscan(in, &n, &m, &s)
	nxt := make([][26]int, 1<<n)
	for diff := range nxt {
		for c := byte('a'); c <= 'z'; c++ {
			var lcs, newLcs, newDiff int
			for j, b := range s {
				one := diff >> j & 1
				pre := newLcs
				newLcs = max(newLcs, lcs+(one|b2i(b == c)))
				newDiff |= (newLcs - pre) << j
				lcs += one
			}
			nxt[diff][c-'a'] = newDiff
		}
	}

	f := make([]int, 1<<n)
	f[0] = 1
	for i := 0; i < m; i++ {
		nf := make([]int, 1<<n)
		for diff, fv := range f {
			for _, newDiff := range nxt[diff] {
				nf[newDiff] = (nf[newDiff] + fv) % mod
			}
		}
		f = nf
	}

	ans := make([]int, n+1)
	for diff, fv := range f {
		ans[bits.OnesCount(uint(diff))] += fv
	}
	for _, v := range ans {
		Fprint(out, v%mod, " ")
	}
}

func main() { run(os.Stdin, os.Stdout) }
func max(a, b int) int { if b > a { return b }; return a }
func b2i(b bool) int {
	if b {
		return 1
	}
	return 0
}

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

public class Main {
    static final int MOD = 998244353;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        String S = br.readLine().trim();
        int totalStates = 1 << N;
        int[][] nextState = new int[totalStates][26];
        for (int stVal = 0; stVal < totalStates; stVal++) {
            int[] olddp = new int[N+1];
            olddp[0] = 0;
            for (int i = 1; i <= N; i++){
                int bit = ((stVal >> (i-1)) & 1);
                olddp[i] = olddp[i-1] + bit;
            }
            for (int c = 0; c < 26; c++) {
                int[] newdp = new int[N+1];
                newdp[0] = 0;
                for (int i = 1; i <= N; i++){
                    int option1 = newdp[i-1];
                    int option2 = olddp[i];
                    int option3 = -100;
                    if(S.charAt(i-1) - 'a' == c) {
                        option3 = olddp[i-1] + 1;
                    }
                    newdp[i] = Math.max(option1, Math.max(option2, option3));
                }
                int ns = 0;
                for (int i = 1; i <= N; i++){
                    int diff = newdp[i] - newdp[i-1];
                    if(diff > 0) {
                        ns |= (1 << (i-1));
                    }
                }
                nextState[stVal][c] = ns;
            }
        }

        long[] cur = new long[totalStates];
        long[] nxt = new long[totalStates];
        cur[0] = 1;
        for (int m = 0; m < M; m++){
            Arrays.fill(nxt, 0);
            for (int stVal = 0; stVal < totalStates; stVal++){
                if(cur[stVal] == 0) continue;
                long ways = cur[stVal];
                for (int c = 0; c < 26; c++){
                    int ns = nextState[stVal][c];
                    nxt[ns] = (nxt[ns] + ways) % MOD;
                }
            }
            long[] temp = cur;
            cur = nxt;
            nxt = temp;
        }

        long[] ans = new long[N+1];
        for (int stVal = 0; stVal < totalStates; stVal++){
            int lcs = Integer.bitCount(stVal);
            ans[lcs] = (ans[lcs] + cur[stVal]) % MOD;
        }

        StringBuilder sb = new StringBuilder();
        for (int k = 0; k <= N; k++){
            sb.append(ans[k]);
            if(k < N) sb.append(" ");
        }
        System.out.println(sb.toString());
    }
}

JavaScript solution:
const MOD = 998244353;

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

    let inputLines = [];
    rl.on('line', (line) => {
        inputLines.push(line);
    }).on('close', () => {
        const [N, M] = inputLines[0].split(' ').map(Number);
        const S = inputLines[1].trim();
        const As = [-1].concat(S.split('').map(c => c.charCodeAt(0) - 'a'.charCodeAt(0)));

        const Lss = [];
        const Ls = [0];
        
        function dfs(i, L) {
            if (i === N) {
                Lss.push(Ls.slice());
                return;
            }
            
            Ls.push(L);
            dfs(i + 1, L);
            Ls.pop();
            
            Ls.push(L + 1);
            dfs(i + 1, L + 1);
            Ls.pop();
        }
        
        dfs(0, 0);
        
        const convs = new Map();
        Lss.forEach((Ls, idx) => {
            convs.set(JSON.stringify(Ls), idx);
        });
        
        const LLL = Lss.length;
        const Css = Array.from({ length: LLL }, () => new Array(26).fill(0));
        
        for (let no = 0; no < LLL; no++) {
            const currentLs = Lss[no];
            for (let ch = 0; ch < 26; ch++) {
                const L2s = [0];
                for (let jS = 1; jS <= N; jS++) {
                    let v = Math.max(currentLs[jS], L2s[jS - 1]);
                    if (ch === As[jS]) {
                        v = Math.max(v, currentLs[jS - 1] + 1);
                    }
                    L2s.push(v);
                }
                const key = JSON.stringify(L2s);
                const no2 = convs.get(key);
                if (no2 === undefined) {
                    console.error("Error: State not found in convs");
                    process.exit(1);
                }
                Css[no][ch] = no2;
            }
        }
        
        let dp = new Array(LLL).fill(0);
        dp[0] = 1;
        
        for (let iT = 0; iT < M; iT++) {
            const dp2 = new Array(LLL).fill(0);
            for (let no = 0; no < LLL; no++) {
                const dpNow = dp[no];
                if (dpNow === 0) continue;
                for (let ch = 0; ch < 26; ch++) {
                    const no2 = Css[no][ch];
                    dp2[no2] = (dp2[no2] + dpNow) % MOD;
                }
            }
            dp = dp2;
        }
        
        const anss = new Array(N + 1).fill(0);
        for (let no = 0; no < LLL; no++) {
            const currentLs = Lss[no];
            const k = currentLs[N];
            anss[k] = (anss[k] + dp[no]) % MOD;
        }
        
        console.log(anss.join(' '));
    });
}

solve();

Python solution:
import sys
def main():
    data = sys.stdin.read().split()
    N, M = map(int, data[:2])
    S = data[2].strip()
    P = 998244353

    # turn S into integers 0..25
    S_idx = [ord(c) - 97 for c in S]

    # Precompute f_prev[b][i] = f[i] for mask b (f[0]=0, f[i]-f[i-1]=(b>>(i-1))&1)
    states = 1 << N
    f_prev = [[0]*(N+1) for _ in range(states)]
    for b in range(states):
        row = f_prev[b]
        # prefix‐sum of bits
        for i in range(1, N+1):
            row[i] = row[i-1] + ((b >> (i-1)) & 1)

    # Precompute transitions trans[b][c] → next mask
    trans = [[0]*26 for _ in range(states)]
    for b in range(states):
        cur = f_prev[b]
        for c in range(26):
            dpn = 0
            nb = 0
            # do one LCS‐DP pass of length N
            for i in range(1, N+1):
                # take max of "skip S[i]" or "skip T char"
                best = cur[i] if cur[i] > dpn else dpn
                # if match, try extend
                if S_idx[i-1] == c:
                    t = cur[i-1] + 1
                    if t > best:
                        best = t
                # did we increase over dpn?
                if best > dpn:
                    nb |= 1 << (i-1)
                dpn = best
            trans[b][c] = nb

    # DP over building T of length M
    dp = [0]*states
    dp[0] = 1
    for _ in range(M):
        nxt = [0]*states
        for b in range(states):
            v = dp[b]
            if v:
                tb = trans[b]
                # distribute to all next‐states
                for b2 in tb:
                    nxt[b2] = (nxt[b2] + v) % P
        dp = nxt

    # collect answers by popcount
    ans = [0]*(N+1)
    for b in range(states):
        k = b.bit_count()
        ans[k] = (ans[k] + dp[b]) % P

    print(*ans)


if __name__ == "__main__":
    main()

Ruby solution:
def main
  input = $stdin.read.split
  idx = 0
  n = input[idx].to_i; idx += 1
  m = input[idx].to_i; idx += 1
  s = input[idx].strip; idx += 1
  mod = 998244353

  # Convert S to indices 0-25
  s_idx = s.chars.map { |c| c.ord - 'a'.ord }

  states = 1 << n

  # Precompute f_prev[b][i] = prefix sum of bits up to i
  f_prev = Array.new(states) { Array.new(n + 1, 0) }
  (0...states).each do |b|
    (1..n).each do |i|
      f_prev[b][i] = f_prev[b][i - 1] + ((b >> (i - 1)) & 1)
    end
  end

  # Precompute transitions trans[b][c] -> new mask
  trans = Array.new(states) { Array.new(26, 0) }
  (0...states).each do |b|
    cur = f_prev[b]
    (0...26).each do |c|
      dpn = 0
      nb = 0
      (1..n).each do |i|
        best = [cur[i], dpn].max
        if s_idx[i - 1] == c
          t = cur[i - 1] + 1
          best = t if t > best
        end
        if best > dpn
          nb |= 1 << (i - 1)
        end
        dpn = best
      end
      trans[b][c] = nb
    end
  end

  # Initialize DP
  dp = Array.new(states, 0)
  dp[0] = 1

  m.times do
    nxt = Array.new(states, 0)
    (0...states).each do |b|
      v = dp[b]
      next if v == 0
      (0...26).each do |c|
        b2 = trans[b][c]
        nxt[b2] = (nxt[b2] + v) % mod
      end
    end
    dp = nxt
  end

  # Collect answers by popcount
  ans = Array.new(n + 1, 0)
  (0...states).each do |b|
    k = b.to_s(2).count('1')
    ans[k] = (ans[k] + dp[b]) % mod
  end

  puts ans.join(' ')
end

main