分析

在比赛中没有做出了，对矩阵的掌握还是太菜了。先对与原问题考虑。我们发现这个问题其实并不好考虑，其中涉及的状态太多，但是考虑一下用全部方案减去不合法的方案来计算。 。先看前面的 。这里有两种理解。

1. 考虑在每个点后面是否划分那么总的方案数为 。
2. 也可以用插板法来理解，那么我们总的方案数为 。

那么现在问题就是如何求出 。先考虑一个朴素的 ，令 凑成 时的不合法数量。那么 。因为 ，所以一个数的影响不会超过 。这个给我们矩阵优化的基础。那么用矩阵求出 ，复杂度为 ，代码的细节如有不理解的可以私聊啊 。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL read() {
    LL x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
LL n,p,k,Max = 0;
LL qpow(LL a,LL b) {
    LL x = 1;
    for(;b;b>>=1,a=(a*a)%p) 
    if(b&1) x = (x*a)%p;
    return x;
}
struct Sqr{
    LL s[110][110];
    Sqr() {memset(s,0,sizeof(s));}
    Sqr operator * (const Sqr A) const{
        Sqr C;
        for(int i = 0;i < Max;i++) {
            for(int j = 0;j < Max;j++) {
                for(int k = 0;k < Max;k++) {
                    C.s[i][j] = (C.s[i][j] + (s[i][k] * A.s[k][j] % p)) % p;
                }
            }
        }
        return C;
    }
}ans,res;
int main()
{
    n = read();p = read();k = read();
    for(int i = 1;i <= k;i++) {
        LL val = read();
        res.s[val - 1][0] = 1;Max = max(1LL * val,Max);
    }
    for(int i = 0;i < Max - 1;i++) res.s[i][i+1] = 1;
    LL b = n;ans.s[0][0] = 1;
    while(b) {
        if(b&1) ans = ans * res;
        b>>=1;res = res * res;
    }
    printf("%lld\n",((qpow(2,n-1)-ans.s[0][0])%p+p)%p);
    return 0;
}

后记

我还是把题解写清楚一点吧，别骂了别骂了。