拆分 题解

考虑容斥，即任意拆分的方案数减去拆分成不喜欢的数的方案数。

先考虑前者。设 表示 任意拆分的方案数，则有

即

再考虑后者。考虑 DP，设 为 拆分为不喜欢的数的方案数，则有

因为 ，所以把相邻的 个状态存到矩阵里，然后矩阵快速幂即可。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10;

ll n; int k,a[N]; int mod;
int qpow(int a,ll b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

struct Matrix {
    int s[110][110];
    Matrix() { memset(s,0,sizeof(s)); }
    int* operator [](int i) { return s[i]; }
} A,Q;
Matrix operator *(Matrix a,Matrix b) {
    Matrix c;
    for (int k=0;k<100;++k)
        for (int i=0;i<100;++i)
            for (int j=0;j<100;++j)
                c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j])%mod;
    return c;
}
Matrix qpow(Matrix a,ll b) {
    Matrix c=a; --b;
    for (;b;b>>=1,a=a*a) if (b&1) c=c*a;
    return c;
}

int main() {
    n=read(),mod=read(),k=read();
    for (int i=1;i<=k;++i) a[i]=read();
    A[0][0]=1;
    for (int i=1;i<100;++i)
        for (int j=1;j<=k;++j)
            if (i-a[j]>=0) A[0][i]=(A[0][i]+A[0][i-a[j]])%mod;
    for (int i=1;i<100;++i) Q[i][i-1]=1;
    for (int i=1;i<=k;++i) Q[100-a[i]][99]=1;
    A=A*qpow(Q,n);
    printf("%d\n",(qpow(2,n-1)-A[0][0]+mod)%mod);
    return 0;
}