codeforces 514E E. Darth Vader and Tree（矩阵应用）

codeforces 514E E. Darth Vader and Tree（矩阵应用）

​​http://codeforces.com/problemset/problem/514/E​​

大意：

给出一颗树，父节点到子节点有不同的路径，求解离根节点的距离不大于x的节点数（含根结点）

分析：设距离是i的结点个数是dp[i]，父节点到子节点距离是i的路径的条数是cnt[i]。 那么对于图中的转移矩阵就是：

推广转移矩阵，人为设定其规模是百行百列：

#include #include #include #include #include using namespace std;typedef long long LL;const int N=105,M=1e5+10,mod=1e9+7;LL d[M];LL cnt[N];LL dp[N];struct matrix{ LL m[N][N];}A,I;matrix multi(matrix a,matrix b){ matrix ans; for(int i=0;i>=1; } return ans;}int main(){ for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。