| |
| P = 998244353 |
|
|
| def computeT(d, gy): |
| Sv = [0] * (d + 1) |
| for j in range(d): |
| c = (Sv[j] - Sv[gy[j]] + (j - gy[j]) + 1) % P |
| Sv[j + 1] = (Sv[j] + c) % P |
| return (Sv[d] + d + 1) % P |
|
|
| d = 27 |
| target1 = 150994941 |
| target2 = 150994939 |
|
|
| |
| print("All two-change solutions for d=27:") |
| for j1 in range(d): |
| for g1 in range(1, j1+1): |
| for j2 in range(j1+1, d): |
| for g2 in range(1, j2+1): |
| gy = [0]*d |
| gy[j1] = g1 |
| gy[j2] = g2 |
| T = computeT(d, gy) |
| if T == target1: |
| print(f"TARGET1: gy[{j1}]={g1}, gy[{j2}]={g2}") |
| if T == target2: |
| print(f"TARGET2: gy[{j1}]={g1}, gy[{j2}]={g2}") |
|
|
| |
| print("\nSearching smaller d values with multi-change:") |
| for d in range(20, 27): |
| print(f"\n=== d={d} (n={d+1}) ===") |
| |
| |
| import random |
| random.seed(42 + d) |
|
|
| best_gy = None |
| for trial in range(100000): |
| gy = [0] * d |
| |
| num_changes = random.randint(1, min(6, d)) |
| positions = random.sample(range(1, d), min(num_changes, d-1)) |
| for j in positions: |
| gy[j] = random.randint(0, j) |
|
|
| T = computeT(d, gy) |
| if T == target1: |
| print(f"FOUND TARGET1 d={d}: gy = {gy}") |
| best_gy = gy[:] |
| break |
| if T == target2: |
| print(f"FOUND TARGET2 d={d}: gy = {gy}") |
| best_gy = gy[:] |
| break |
|
|
| if best_gy is None: |
| |
| for restart in range(200): |
| gy = [0] * d |
| for j in range(1, d): |
| gy[j] = random.randint(0, j) |
| T = computeT(d, gy) |
|
|
| for iteration in range(50000): |
| j = random.randint(1, d-1) |
| old_g = gy[j] |
| gy[j] = random.randint(0, j) |
| nT = computeT(d, gy) |
|
|
| if nT == target1 or nT == target2: |
| print(f"FOUND d={d}: T={nT}, gy = {gy}") |
| best_gy = gy[:] |
| break |
|
|
| nd = min((nT - target1) % P, (target1 - nT) % P, (nT - target2) % P, (target2 - nT) % P) |
| od = min((T - target1) % P, (target1 - T) % P, (T - target2) % P, (target2 - T) % P) |
|
|
| if nd <= od: |
| T = nT |
| else: |
| gy[j] = old_g |
|
|
| if best_gy: break |
|
|
