File size: 3,597 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | // Check: what range of T values do generalized chains with d=26 produce?
// Specifically, can T exceed 134217727 (the standard chain max)?
#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);
}
// Modify some g1
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;
}
|