// Analyze what step counts are achievable with small n and varying alphabet // Try to understand the structure of possible step counts #include using namespace std; constexpr long long P = 998244353; struct MInt { long long x; MInt(): x(0) {} MInt(long long v): x(((v % P) + P) % P) {} MInt operator+(const MInt& b) const { return MInt(x + b.x); } MInt operator-(const MInt& b) const { return MInt(x - b.x); } MInt operator*(const MInt& b) const { return MInt(x * b.x); } bool operator==(const MInt& b) const { return x == b.x; } }; int n_instr; int type_arr[30]; // 0=POP, 1=HALT int pop_char_arr[30], goto1_arr[30], push_char_arr[30], goto2_arr[30]; int maxChar; optional> dp[30][1030]; bool vis[30][1030]; bool infinite_flag; pair solve(int i, int x) { if (dp[i][x]) return dp[i][x].value(); if (vis[i][x]) { infinite_flag = true; return {-1, MInt(0)}; } vis[i][x] = true; if (type_arr[i] == 0) { // POP if (x == pop_char_arr[i]) { dp[i][x] = {goto1_arr[i], MInt(1)}; } else { auto [j, u] = solve(goto2_arr[i], push_char_arr[i]); if (infinite_flag) return {-1, MInt(0)}; auto [k, v] = solve(j, x); if (infinite_flag) return {-1, MInt(0)}; dp[i][x] = {k, u + v + MInt(1)}; } } else { // HALT if (x == 0) { dp[i][x] = {-1, MInt(1)}; } else { auto [j, u] = solve(goto2_arr[i], push_char_arr[i]); if (infinite_flag) return {-1, MInt(0)}; auto [k, v] = solve(j, x); if (infinite_flag) return {-1, MInt(0)}; dp[i][x] = {k, u + v + MInt(1)}; } } return dp[i][x].value(); } MInt evaluate() { for (int i = 0; i < n_instr; i++) for (int j = 0; j <= maxChar; j++) { dp[i][j].reset(); vis[i][j] = false; } infinite_flag = false; auto [fi, steps] = solve(0, 0); if (infinite_flag) return MInt(P - 1); // sentinel for infinite return steps; } int main() { // Let's try a specific structure: // n=2: one HALT + one POP // HALT pushes some char b and goes to instruction g // POP pops some char a, goto g1, push char c, goto g2 // With n=2, alphabet {1..A}: // Instruction 0: HALT PUSH b GOTO g (g in {0,1}) // Instruction 1: POP a GOTO g1 PUSH c GOTO g2 // solve(0, 0) = 1 (halt immediately) // solve(0, x) for x != 0: push b, goto g. So solve(g, b) then solve(result, x) // steps = 1 + solve(g, b).steps + solve(solve(g,b).ret, x).steps // Let's manually compute for n=2: // Instr 0: HALT PUSH 1 GOTO 1 // Instr 1: POP 1 GOTO 0 PUSH 1 GOTO 0 // // solve(0, 0) = (-1, 1) -- halt // solve(1, 1) = (0, 1) -- pop, goto 0 // solve(0, x) for x>0: push 1 goto 1. solve(1, 1) = (0, 1). solve(0, x). // But this is circular! solve(0, x) depends on solve(0, x). // So this program doesn't halt for x > 0 (other than when x is on the HALT path) // For the program to halt, we need no cycles in the dependency graph. // With n=2, alphabet 1..2: // Instr 0: HALT PUSH 1 GOTO 1 // Instr 1: POP 2 GOTO 0 PUSH 1 GOTO 0 // // solve(0, 0) = (-1, 1) // solve(1, 2) = (0, 1) -- pop, goto 0 // solve(0, x) for x != 0: push 1, goto 1, solve(1, 1) // solve(1, 1): x=1 != 2 (pop char). Push 1, goto 0. solve(0, 1) then solve(result, 1). // solve(0, 1): push 1, goto 1. solve(1, 1) -- CYCLE! infinite. // Hmm. The challenge with small n is avoiding cycles. // Chain programs avoid cycles by having strictly increasing instruction indices. // Let me think about what makes chain programs special: // Chain: instrs 0..d-1 are POP, instr d is HALT // POP j: pops char (j+1), goto (j+1), push char (j+1), goto gy[j] // HALT d: push 1, goto d // The key is: POP j pops char (j+1). So when we push char (j+1) and call solve(gy[j], j+1), // the only instruction that can pop char (j+1) is instruction j itself. // This creates a well-structured recursion. // For non-chain: we could use different characters to create multiple "levels" of recursion // with the same instruction. E.g., one POP instruction that handles multiple stack symbols. // Actually, let me think about n=3 with the right structure: // If we can get 2 POP instructions to both create exponential growth, // and chain them, we might get 2^a * 2^b type behavior with a+b controlled. // Actually, let me try a different approach: enumerate step counts for very small programs n_instr = 3; maxChar = 4; set seen_steps; long long max_steps = 0; // Enumerate all programs with n=3, alphabet 1..4 // Last instruction must be HALT // Try all configurations int count = 0; int halting = 0; for (int t0 = 0; t0 <= 1; t0++) for (int t1 = 0; t1 <= 1; t1++) { type_arr[2] = 1; // HALT type_arr[0] = t0; type_arr[1] = t1; auto enumerate_instr = [&](int i, auto& self, auto& callback) -> void { if (i == n_instr) { callback(); return; } if (type_arr[i] == 0) { // POP for (int a = 1; a <= maxChar; a++) for (int g1 = 0; g1 < n_instr; g1++) for (int c = 1; c <= maxChar; c++) for (int g2 = 0; g2 < n_instr; g2++) { pop_char_arr[i] = a; goto1_arr[i] = g1; push_char_arr[i] = c; goto2_arr[i] = g2; self(i + 1, self, callback); } } else { // HALT for (int c = 1; c <= maxChar; c++) for (int g2 = 0; g2 < n_instr; g2++) { push_char_arr[i] = c; goto2_arr[i] = g2; self(i + 1, self, callback); } } }; auto callback = [&]() { count++; MInt T = evaluate(); if (T.x != (P - 1) % P) { halting++; seen_steps.insert(T.x); if (T.x > max_steps) { max_steps = T.x; cerr << "New max: " << T.x << " with config:"; for (int i = 0; i < n_instr; i++) { if (type_arr[i] == 0) { cerr << " POP" << pop_char_arr[i] << "→" << goto1_arr[i] << ",push" << push_char_arr[i] << "→" << goto2_arr[i]; } else { cerr << " HALT,push" << push_char_arr[i] << "→" << goto2_arr[i]; } } cerr << endl; } } }; enumerate_instr(0, enumerate_instr, callback); } cout << "Total programs: " << count << ", halting: " << halting << endl; cout << "Distinct step counts: " << seen_steps.size() << endl; cout << "Max step count: " << max_steps << endl; cout << "First 50 step counts:"; int printed = 0; for (long long v : seen_steps) { if (printed++ >= 50) break; cout << " " << v; } cout << endl; return 0; }