| |
| |
| #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) { |
| restarts++; |
| |
| 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; } |
|
|
| |
| 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 { |
| |
| 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; |
| |
| long long verify = computeT(d, bestGy); |
| cerr << "T=" << verify << " target=" << target << " match=" << (verify == target) << endl; |
| |
| 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; |
| } |
|
|
