这题想了好长时间，果断没思路。。于是搜了一下题解。一看题解上的”快速幂”这俩字，，不对。。这仨字。。犹如醍醐灌顶啊。。。因为x的范围是10^9，所以当时想的时候果断把dp递推这一方法抛弃了。我怎么就没想到矩阵快速幂呢。。。。。。。还是太弱了。。sad。。100*100*100*log（10^9）的复杂度刚刚好。 于是，想到了矩阵快速幂后，一切就变得简单了。就可以把距离<=x的所有距离的点数都通过DP推出来，然后一个快速幂就解决了。 首先DP递推式很容易想到。递推代码如下：
++){<=i; j++) {dp[i]+=dp[i-j]*a[j];}}
dp[i]代表距离为i的点的个数。由于每段距离最大为100，也就是说下面的j的循环最多只有100次。那么就可以构造一个100*100的矩阵来实现这个递推过程。先处理出前100个dp值，然后套上矩阵快速幂就可以了。 代码如下：
using namespace std;const int mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;LL a[102], dp[102], sum[102];struct Matrix {LL ma[102][102];} init,res;Matrix Mult(Matrix x, Matrix y){Matrix tmp;for(int i=0; i<101; i++) {for(int j=0; j<101; j++) {tmp.ma[i][j]=0;for(int k=0; k<101; k++) {tmp.ma[i][j]+=x.ma[i][k]*y.ma[k][j];if(tmp.ma[i][j]>=mod) tmp.ma[i][j]%=mod;}}}return tmp;}Matrix Pow(Matrix x, int k){Matrix tmp;int i, j;for(i=0; i<101; i++) for(j=0; j<101; j++) tmp.ma[i][j]=(i==j);while(k) {if(k&1) tmp=Mult(tmp,x);x=Mult(x,x);k>>=1;}return tmp;}int main(){int n, x, i, j, y;while(scanf(“%d%d”,&n,&x)!=EOF) {memset(a,0,sizeof(a));memset(dp,0,sizeof(dp));for(i=0; i<n; i++) {scanf(“%d”,&y);a[y]++;}dp[0]=1;sum[0]=0;for(i=1; i<=100; i++) {for(j=1; j<=i; j++) {dp[i]+=dp[i-j]*a[j];if(dp[i]>=mod) dp[i]%=mod;}sum[i]=sum[i-1]+dp[i];if(sum[i]>=mod) sum[i]%=mod;}if(x<=100) {printf(“%I64d\n”,(sum[x]+1)%mod);continue ;}memset(init.ma,0,sizeof(init.ma));for(i=0; i<100; i++) {init.ma[0][i]=init.ma[100][i]=a[i+1];}for(i=1; i<100; i++) {init.ma[i][i-1]=1;}init.ma[100][100]=1;res=Pow(init,x-100);LL ans=(sum[100]*res.ma[100][100])%mod;for(i=1; i<=100; i++) {ans+=dp[i]*res.ma[100][100-i];if(ans>=mod) ans%=mod;}printf(“%I64d\n”,(ans+1)%mod);}return 0;}
也许不是自己该去发挥的地方，还是让自己到最适合自己战斗的方面去吧!勇敢的接受自己的失败，
