File size: 1,429 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 | #include <bits/stdc++.h>
using namespace std;
static const long long P = 998244353;
int main() {
// For d=10, enumerate all d!=3628800 configs and count distinct T values
for (int d = 3; d <= 12; d++) {
unordered_set<long long> vals;
vector<int> gy(d, 0);
while (true) {
long long Sv[35];
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;
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;
}
long long total = 1;
for (int j = 1; j <= d; j++) total *= j;
// But gy[0] is always 0, so actual configs = d!/1 = d!... wait gy[0] must be 0
// Actually gy[j] ranges from 0 to j, so there are (j+1) choices for gy[j]
// Total = product(j+1, j=0..d-1) = product(1,2,...,d) = d!
// Wait no: gy[0] can only be 0 (0..0), gy[1] can be 0 or 1, etc.
// So total = 1 * 2 * 3 * ... * d = d!
cout << "d=" << d << ": " << vals.size() << " distinct values out of " << total << " configs" << endl;
}
return 0;
}
|