先考虑暴力的 DP，设 \(f_i\) 表示到根节点距离恰好为 \(i\) 的节点数量，则有
\[f_i=\sum_{j=1}^nf_{i-d_j} \]初值为 \(f_0=1\)，最终求的是 \(\sum\limits_{i=0}^x f_i\)。
注意到 \(d_i\le100\)，有很多相同的转移，于是记 \(cnt_i\) 表示 \(\left\{d\right\}\) 中 \(i\) 的出现次数，则有
\[f_i=\sum_{j=1}^{100} cnt_j\times f_{i-j} \]\(x\) 最大有 \(10^9\) 级别并且这个式子看着就能矩阵快速幂优化，于是设 \(sum_i\) 表示 \(f\) 的前缀和，将 \(f\) 的前 \(100\) 个元素暴力求出，然后构造一个 \(101\times101\) 的矩阵：
\[\begin{bmatrix} 1 & cnt_1 & cnt_2 & cnt_3 & cnt_4 & \cdots & cnt_{100}\\ 0 & cnt_1 & cnt_2 & cnt_3 & cnt_4 & \cdots & cnt_{100}\\ 0 & 1 & 0 & 0 & 0 & \cdots & 0\\ 0 & 0 & 1 & 0 & 0 & \cdots & 0\\ 0 & 0 & 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 0 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & \cdots & 0 & 0 & 0 & 1 & 0 \end{bmatrix}\times \begin{bmatrix} sum_{i-1}\\ f_{i-1}\\ f_{i-2}\\ f_{i-3}\\ f_{i-4}\\ f_{i-5}\\ \vdots\\ f_{i-100} \end{bmatrix}=\begin{bmatrix} sum_{i}\\ f_{i}\\ f_{i-1}\\ f_{i-2}\\ f_{i-3}\\ f_{i-4}\\ \vdots\\ f_{i-99} \end{bmatrix}\]然后矩阵快速幂优化即可。
时间复杂度 \(\mathcal O(100^3\log x)\)。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105, mod = 1e9 + 7;
int n, m;
int cnt[N];
int g[N], sum[N];
struct mat {
int a[N][N];
void clear() { memset(a, 0, sizeof a); }
void init() { clear(); for (int i = 0; i <= 100; ++i) a[i][i] = 1; }
mat operator * (const mat &x) const {
mat res; res.clear();
for (int i = 0; i <= 100; ++i)
for (int j = 0; j <= 100; ++j)
for (int k = 0; k <= 100; ++k)
res.a[i][j] = (res.a[i][j] + 1ll * a[i][k] * x.a[k][j] % mod) % mod;
return res;
}
} f, trans;
mat qpow(mat x, int y) {
mat res; res.init();
while (y) {
if (y & 1) res = res * x;
x = x * x;
y >>= 1;
}
return res;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1, x; i <= n; ++i) scanf("%d", &x), ++cnt[x];
g[0] = sum[0] = 1;
for (int i = 1; i < 100; ++i) {
for (int j = 1; j <= min(i, 100); ++j) g[i] = (g[i] + 1ll * g[i - j] * cnt[j] % mod) % mod;
sum[i] = (sum[i - 1] + g[i]) % mod;
}
if (m < 100) return printf("%d", sum[m]), 0;
trans.clear();
trans.a[0][0] = 1;
for (int i = 1; i <= 100; ++i) trans.a[0][i] = trans.a[1][i] = cnt[i];
for (int i = 2; i <= 100; ++i) trans.a[i][i - 1] = 1;
f.clear();
f.a[0][0] = sum[99];
for (int i = 1; i <= 100; ++i) f.a[i][0] = g[100 - i];
mat ans = qpow(trans, m - 99) * f;
printf("%d", ans.a[0][0]);
return 0;
}