有一棵n叉树，深度是无限的，每个结点有n个儿子。从左到右编号为1到n号儿子，第i号儿子离该结点的距离是di。现在要统计一下距离根结点不超过x的结点有多少个。
数字比较大对 109 + 7 取余后输出。
样例解释：
图中黄色的结点是距离根不超3的。
单组测试数据。 第一行有两个整数n和x (1≤n≤10^5,0≤x≤10^9)，表示每个结点的儿子数目，以及上文提到的x。 第二行有n个整数d1,d2,d3,…,dn (1≤di≤100)。
输出结果占一行。
样例输入1 3 3 1 2 3
样例输出1 8
暴力DP很好想，f[i]表示到根节点深度为i的有几个,f[i]=sigma(f[i-j]*cnt[j]),j=1->100
这样就可以用个矩阵来描述啦，意会一下
放上大佬NBC的代码就是上面的思路，对于边界的情况我不是很懂，如有大佬看懂请尽快发表。
#include <cstdio> #include<iostream> using namespace std; int I() { int r = 0, c; do c = getchar(); while (c < 48 || c > 57); do r = (r << 3) + r + r + (c - 48), c = getchar(); while (c > 47 && c < 58); return r; } const long long MOD = 1000000007; int N, X, cnt[101]; long long ans[101], bit[101][101]; void push() { static long long tmp[101]; for (int i = 0; i < 101; i++) { tmp[i] = 0; for (int j = 0; j < 101; j++) if ((tmp[i] += bit[i][j] * ans[j]) > 8223372024854775771LL) tmp[i] %= MOD; } for (int i = 0; i < 101; i++) ans[i] = tmp[i] % MOD; } void twice() { static long long tmp[101][101]; for (int i = 0; i < 100; i++) for (int j = 0; j < 100; j++) { tmp[i][j] = 0; for (int k = 0; k < 101; k++) if ((tmp[i][j] += bit[i][k] * bit[k][j]) > 8223372024854775771LL) tmp[i][j] %= MOD; } for (int i = 0; i < 101; i++) for (int j = 0; j < 101; j++) bit[i][j] = tmp[i][j] % MOD; } int main() { N = I(), X = I(); for (int i = 1; i <= N; i++) cnt[I()]++; ans[0] =ans[100] = 1; for (int i = 0; i < 99; i++) bit[i + 1][i] = 1; for (int i = 0; i < 100; i++) bit[0][i] = cnt[i + 1]; bit[0][100] = bit[100][100] = 1; for(int i=0;i<=50;i++) { for(int j=0;j<=50;j++) cout<<bit[i][j]<<‘ ‘; cout<<endl; } for (; X; X >>= 1) { if (X & 1) push(); twice(); } printf("%lld\n", ans[0]); return 0; }
原文：http://www.cnblogs.com/dancer16/p/7355396.html