| |
| |
| #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); |
|
|
| long long max_T = 0; |
| long long min_T = P; |
| int above_134M = 0; |
| int total_valid = 0; |
| set<long long> unique_T; |
|
|
| auto t0 = chrono::steady_clock::now(); |
|
|
| for (int trial = 0; trial < 1000000; trial++) { |
| for (int j = 0; j < d; j++) { |
| g1_arr[j] = j + 1; |
| gy_arr[j] = rng() % (j + 1); |
| } |
| |
| int nc = 1 + rng() % 5; |
| for (int c = 0; c < nc; c++) { |
| g1_arr[rng() % d] = rng() % (d + 1); |
| } |
|
|
| long long T = eval_fast(); |
| if (T < 0) continue; |
| total_valid++; |
| if (T > max_T) { |
| max_T = T; |
| fprintf(stderr, "New max T: %lld at trial %d\n", T, trial); |
| } |
| if (T < min_T) min_T = T; |
| if (T > 134217727) above_134M++; |
| if (unique_T.size() < 100000) unique_T.insert(T); |
|
|
| if (trial % 100000 == 0) { |
| auto t1 = chrono::steady_clock::now(); |
| double ms = chrono::duration_cast<chrono::milliseconds>(t1 - t0).count(); |
| fprintf(stderr, "trial=%d valid=%d max=%lld min=%lld above_134M=%d unique=%zu time=%.0fms\n", |
| trial, total_valid, max_T, min_T, above_134M, unique_T.size(), ms); |
| } |
| } |
|
|
| printf("Total valid: %d\n", total_valid); |
| printf("Max T: %lld\n", max_T); |
| printf("Min T: %lld\n", min_T); |
| printf("Above 134217727: %d (%.2f%%)\n", above_134M, 100.0*above_134M/total_valid); |
| printf("Unique T values: %zu\n", unique_T.size()); |
|
|
| return 0; |
| } |
|
|
