C++14(g++5.4) 解法, 执行用时: 1064ms, 内存消耗: 632K, 提交时间: 2020-09-05 18:12:24

#include<bits/stdc++.h>
using namespace std;
//dengyaotriangle!

const int maxn=105;

int mdn;
struct mat{
    int v[maxn][maxn];
    mat(){memset(v,0,sizeof(v));}
};

mat operator*(const mat&a,const mat&b){
    mat c;
    for(int i=0;i<maxn;i++){
        for(int k=0;k<maxn;k++){
            for(int j=0;j<maxn;j++){
                c.v[i][j]=(c.v[i][j]+a.v[i][k]*(long long)b.v[k][j])%mdn;
            }
        }
    }
    return c;
}

template<typename t,typename te,typename tm> inline t qpowm(t bse,te ex,tm mdn){t ans=(mdn!=1);while(ex){if(ex&1)ans=(ans*bse)%mdn;bse=(bse*bse)%mdn;ex>>=1;}return ans;}

int main(){
    long long n;
    cin>>n>>mdn;
    mat bse;
    int k;
    cin>>k;
    for(int i=1;i<maxn;i++)bse.v[i-1][i]=1;
    while(k--){
        int u;cin>>u;
        bse.v[u-1][0]=1;
    }
    mat e;
    int t=qpowm<long long>(2,n-1,mdn);
    for(int i=0;i<maxn;i++)e.v[i][i]=1;
    while(n){
        if(n&1)e=e*bse;
        n>>=1;bse=bse*bse;
    }
    int a=e.v[0][0];
    cout<<(t-a+mdn)%mdn;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 810ms, 内存消耗: 608K, 提交时间: 2020-09-05 18:30:47

#include<bits/stdc++.h>
using namespace std;
long long n;
int p;
int k;
int a[110];
int mn=2;
struct matrix
{
	int f[101][101];
	void clear(){memset(f,0,sizeof(f));}
	matrix operator * (const matrix a)const
	{
		matrix c; c.clear();
		for(int i=1;i<=mn;i++)
			for(int j=1;j<=mn;j++)
				for(int k=1;k<=mn;k++)
					c.f[i][k]=(1ll*f[i][j]*a.f[j][k]+c.f[i][k])%p;
		return c;
	}
}x,ans;
int qp(int x,long long k)
{
	int res=1;
	for(;k;k>>=1,x=1ll*x*x%p)
		if(k&1)
			res=1ll*res*x%p;
	return res;
}
int main()
{
	scanf("%lld%d",&n,&p);
	scanf("%d",&k);
	for(int i=1;i<=k;i++)
		scanf("%d",&a[i]),mn=max(mn,a[i]);
	for(int i=1;i<=k;i++)
		x.f[mn-a[i]+1][mn]=1;
	for(int i=2;i<=mn;i++)
		x.f[i][i-1]=1;
	ans.f[1][mn]=1;
	long long m=n;
	for(;m;m>>=1,x=x*x)
		if(m&1)
			ans=ans*x;
	printf("%d\n",(qp(2,n-1)-ans.f[1][mn]+p)%p);
	return 0;
}