题目大意
有1~n共n个数，每次删掉x并把x-2和x+K加上，问可能的序列个数
n<=150
题解
这才叫集训队作业
比较正常的做法：https://www.cnblogs.com/Tiw-Air-OAO/p/11795339.html
由于比较naive没有想出来，于是搞了另一种做法
把x向x-2和x+K连边，则一个删除序列满足条件当且仅当导出子图中无环（按拓扑序删就可以了）
K是偶数很简单，按奇偶分开就变成不能选连续的K/2+1个，随便dp
考虑K是奇数的情况
设K=7，则所有不合法方案的必然包含以下子串（?表示任意o表示选择）：
ooooooooo
o?ooooooo?o
o?o?ooooo?o?o
o?o?o?ooo?o?o?o
按奇偶分开，就是奇/偶上连续一段和中间偶/奇的连续一段
很轻松的想到设f[i][j][k]表示放到i奇数位连续j个偶数位连续k个的方案，然后在中间连续段的后一位判断
这样有个问题，后面的部分无法判断，举个栗子
o?o?o?ooo?o?o?o
在ooo后的?处判断不选，那么接下来的三个o位置上不能同时选
考虑再加两维来表示奇/偶接下若干位不能同时选，这样是n^5的，考虑优化
可以发现ooo?无论怎样接（连续段+间隔）后面的长度都为K+2，而在至多K-2位置上就有一个不能选的，所以不会产生新的限制（不可能在?后面跳一位再选，两个空位会把前面的阻断）
记录连续选个数的意义就是为了产生限制，而现在不可能产生限制，所以就没有记的必要了
所以设f[i][j][k][0/1][0/1]表示放了i个，奇/偶 连续j/k个 或 接下来的j/k个不能同时选
转移讨论一下即可
code
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define add(a,b) a=((a)+(b))%mod
#define ll long long
//#define file
using namespace std;
ll f[151][151][151][2][2],g[151][151],ans;
int n,m,mod,i,j,k,l,p1,p2,I,J,K,L,P1,P2,s;
ll qpower(ll a,int b) {ll ans=1;while (b) {if (b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;} return ans;}
int main()
{
#ifdef file
freopen("agc035E.in","r",stdin);
#endif
scanf("%d%d%d",&n,&m,&mod);
if (m==n) {printf("%lld
",qpower(2,n));return 0;}
if (!(m&1))
{
g[0][0]=1;
fo(i,1,n)
{
fo(j,0,m/2)
{
if (j<m/2) add(g[i][j+1],g[i-1][j]);
add(g[i][0],g[i-1][j]);
}
}
j=k=0;
fo(i,0,m/2) add(j,g[(n+1)/2][i]),add(k,g[n/2][i]);
printf("%lld
",1ll*j*k%mod);
}
else
{
f[0][0][0][0][0]=1;
fo(i,1,n)
{
fo(j,0,i-1)
{
fo(k,0,i-1)
{
fo(p1,0,1)
{
fo(p2,0,1)
if (f[i-1][j][k][p1][p2])
{
fo(s,0,1)
{
if (s) //yes
{
if (i&1)
{
K=k,P2=p2;
if (!p1) J=j+1;
else
{if (j==1) continue; else J=j-1,P1=1;};
}
else
{
J=j,P1=p1;
if (!p2) K=k+1;
else
{if (k==1) continue; else K=k-1,P2=1;};
}
}
else //no
{
if (i&1)
{
if (p1 || p2 || k<m/2+2 || !j)
J=0,P1=0,K=k,P2=p2;
else
{
if (j>=m/2+1) continue;
J=0,P1=0,K=m/2+1-j,P2=1;
}
}
else
{
if (p2 || p1 || j<m/2+2 || !k)
K=0,P2=0,J=j,P1=p1;
else
{
if (k>=m/2+1) continue;
K=0,P2=0,J=m/2+1-k,P1=1;
}
}
}
add(f[i][J][K][P1][P2],f[i-1][j][k][p1][p2]);
}
}
}
}
}
}
fo(j,0,n)
{
fo(k,0,n)
{
fo(p1,0,1)
{
fo(p2,0,1)
if (f[n][j][k][p1][p2] && !((!p1 && !p2 && ((n&1) && j>m/2+1 || !(n&1) && j>m/2)) && (!(n&1) && k>m/2+1 || (n&1) && k>m/2)))
add(ans,f[n][j][k][p1][p2]);
}
}
}
printf("%lld
",ans);
}
}