F. Cowmpany Cowmpensation
首先一般dp推导
d
p
[
i
]
[
j
]
=
∏
u
∈
s
o
n
i
∑
k
=
1
j
d
p
[
v
]
[
k
]
dp[i][j] = \prod\limits_{u \in son_i} \sum\limits_{k = 1} ^{j} dp[v][k]
dp[i][j]=u∈soni∏k=1∑jdp[v][k]
这个是毫无疑问的，然后我们考虑如何得到
d
≥
n
d \geq n
d≥n的情况。
我们给定一个出了1号节点全是叶节点的情况，显然在根节点的统计也就是一个关于叶节点个数的多项式，当我们对根节点的情况统计求和的时候这个维度可能会升高，所以得到，在这种情况下最多就是n次多项式，
其他情况类比上面的情况，得到这是一个最多为n次的多项式，所以我们筛出前n + 1项来就能套上拉个朗日插值了，
d
f
s
dfs
dfs进行
d
p
dp
dp的复杂度是
O
(
n
2
)
O(n ^ 2)
O(n2)的加上
O
(
n
)
O(n)
O(n)拉格朗日插值，整体还是
O
(
n
2
)
O(n ^ 2)
O(n2)得。
代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const int inf
= 0x3f3f3f3f;
const double eps
= 1e-7;
const int N
= 3e3 + 10, mod
= 1e9 + 7;
int head
[N
], to
[N
], nex
[N
], cnt
= 1, n
, d
;
ll dp
[N
][N
], pre
[N
], suc
[N
], fac
[N
], inv
[N
];
ll
quick_pow(ll a
, int n
) {
ll ans
= 1;
while(n
) {
if(n
& 1) ans
= ans
* a
% mod
;
a
= a
* a
% mod
;
n
>>= 1;
}
return ans
;
}
void add(int x
, int y
) {
to
[cnt
] = y
;
nex
[cnt
] = head
[x
];
head
[x
] = cnt
++;
}
void dfs(int rt
, int fa
) {
for(int i
= 1; i
<= n
+ 1; i
++) dp
[rt
][i
] = 1;
for(int i
= head
[rt
]; i
; i
= nex
[i
]) {
if(to
[i
] == fa
) continue;
dfs(to
[i
], rt
);
for(int j
= 1; j
<= n
+ 1; j
++) {
dp
[rt
][j
] = (1ll * dp
[rt
][j
] * dp
[to
[i
]][j
]) % mod
;
}
}
for(int i
= 1; i
<= n
+ 1; i
++) dp
[rt
][i
] = (dp
[rt
][i
] + dp
[rt
][i
- 1]) % mod
;
}
ll
solve(int x
) {
if(x
<= n
+ 1) return dp
[1][x
];
n
++;
pre
[0] = suc
[n
+ 1] = fac
[0] = inv
[0] = 1;
for(int i
= 1; i
<= n
; i
++) {
pre
[i
] = 1ll * pre
[i
- 1] * (x
- i
) % mod
;
fac
[i
] = 1ll * fac
[i
- 1] * i
% mod
;
}
fac
[n
+ 1] = 1ll * fac
[n
] * (n
+ 1) % mod
;
inv
[n
+ 1] = quick_pow(fac
[n
+ 1], mod
- 2);
for(int i
= n
; i
>= 1; i
--) {
suc
[i
] = 1ll * suc
[i
+ 1] * (x
- i
) % mod
;
inv
[i
] = 1ll * inv
[i
+ 1] * (i
+ 1) % mod
;
}
ll ans
= 0;
for(int i
= 1; i
<= n
; i
++) {
ll a
= 1ll * pre
[i
- 1] * suc
[i
+ 1] % mod
* dp
[1][i
] % mod
;
ll b
= 1ll * inv
[i
- 1] * inv
[n
- i
] % mod
;
if((n
- i
) & 1) b
*= -1;
ans
= ((ans
+ a
* b
% mod
) % mod
+ mod
) % mod
;
}
return ans
;
}
int main() {
scanf("%d %d", &n
, &d
);
for(int i
= 2; i
<= n
; i
++) {
int x
; scanf("%d", &x
);
add(x
, i
);
}
dfs(1, 0);
printf("%lld\n", solve(d
));
return 0;
}
