| #include <bits/stdc++.h> |
| using namespace std; |
| constexpr long long P = 998244353; |
| constexpr int MAXSTATES = 31 * 31; |
|
|
| int d; |
| int g1_arr[30], gy_arr[30]; |
| int ret_instr[MAXSTATES]; |
| long long cost_arr[MAXSTATES]; |
| int8_t status_arr[MAXSTATES]; |
|
|
| struct Frame { int state; int8_t phase; int dep1, dep2; }; |
| Frame stk[MAXSTATES * 2]; |
| int stk_top; |
|
|
| inline int encode(int i, int x) { return i * (d + 1) + x; } |
|
|
| long long eval_fast() { |
| int ns = (d + 1) * (d + 1); |
| memset(status_arr, 0, ns); |
| stk_top = 0; |
| stk[stk_top++] = {encode(0, 0), 0, -1, -1}; |
| while (stk_top > 0) { |
| Frame& f = stk[stk_top - 1]; |
| int s = f.state, i = s / (d + 1), x = s % (d + 1); |
| if (f.phase == 0) { |
| if (status_arr[s] == 2) { stk_top--; continue; } |
| if (status_arr[s] == 1) return -1; |
| status_arr[s] = 1; |
| if (i < d) { |
| if (x == i + 1) { ret_instr[s] = g1_arr[i]; cost_arr[s] = 1; status_arr[s] = 2; stk_top--; continue; } |
| f.dep1 = encode(gy_arr[i], i + 1); f.phase = 1; stk[stk_top++] = {f.dep1, 0, -1, -1}; continue; |
| } else { |
| if (x == 0) { ret_instr[s] = -1; cost_arr[s] = 1; status_arr[s] = 2; stk_top--; continue; } |
| f.dep1 = encode(d, 1); f.phase = 1; stk[stk_top++] = {f.dep1, 0, -1, -1}; continue; |
| } |
| } else if (f.phase == 1) { |
| if (status_arr[f.dep1] != 2) return -1; |
| int j = ret_instr[f.dep1]; if (j < 0 || j > d) return -1; |
| f.dep2 = encode(j, x); f.phase = 2; stk[stk_top++] = {f.dep2, 0, -1, -1}; continue; |
| } else { |
| if (status_arr[f.dep2] != 2) return -1; |
| ret_instr[s] = ret_instr[f.dep2]; cost_arr[s] = (cost_arr[f.dep1] + cost_arr[f.dep2] + 1) % P; |
| status_arr[s] = 2; stk_top--; |
| } |
| } |
| return status_arr[encode(0, 0)] == 2 ? cost_arr[encode(0, 0)] : -1; |
| } |
|
|
| int main() { |
| d = 26; |
| mt19937 rng(42); |
|
|
| auto t0 = chrono::steady_clock::now(); |
| int total = 0, valid = 0; |
|
|
| for (int i = 0; i < 100000; i++) { |
| for (int j = 0; j < d; j++) { |
| g1_arr[j] = j + 1; |
| gy_arr[j] = rng() % (j + 1); |
| } |
| int nc = rng() % 4; |
| for (int c = 0; c < nc; c++) { |
| g1_arr[rng() % d] = rng() % (d + 1); |
| } |
| total++; |
| long long T = eval_fast(); |
| if (T >= 0) valid++; |
| } |
|
|
| auto t1 = chrono::steady_clock::now(); |
| double ms = chrono::duration_cast<chrono::microseconds>(t1 - t0).count() / 1000.0; |
| printf("d=%d: %d evals in %.1f ms (%.1f us/eval), %d valid (%.1f%%)\n", |
| d, total, ms, ms*1000/total, valid, 100.0*valid/total); |
|
|
| return 0; |
| } |
|
|
