题意翻译

有一个无限大的有根树，树上的每一个节点都有n个子节点 \(( 1 \leq n \leq 10^5 )\)，任意一个节点它的第\(i\)个子节点之间的距离为\(d_i( 1 \leq d_i \leq 10^9 )\)。

给出一个数\(x(0 \leq x \leq 10)\)，求有多少个节点到根节点的距离小于等于\(x\) ( 答案模\(1e9+7\) )。

题解

首先可以想到一个很简单的DP。
设\(dp[i]\)表示最远不超过\(i\)的个数，答案为\(dp[x]\)。
然而它肯定超时了，于是开始优化。
可以注意到，\(d_i \leq 100\)，所以不需要枚举\(1 \sim n\)，只需要统计\(1 \sim 100\)的个数就行了。
然而它还是超时了，于是继续优化。
这里采用矩阵乘法优化。
设$$sum_i=\sum_{j=1}^idp_j$$
\(t_i\)为\(i\)的个数。
构造如下矩阵\(:\)

\(\begin{bmatrix}sum_{i-1}\\dp_{i-1}\\dp_{i-2}\\dp_{i-3}\\dp_{i-4}\\\vdots\\dp_{i-100}\end{bmatrix}\times\begin{bmatrix}1&t_1&t_2&t_3&t_4&\cdots&t_{99}\\0&t_1&t_2&t_3&t_4&\cdots&t_{99}\\0&1&0&0&0&\cdots&0\\0&0&1&0&0&\cdots&0\\0&0&0&1&0&\cdots&0\\\vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\0&\cdots&0&0&0&1&0\end{bmatrix}=\begin{bmatrix}sum_{i}\\dp_{i}\\dp_{i-1}\\dp_{i-2}\\dp_{i-3}\\\vdots\\dp_{i-99}\end{bmatrix}?\)

然后直接转移就行了。

#include<bits/stdc++.h> 
#define ll long long
const int MM=150;
const long long mod=1e9+7;
long long t[105];
long long n,m;
struct node{
	ll M[MM][MM];
}a;
struct node2{
	ll M[MM];
}ans;
node operator *(node a,node b){//矩阵乘矩阵
	node ans;
	for(int i=1;i<=101;i++)
	for(int j=1;j<=101;j++) ans.M[i][j]=0;
	for(int i=1;i<=101;i++)
	for(int j=1;j<=101;j++)
	for(int k=1;k<=101;k++) ans.M[i][j]=(ans.M[i][j]+a.M[i][k]*b.M[k][j]%mod)%mod;
	return ans;
}
node2 operator *(node2 a,node b){//向量乘矩阵
	node2 ans;
	for(int i=1;i<=101;i++) ans.M[i]=0;
	for(int i=1;i<=101;i++)
	for(int k=1;k<=101;k++) ans.M[i]=(ans.M[i]+b.M[i][k]*a.M[k]%mod)%mod;
	return ans;
}

int main(){
	scanf("%lld %lld",&n,&m);
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		t[x]++;
	}
    a.M[1][1]=1;//初始矩阵 
	for(int i=2;i<=101;i++){
		a.M[1][i]=t[i-1];a.M[2][i]=t[i-1];
	}
	for(int i=3;i<=101;i++) a.M[i][i-1]=1;
	ans.M[1]=1;//答案矩阵 
	ans.M[2]=1;

	while(m>0) {//矩阵快速幂 
        if(m&1) ans=ans*a;
        a=a*a;
        m>>=1;
    }
	printf("%lld\n",ans.M[1]);
	return 0;
}

CF514E Darth Vader and Tree

原文：https://www.cnblogs.com/yzk-home/p/14249569.html