File size: 3,602 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 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 | // Intensive hill climbing / SA search for minimum d
// For each d from 20 to 26, run many restarts with SA
#include <bits/stdc++.h>
using namespace std;
static const long long P = 998244353;
long long Sv[35];
inline long long computeT(int d, const int* gy) {
Sv[0] = 0;
for (int j = 0; j < d; j++) {
long long c = ((Sv[j] - Sv[gy[j]] + (j - gy[j]) + 1) % P + P) % P;
Sv[j + 1] = (Sv[j] + c) % P;
}
return (Sv[d] + d + 1) % P;
}
int main(int argc, char* argv[]) {
if (argc < 3) {
cerr << "Usage: " << argv[0] << " <target_mod_P> <d>" << endl;
return 1;
}
long long target = atoll(argv[1]);
int d = atoi(argv[2]);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int gy[35];
long long bestDist = P;
int bestGy[35];
bool found = false;
auto startTime = chrono::steady_clock::now();
auto elapsed_ms = [&]() {
return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - startTime).count();
};
int restarts = 0;
long long total_iters = 0;
while (elapsed_ms() < 60000 && !found) { // 60 seconds
restarts++;
// Random init
memset(gy, 0, sizeof(int) * d);
for (int j = 1; j < d; j++) gy[j] = rng() % (j + 1);
long long T = computeT(d, gy);
if (T == target) { found = true; memcpy(bestGy, gy, sizeof(int) * d); break; }
// Simulated annealing
double temp = 1e18;
double coolRate = 0.99999;
int noImprove = 0;
for (int iter = 0; iter < 500000; iter++) {
total_iters++;
int j = 1 + rng() % (d - 1);
int og = gy[j];
int ng = rng() % (j + 1);
if (ng == og) continue;
gy[j] = ng;
long long nT = computeT(d, gy);
if (nT == target) {
found = true;
memcpy(bestGy, gy, sizeof(int) * d);
break;
}
long long nd = min((nT - target + P) % P, (target - nT + P) % P);
long long od = min((T - target + P) % P, (target - T + P) % P);
if (nd < od) {
T = nT;
if (nd < bestDist) {
bestDist = nd;
memcpy(bestGy, gy, sizeof(int) * d);
}
} else {
// SA acceptance
double delta = (double)(nd - od);
if (rng() % 1000000 < (int)(1000000.0 * exp(-delta / temp))) {
T = nT;
} else {
gy[j] = og;
}
}
temp *= coolRate;
}
if (found) break;
}
if (found) {
cerr << "FOUND d=" << d << " after " << restarts << " restarts, " << total_iters << " iters" << endl;
cerr << "gy[] =";
for (int j = 0; j < d; j++) cerr << " " << bestGy[j];
cerr << endl;
// Verify
long long verify = computeT(d, bestGy);
cerr << "T=" << verify << " target=" << target << " match=" << (verify == target) << endl;
// Output program
int n = d + 1;
cout << n << endl;
for (int j = 0; j < d; j++) {
cout << "POP " << (j+1) << " GOTO " << (j+2)
<< " PUSH " << (j+1) << " GOTO " << (bestGy[j]+1) << endl;
}
cout << "HALT PUSH 1 GOTO " << n << endl;
} else {
cerr << "NOT FOUND d=" << d << " after " << restarts << " restarts, " << total_iters << " iters, best_dist=" << bestDist << endl;
}
return 0;
}
|