Hugging Face's logo

JustinTX
/
shinka-backup

Model card Files
xet
 Community
shinka-backup / docker_space /frontier_cs_8 /count_general.cpp
JustinTX's picture
JustinTX
Add files using upload-large-folder tool
1fd0050 verified
Raw History Blame Contribute Delete
7.94 kB
#include <bits/stdc++.h>
using namespace std;
static const long long P = 998244353;
// Count distinct T values for the generalized chain structure
// where push_val[i] can be any value in 1..d, not just i+1
int main() {
for (int d = 3; d <= 10; d++) {
// For each instruction i (0..d-1): push_val[i] in 1..d, push_goto[i] in 0..i
// HALT: halt_push in 1..d, halt_goto in 0..d-1
// Total configs per instruction: d * (i+1)
// Total: product(d * (i+1), i=0..d-1) * d * d = d^(d+1) * d! * d ... too many
// Let's just count for standard chain (push_val=i+1) vs generalized
// Standard: push_goto[i] in 0..i, halt fixed
// Generalized: push_val[i] in 1..d, push_goto[i] in 0..i, halt fixed
// For speed, fix halt_push=1, halt_goto=d-1 (last POP)
// and use recursive DP
unordered_set<long long> std_vals, gen_vals;
// Standard chain
{
vector<int> gy(d, 0);
while (true) {
long long Sv[15]; 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;
}
long long T = (Sv[d] + d + 1) % P;
std_vals.insert(T);
int pos = d - 1;
while (pos >= 0) { gy[pos]++; if (gy[pos] <= pos) break; gy[pos] = 0; pos--; }
if (pos < 0) break;
}
}
// Generalized: vary push_val and push_goto
// Use the actual checker DP
{
// Too many configs for large d, sample
int maxVal = d;
mt19937 rng(42);
int samples = min((long long)10000000, (long long)1);
// Actually, let's enumerate for small d
// push_val[i] in 1..d: d choices
// push_goto[i] in 0..i: (i+1) choices
// Total: product(d*(i+1), i=0..d-1) = d^d * d!
long long total = 1;
for (int i = 0; i < d; i++) {
total *= (long long)d * (i + 1);
if (total > 100000000) break;
}
if (total <= 100000000) {
// Enumerate
// Config: array of (push_val, push_goto) for each instruction
vector<int> pv(d, 1), pg(d, 0); // push_val 1..d, push_goto 0..i
long long count = 0;
while (true) {
// Evaluate using recursive DP
// States: (0..d, 0..maxVal)
int nstates = (d + 1) * (maxVal + 1);
vector<int> dest(nstates, -2);
vector<long long> cost(nstates, 0);
vector<int8_t> st(nstates, 0);
bool cycle = false;
function<pair<int,long long>(int,int)> solve = [&](int i, int x) -> pair<int,long long> {
int id = i * (maxVal + 1) + x;
if (st[id] == 2) return {dest[id], cost[id]};
if (st[id] == 1) { cycle = true; return {-2, 0}; }
st[id] = 1;
int dd; long long cc;
if (i < d) {
if (x == i + 1) { dd = i + 1; cc = 1; }
else {
auto [j, u] = solve(pg[i], pv[i]);
if (cycle) return {-2, 0};
if (j < 0 || j > d) { cycle = true; return {-2, 0}; }
auto [k, v] = solve(j, x);
if (cycle) return {-2, 0};
dd = k; cc = (u + v + 1) % P;
}
} else {
if (x == 0) { dd = -1; cc = 1; }
else {
// HALT pushes 1, goto d-1
auto [j, u] = solve(d - 1, 1);
if (cycle) return {-2, 0};
if (j < 0 || j > d) { cycle = true; return {-2, 0}; }
auto [k, v] = solve(j, x);
if (cycle) return {-2, 0};
dd = k; cc = (u + v + 1) % P;
}
}
st[id] = 2; dest[id] = dd; cost[id] = cc;
return {dd, cc};
};
auto [_, T] = solve(0, 0);
if (!cycle) gen_vals.insert(T);
count++;
if (count % 5000000 == 0) cerr << "d=" << d << " count=" << count << "/" << total << endl;
// Increment config
int pos = d - 1;
while (pos >= 0) {
// Try incrementing push_goto first, then push_val
pg[pos]++;
if (pg[pos] <= pos) break;
pg[pos] = 0;
pv[pos]++;
if (pv[pos] <= d) break;
pv[pos] = 1;
pos--;
}
if (pos < 0) break;
}
} else {
cerr << "d=" << d << ": too many configs (" << total << "), sampling" << endl;
for (int s = 0; s < 10000000; s++) {
vector<int> pv(d), pg(d);
for (int i = 0; i < d; i++) {
pv[i] = 1 + rng() % d;
pg[i] = rng() % (i + 1);
}
int maxVal2 = d;
int nstates = (d + 1) * (maxVal2 + 1);
vector<int> dest(nstates, -2);
vector<long long> cost(nstates, 0);
vector<int8_t> st(nstates, 0);
bool cycle = false;
function<pair<int,long long>(int,int)> solve = [&](int i, int x) -> pair<int,long long> {
int id = i * (maxVal2 + 1) + x;
if (st[id] == 2) return {dest[id], cost[id]};
if (st[id] == 1) { cycle = true; return {-2, 0}; }
st[id] = 1;
int dd; long long cc;
if (i < d) {
if (x == i + 1) { dd = i + 1; cc = 1; }
else {
auto [j, u] = solve(pg[i], pv[i]);
if (cycle) return {-2, 0};
if (j < 0 || j > d) { cycle = true; return {-2, 0}; }
auto [k, v] = solve(j, x);
if (cycle) return {-2, 0};
dd = k; cc = (u + v + 1) % P;
}
} else {
if (x == 0) { dd = -1; cc = 1; }
else {
auto [j, u] = solve(d - 1, 1);
if (cycle) return {-2, 0};
if (j < 0 || j > d) { cycle = true; return {-2, 0}; }
auto [k, v] = solve(j, x);
if (cycle) return {-2, 0};
dd = k; cc = (u + v + 1) % P;
}
}
st[id] = 2; dest[id] = dd; cost[id] = cc;
return {dd, cc};
};
auto [_, T] = solve(0, 0);
if (!cycle) gen_vals.insert(T);
}
}
}
cout << "d=" << d << ": std=" << std_vals.size() << " gen=" << gen_vals.size() << endl;
}
return 0;
}