题意

有一个黑板上面写了 $\mathbb{Z}$ 内的所有数字。每个数字出现且仅出现一次。现在你可以对这个黑板做任意次以下操作：

• 选择一个在黑板上目前出现的在 $[1,N]$ 之间的数字 $x$，并删去 $x$
• 如果 $x-2$ 不在黑板上，把 $x-2$ 写在黑板上
• 如果 $x+K$ 不在黑板上，把 $x+K$ 写在黑板上

求有多少种最终结果序列。对 $M$ 取模。

$1 \leq K \leq N \leq 150,10^8 \leq M \leq 10^9$。

题解

方案只与哪些数字被删除了有关系，我们设我们按顺序删除的数字序列为 $S$，发现那个删除操作实际上是一些先后顺序限制：$x-2,x+K$ 必须在 $x$ 之后被删除。

所以我们对于 $x$ ，向 $x-2,x+K$ 连边，现在问题就是有多少个在 $[1,N+K]$ 之间选数的方案数，满足不会选出环。

看到 $2$ 这个奇怪的数字，让我们想到可能和 $K$ 的奇偶性有关。如果 $K$ 是偶数，那么奇数和偶数之间互不影响可以分开。对于每一类，有环当且仅当存在连续段长度 $\geq \frac{K}{2}+1$ 的连续段。这样直接 dp 一下就好了。

现在问题在于 $K$ 是奇数，我们还是要找一下性质。我们把数排成这样（以 $N=8,K=3$ 为例）：

首先我们发现所有的环都可以归纳成跳 $2$ 次 $+K$ 操作的环，所以我们重点研究这种环是怎么存在的。

我们发现可能的环只有可能是从左边某个点 $x$ 开始往上走 $n_1$ 步（这时候是 $x-2n_1$），然后跳到右边（变成 $x-2n_1+K$），然后再往上走 $n_2$ 步（$x-2n_1+K-2n_2$），然后跳到 $x$。也就是要求 $x = x-2n_1+2K-2n_2$，可以得到 $n_1+n_2 = K$。也就是说我们要求不能存在长度 $\geq K+2$ 的环。

这样我们再顺着这个层进行 dp，设 $f_{i,j,k}$ 表示到了第 $i$ 层，当前与第 $i$ 层联通的，最长的上-右-上路径长度为 $j$，为了更新答案我们还需要记录右侧最长的上路径是 $k$。

转移枚举左右两个点（也有可能只有一个点）选还是不选，注意要保证 $j$ 统计的路径一定往右就好了（也就是注意一下，$j=0$ 的时候只选左边的点不能让它转移到 $j=1$）。

复杂度 $O(n^3)$。

代码

#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 150 + 5;
int n,k,ha;

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

namespace Subtask1{
    int f[2][MAXN][MAXN],now;
    inline void Solve(){
        CLR(f[now=0],0);f[now][0][0] = 1;k >>= 1;
        FOR(i,1,n){
            CLR(f[now^1],0);
            FOR(j,0,::k){
                FOR(k,0,::k){
                    if(!f[now][j][k]) continue;
                    int c = f[now][j][k];
                    add(f[now^1][(i&1)?0:j][(i&1)?k:0],c);
                    add(f[now^1][j+(i&1)][k+(!(i&1))],c);
                }
            }
            now ^= 1;
        }
        int ans = 0;
        FOR(i,0,k) FOR(j,0,k) add(ans,f[now][i][j]);
        printf("%d\n",ans);
    }
}

namespace Subtask2{
    int f[2][MAXN][MAXN],now;
    inline void Solve(){
        CLR(f[now=0],0);
        f[now][0][0] = 1;
        for(int i = 2-k;i <= n;i += 2){
            CLR(f[now^1],0);
            FOR(j,0,::k+1){
                FOR(k,0,n){
                    int c = f[now][j][k];
                    if(!c) continue;
                    if(i < 0){// 只有偶数
                        add(f[now^1][0][0],c);
                        add(f[now^1][0][k+1],c);
                    }
                    else if(i+::k > n){// 只有奇数
                        add(f[now^1][0][0],c);
                        if(j) add(f[now^1][j+1][0],c);
                        else add(f[now^1][0][0],c);
                        // 注意:必须要求是拐弯后的路径长度
                        // 所以只在左边的长度为1的路径是不允许的
                    }
                    else{// 都有
                        add(f[now^1][0][0],c);//00
                        add(f[now^1][0][k+1],c);//01
                        if(j) add(f[now^1][j+1][0],c);//10
                        else add(f[now^1][0][0],c);
                        add(f[now^1][std::max(j+1,k+2)][k+1],c);//11
                    }
                }
            }
            now ^= 1;
        }
        int ans = 0;
        FOR(i,0,k+1) FOR(j,0,n) add(ans,f[now][i][j]);
        printf("%d\n",ans);
    }
}

int main(){
    scanf("%d%d%d",&n,&k,&ha);
    if(!(k&1)) Subtask1::Solve();
    else Subtask2::Solve();
    return 0;
}