Codeforces 514E Darth Vader and Tree【Dp+矩阵快速幂优化】

题目大意：

有一棵树，最开始就一个根节点，每个节点都有N个儿子，这个节点距离每个儿子的距离为di（1<=di<=100），问你距离根节点距离小于等于X的节点个数有多少个。

思路：

1、如果对于统计个数，我们考虑dp，设定dp【i】表示距离根节点距离为i的节点个数。

那么不难推出状态转移方程：dp【i】=Σdp【i-j】*len【j】；

2、显而易见，直接dp是会超时的，考虑优化，既然我们有了递推式，那么我们不妨介入矩阵优化。

然后矩阵快速幂就能够做到O（LogX）的时间复杂度。

3、既然有了dp递推式，那么矩阵的构造也就不难了：

①因为最大长度di==100，那么我们不妨将矩阵构造为101*101的大小，最后一行用来转移sum.因为我们要求的是Σdp【i】（0<=i<=X），而不是dp【X】；

②那么接下来预处理出dp【0~100】；

③那么有：

③对应求Sum【X】的时候，将第二个矩阵按照幂次增加即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int MOD=1e9+7;
#define LL __int64
struct Matrix
{
    int a[105][105];	//
    int n,m;
    Matrix(int _n=0,int _m=0,LL val=0)
    {
        n=_n; m=_m;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                a[i][j]=(i==j?val:0);
    }
    void print()
    {
        for(int i=0;i<n;i++,puts(""))
            for(int j=0;j<m;j++)
                cout<<a[i][j]<<' ';
        puts("");
    }
    Matrix operator *(Matrix tmp)
    {
        Matrix ret(n,tmp.m);
        for(int i=0;i<n;i++)
            for(int j=0;j<tmp.m;j++)
                for(int k=0;k<m;k++)
                    ret.a[i][j]=((LL)ret.a[i][j]+(LL)a[i][k]*tmp.a[k][j])%MOD;	//
        return ret;
    }
    Matrix operator ^(LL b)
    {
        Matrix ret(n,m,1),base=(*this);
        while(b)
        {
            if(b&1) ret=ret*base;
            b>>=1;
            base=base*base;
        }
        return ret;
    }
};
int tab[105];
LL dp[105];
int main(){
	int n,x;
	scanf("%d%d",&n,&x);
	int d;
	Matrix m0=Matrix(1,101);
	Matrix p=Matrix(101,101);
	for(int i=0;i<n;++i){
		scanf("%d",&d);
		++tab[d];
		++p.a[100-d][99];
		++p.a[100-d][100];
	}
	dp[0]=1;
	LL sum=1;
	for(int i=1;i<=100;++i){
		for(int j=1;j<=i;++j){
			dp[i]=(dp[i]+dp[i-j]*tab[j])%MOD;
		}
		sum=(sum+dp[i])%MOD;
		m0.a[0][i-1]=dp[i];
	}
	m0.a[0][100]=sum;
	//m0.print();
	for(int i=1;i<100;++i)
		p.a[i][i-1]=1;
	p.a[100][100]=1;
	LL ans=1;
	if(x<100){
		for(int i=0;i<x;++i)
			ans=(ans+m0.a[0][i])%MOD;
		printf("%I64d\n",ans);
	}
	else if(x==100) printf("%d\n",m0.a[0][100]);
	else{
		p=p^((x-100));
		m0=m0*p;
		printf("%d\n",m0.a[0][100]);
	}
	return 0;
}