思路:
考虑状压,但是状态数太多。
可是有一些状态是不可用的。比如说xxxx11xxxx11xxx这个状态如果是走到中间那个x,那么这个i就走不出来了。所以对于这种有连续两个1的情况,把它中间的全部x变成1,这样是等价的。
所以可用状态一定形如xxxxxxxxxxx1111111111这样,其中连续的x中没有两个1是连续的而且前后缀一定是01交错的。(因为不能跳到旁边的地方,所以只能跳2个)
于是分析状态数,首先枚举连续x长度,然后枚举两端01串长度,然后枚举走到的位置。所以是n^4的。
c o d e code code
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
int n, p, inv;
map<pair<int, __int128>, int> f;
map<pair<int, __int128>, bool> v;
__int128 one = 1;
int qpow(int x, int k) {
int ans = 1;
for(; k; k >>= 1, x = 1ll * x * x % p) if(k & 1) ans = 1ll * ans * x % p;
return ans;
}
__int128 solve(int x, __int128 s) {
int a = -1, b = -1;
for(int i = x + 1, j = x + 2; i < x + n - 1; i ++, j ++) {
int w1, w2;
if(i >= n) w1 = i - n;
else w1 = i;
if(j >= n) w2 = j - n;
else w2 = j;
if(((s >> w1) & 1) && ((s >> w2) & 1)) {
if(a < 0) a = i;
b = i;
}
}
for(int i = a; i <= b; i ++) {
int w;
if(i >= n) w = i - n;
else w = i;
s |= (one << w);
}
return s;
}
int dfs(int x, __int128 s) {
if(x >= n) x -= n;
if(x < 0) x += n;
if((s >> x) & 1) return 0;
s |= (one << x);
s = solve(x, s);
if(!v[make_pair(x, s)]) f[make_pair(x, s)] = ((0ll + dfs(x + 1, s) + dfs(x + 2, s) + dfs(x - 1, s) + dfs(x - 2, s)) % p * inv % p + 1ll) % p;
v[make_pair(x, s)] = 1;
return f[make_pair(x, s)];
}
int main() {
// freopen("walk.in", "r", stdin);
// freopen("walk.out", "w", stdout);
scanf("%d%d", &n, &p);
inv = qpow(4, p - 2);
if(n == 1) printf("1");
else printf("%d", dfs(0, 0));
return 0;
}