随机游走
题目链接：YBT2023寒假Day10 B
题目大意
有 n 个点排成环，你一开始在 1 号点，每次可以等概率选择左边跳两格，左边跳一格，右边跳一格，右边跳两格。
走到一个走过的点就停止。
问你走的期望步数。
思路
首先一个暴力的 DP 是有当前点和所有点是否到过这两个状态。
不过会发现特殊得到行动方式使得很多状态是不存在的。
考虑思考怎样才会是合法的状态。
考虑到最多跳两格，那当存在一个 \(11\) 的部分的时候而且你不站在这两个点上，那你是不能跨越它的。
那我们考虑会不会存在一些不能到的地方，也就是存在 \(11X...X11\) 而且当前你不在这些点上，那就可以直接变成 \(111...111\)。
那也就是这两个是等价的，那场上不会存在两对 \(11\) 中间有 \(0\)，那就是一个 \(X...X1...1X...X\) 的形式。
还有一个点就是两边的 \(X...X\) 其实也很固定，因为你只有跳两格的情况，那就是 \(...101011...11010101...\)
那考虑根据这个形式来统计一下状态数。
那我们就枚举 \(11...11\) 的长度，再枚举左右 \(01\) 串的长度，在是当前点的位置，那总状态数是 \(n^4\) 的，记搜转移就可以了。
代码
#include<map>
#include<cstdio>
using namespace std;
const int N = 80;
int n, mo, inv4, ans;
map <pair<int, __int128>, int> rem;
__int128 one = 1;
int add(int x, int y) {return x + y >= mo ? x + y - mo : x + y;}
int dec(int x, int y) {return x < y ? x - y + mo : x - y;}
int mul(int x, int y) {return 1ll * x * y % mo;}
int addex(int x, int y, int z) {return x + y >= z ? x + y - z : x + y;}
int decex(int x, int y, int z) {return x < y ? x - y + z : x - y;}
int ksm(int x, int y) {
int re = 1;
while (y) {
if (y & 1) re = mul(re, x);
x = mul(x, x); y >>= 1;
}
return re;
}
__int128 work(int fr, __int128 s) {
int a = -1, b = -1;
for (int i = addex(fr, 1, n); i != decex(fr, 1, n); i = addex(i, 1, n)) {
int j = addex(i, 1, n);
if (((s >> i) & 1) && ((s >> j) & 1)) {
if (a == -1) a = i;
b = i;
}
}
for (int i = a; i != b; i = addex(i, 1, n)) {
s |= (one << i);
}
return s;
}
int dfs(int now, __int128 s) {
if ((s >> now) & 1) return 0;
s |= (one << now); s = work(now, s);
if (rem[make_pair(now, s)]) return rem[make_pair(now, s)];
return rem[make_pair(now, s)] = add(1, mul(inv4, add(add(dfs(addex(now, 1, n), s), dfs(addex(now, 2, n), s)), add(dfs(decex(now, 1, n), s), dfs(decex(now, 2, n), s)))));
}
int main() {
freopen("walk.in", "r", stdin);
freopen("walk.out", "w", stdout);
scanf("%d %d", &n, &mo); inv4 = ksm(4, mo - 2);
if (n == 1) {printf("1"); return 0;}
printf("%d", dfs(0, 0));
return 0;
}