【YBT2023寒假Day10 B】随機遊走（記憶化搜尋）

随機遊走

題目連結：YBT2023寒假Day10 B

題目大意

有 n 個點排成環，你一開始在 1 号點，每次可以等機率選擇左邊跳兩格，左邊跳一格，右邊跳一格，右邊跳兩格。

走到一個走過的點就停止。

問你走的期望步數。

思路

首先一個暴力的 DP 是有目前點和所有點是否到過這兩個狀态。

不過會發現特殊得到行動方式使得很多狀态是不存在的。

考慮思考怎樣才會是合法的狀态。

考慮到最多跳兩格，那當存在一個 11 11 11 的部分的時候而且你不站在這兩個點上，那你是不能跨越它的。

那我們考慮會不會存在一些不能到的地方，也就是存在 11 X . . . X 11 11X...X11 11X...X11 而且目前你不在這些點上，那就可以直接變成 111...111 111...111 111...111。

那也就是這兩個是等價的，那場上不會存在兩對 11 11 11 中間有 0 0 0，那就是一個 X . . . X 1...1 X . . . X X...X1...1X...X X...X1...1X...X 的形式。

還有一個點就是兩邊的 X . . . X X...X X...X 其實也很固定，因為你隻有跳兩格的情況，那就是 . . . 101011...11010101... ...101011...11010101... ...101011...11010101...

那考慮根據這個形式來統計一下狀态數。

那我們就枚舉 11...11 11...11 11...11 的長度，再枚舉左右 01 01 01 串的長度，在是目前點的位置，那總狀态數是 n 4 n^4 n4 的，記搜轉移就可以了。

代碼

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