| |
| |
| #include <bits/stdc++.h> |
| using namespace std; |
|
|
| constexpr long long P = 998244353; |
|
|
| int n_instr, maxChar; |
| int type_arr[30]; |
| int pop_c[30], g1[30], push_c[30], g2[30]; |
|
|
| optional<pair<int, long long>> dp[30][1030]; |
| bool vis[30][1030]; |
| bool inf_flag; |
|
|
| pair<int, long long> solve(int i, int x) { |
| if (dp[i][x]) return dp[i][x].value(); |
| if (vis[i][x]) { inf_flag = true; return {-1, 0}; } |
| vis[i][x] = true; |
| if (type_arr[i] == 0) { |
| if (x == pop_c[i]) { dp[i][x] = {g1[i], 1LL}; } |
| else { |
| auto [j, u] = solve(g2[i], push_c[i]); |
| if (inf_flag) return {-1, 0}; |
| auto [k, v] = solve(j, x); |
| if (inf_flag) return {-1, 0}; |
| dp[i][x] = {k, (u + v + 1) % P}; |
| } |
| } else { |
| if (x == 0) { dp[i][x] = {-1, 1LL}; } |
| else { |
| auto [j, u] = solve(g2[i], push_c[i]); |
| if (inf_flag) return {-1, 0}; |
| auto [k, v] = solve(j, x); |
| if (inf_flag) return {-1, 0}; |
| dp[i][x] = {k, (u + v + 1) % P}; |
| } |
| } |
| return dp[i][x].value(); |
| } |
|
|
| long long eval_prog() { |
| for (int i = 0; i < n_instr; i++) |
| for (int j = 0; j <= maxChar; j++) { |
| dp[i][j].reset(); |
| vis[i][j] = false; |
| } |
| inf_flag = false; |
| auto [fi, steps] = solve(0, 0); |
| if (inf_flag) return -1; |
| return steps; |
| } |
|
|
| int main() { |
| mt19937 rng(42); |
|
|
| |
| for (int n = 2; n <= 10; n++) { |
| for (int A : {n, n+2, 2*n, 3*n, min(30, 5*n)}) { |
| n_instr = n; |
| maxChar = A; |
| long long global_max = 0; |
|
|
| for (int restart = 0; restart < 10000; restart++) { |
| |
| for (int i = 0; i < n; i++) { |
| type_arr[i] = (i == n-1) ? 1 : 0; |
| if (type_arr[i] == 0) { |
| pop_c[i] = 1 + rng() % A; |
| g1[i] = rng() % n; |
| push_c[i] = 1 + rng() % A; |
| g2[i] = rng() % n; |
| } else { |
| push_c[i] = 1 + rng() % A; |
| g2[i] = rng() % n; |
| } |
| } |
|
|
| long long T = eval_prog(); |
| if (T < 0) continue; |
|
|
| |
| for (int iter = 0; iter < 5000; iter++) { |
| int i = rng() % n; |
| int sv_pop = pop_c[i], sv_g1 = g1[i], sv_push = push_c[i], sv_g2 = g2[i]; |
| int what = rng() % 4; |
| if (what == 0 && type_arr[i] == 0) pop_c[i] = 1 + rng() % A; |
| else if (what == 1) push_c[i] = 1 + rng() % A; |
| else if (what == 2) g2[i] = rng() % n; |
| else if (type_arr[i] == 0) g1[i] = rng() % n; |
|
|
| long long nT = eval_prog(); |
| if (nT > T) T = nT; |
| else { pop_c[i] = sv_pop; g1[i] = sv_g1; push_c[i] = sv_push; g2[i] = sv_g2; } |
| } |
|
|
| if (T > global_max) global_max = T; |
| } |
|
|
| printf("n=%d A=%d: maxT=%lld (chain max=%lld, P=%d)\n", |
| n, A, global_max, min((1LL<<(n))-1, (long long)P), P); |
| } |
| } |
|
|
| return 0; |
| } |
|
|
