514 E(マトリックス高速べき乗＋DP)

1本の木で、各ノードにn人の息子がおり、このi番目の息子から親ノードまでの距離はd[i]であり、ルートノードからxを超えないノードが何個あるかを尋ねた結果、1 e 9+7を型取りした.
前に書いたのですが、どの大牛のブログを参考にしたのか忘れました.以下は彼の分析です.
 
まず各di<=100のデータは小さいことに着目し,すべてのnにおける分岐の長さiの個数をtiで表すとt[1~100],*ルートノードの長さiの点までの個数をdp[i]で表すと,状態遷移方程式*dp[x]=dp[x-1]*t[1]+dp[x-2]*t[2]+・・+dp[x-100]*t[100]*明らかにこの線形の状態遷移方程式に対して,dp[0~99]を予め処理して計算すれば後の値を繰り返すことができる*最後の結果はS[x]=dp[0]+dp[1]+...+dp[x]*従ってマトリクス転送を確立することができ、
 

#include<bits/stdc++.h>
using namespace std;
#define LL __int64
#define maxn 102
#define MOD 1000000007
struct Matrix
{
    LL a[maxn][maxn];
    Matrix()
    {
        memset(a,0,sizeof(a));
        for(int i=1;i<maxn;++i) a[i][i]=1;
    }
};
Matrix operator *(Matrix A,Matrix B)
{
    Matrix C;
    for(int i=1;i<maxn;++i)
        for(int j=1;j<maxn;++j)
        {
            C.a[i][j]=0;
            for(int k=1;k<maxn;++k)
                C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j]%MOD)%MOD;
        }
    return C;
}
Matrix pow(Matrix A,int n)
{
    Matrix res;
    while(n)
    {
        if(n&1) res=res*A;
        A=A*A;
        n>>=1;
    }
    return res;
}

LL t[maxn],dp[100005];
int main()
{
    int x,n,i,j;
    scanf("%d%d",&n,&x);
    memset(t,0,sizeof(t));
    for(i=1;i<=n;++i)
    {
        int tem;
        scanf("%d",&tem);
        ++t[tem];
    }
    memset(dp,0,sizeof(dp));
    LL s=1;
    dp[0]=1;
    for(i=1;i<=100;++i)
    {
        for(j=1;i-j>=0;++j)
            dp[i]=(dp[i]+dp[i-j]*t[j]%MOD)%MOD;
        if(i!=100) s=(s+dp[i])%MOD;
    }
    LL ans=0;
    if(x<=100)
        for(i=0;i<=x;++i) ans=(ans+dp[i])%MOD;
    else
    {
        Matrix A;
        memset(A.a,0,sizeof(A.a));
        for(i=1;i<=100;++i) {A.a[i][1]=t[i];A.a[i][101]=t[i];}
        A.a[i][1]=0,A.a[i][101]=1;
        for(i=1;i<=99;++i) A.a[i][i+1]=1;
        A=pow(A,x-99);
        for(i=1;i<=100;++i) ans=(ans+dp[100-i]*A.a[i][101])%MOD;
        ans=(ans+s*A.a[i][101])%MOD;
    }
    printf("%I64d
",ans);
    return 0;
}