docker_space/frontier_cs_8/count_general.cpp

#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;
}