General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
86746688 Practice:
JKLover
995F - 17 C++17 (GCC 7-32) Accepted 327 ms 39508 KB 2020-07-13 15:25:29 2020-07-13 15:25:29
→ Source
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int P = 1e9 + 7;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
const int N = 3e3 + 10;
int n, D, inv[N];
int dp[N][N]; // dp[x][i] := subtree x, choose from [1, i]
vector<int> G[N];
void dfs(int x)
{
	for (int y : G[x])
		dfs(y);
	for (int i = 1; i <= n + 1; ++i)
	{
		int prod = 1;
		for (int y : G[x])
			prod = mul(prod, dp[y][i]);
		dp[x][i] = add(dp[x][i - 1], prod);
	}
}
int main()
{
	n = read(), D = read();
	inv[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		inv[i] = mul(P - P / i, inv[P % i]);
		G[read()].push_back(i);
	}
	dfs(1);
	int ans = 0;
	for (int i = 1; i <= n + 1; ++i)
	{
		int tmp = dp[1][i];
		for (int j = 1; j <= n + 1; ++j)
			if (i != j)
			{
				tmp = mul(tmp, add(P, D - j));
				if (i > j)
					tmp = mul(tmp, inv[i - j]);
				else
					tmp = mul(tmp, P - inv[j - i]);
			}
		inc(ans, tmp);
	}
	cout << ans << '\n';
	return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details