本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-08-12 11:54:12

做法

可以快速得出 $x \in [1,100]$ 的答案。
将其记录下来，通过矩阵乘法转移到 $x \in [2,101]$ 的答案。
以此类推。

Code

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	const ll mod=1e9+7;
	const int maxn=1e5+5;
	const int mamx=105;
	int n,x,d[maxn];
	struct Matrix
	{
		ll imap[mamx][mamx];
		void init()
		{
			memset(imap,0,sizeof imap);
		}
		Matrix operator*(const Matrix& b)
		{
			Matrix ans;
			ans.init();
			for(int i=1;i<=101;i++)
			{
				for(int j=1;j<=101;j++)
				{
					for(int k=1;k<=101;k++)
					{
						ans.imap[i][j]+=imap[i][k]*b.imap[k][j];
						ans.imap[i][j]%=mod;
					}
				}
			}
			return ans;
		}
	}A,B,out;
	Matrix ksm(Matrix a,ll b)
	{
		Matrix ret;
		ret.init();
		for(int i=1;i<=101;i++)ret.imap[i][i]=1;
		while(b)
		{
			if(b&1)ret=ret*a;
			a=a*a;
			b>>=1;
		}
		return ret;
	}
	ll f0[105],f[105],cnt[105];
	void main()
	{
		scanf("%d%d",&n,&x);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&d[i]);
			cnt[d[i]]++;
		}
		f0[0]=1;
		for(int i=1;i<=100;i++)
		{
			for(int j=1;j<=i;j++)
			{
				f0[i]+=cnt[j]*f0[i-j];
				f0[i]%=mod;
			}
		}
		f[0]=1;
		for(int i=1;i<=100;i++)
		{
			f[i]=f[i-1]+f0[i];
			f[i]%=mod;
		}
		if(x<=100)
		{
			printf("%lld",f[x]);
			return;
		}
		A.init();
		B.init();
		for(int i=1;i<=101;i++)
		{
			A.imap[1][i]=f[100-i+1];
		}
		for(int i=1;i<=100;i++)
		{
			B.imap[i][1]=cnt[i];
		}
		B.imap[101][1]=1;\/\/根节点没选，选上
		for(int i=1;i<=99;i++)
		{
			B.imap[i][i+1]=1;
		 } 
		B.imap[101][101]=1;
		out=A*ksm(B,x-100);
		printf("%lld",out.imap[1][1]);
	}
}
int main()
{
	Main::main();
	return 0;
}