A - Awkward

Time Limit: 3 sec / Memory Limit: 512 MB

配点 : 1000 点

問題文

ButCoder株式会社 は、プログラミングコンテストサイト「ButCoder」の開発や運営を主な事業とするスタートアップ企業です。

ButCoder社には社長を含めて N 人の社員が在籍し、社長以外の各社員は直属の上司を一人だけ持ちます。各社員には 1 から N までの重複しない社員番号が割り当てられており、社員番号 i の社員は社員 i と呼ばれます。社長は社員 1 であり、社員 i (2 ≤ i ≤ N) の直属の上司は社員 b_i (1 ≤ b_i < i) です。

ButCoder社員一同の集合写真を撮影するべく、全社員がButCoder本社の大広間に集まりました。この大広間はとても広く、N 人全員が横一列に並ぶことができます。しかし、彼らはどのような順番で並ぶかを決めかねています。どういうわけか、彼らは社長以外みな、自分の直属の上司と隣り合って並ぶことを避けたいようです。

N 人の社員の並び方であって、彼らの希望を満たすものは何通り存在するでしょうか？その個数を 10^9+7 で割ったあまりを求めてください。

制約

  • 2 ≤ N ≤ 2000
  • 1 ≤ b_i < i (2 ≤ i ≤ N)

入力

入力は以下の形式で標準入力から与えられる。

N
b_2
b_3
:
b_N

出力

N 人の社員の並び方であって、社長を除くどの社員も自分の直属の上司と隣り合わないようなものの個数を 10^9+7 で割ったあまりを出力せよ。

入力例 1

4
1
2
3

出力例 1

2

以下、社員 A が社員 B の直属の上司であることを A → B と表記します。

このケースでは、社員の主従関係は 1 → 2 → 3 → 4 となっています。以下の 2 通りの並び方が全社員の希望を満たします。

  • 2, 4, 1, 3
  • 3, 1, 4, 2

なお、後者は前者を左右に反転したものですが、これらは個別に数えます。

入力例 2

3
1
2

出力例 2

0

社員の主従関係は 1 → 2 → 3 となっています。3 人の社員がどのように並んでも、社員 2, 3 の希望のうち少なくとも一方に反するため、答えは 0 通りです。

入力例 3

5
1
1
3
3

出力例 3

8

社員の主従関係は次の図のようになっています。

以下の 8 通りの並び方が全社員の希望を満たします。

  • 1, 4, 5, 2, 3
  • 1, 5, 4, 2, 3
  • 3, 2, 4, 1, 5
  • 3, 2, 4, 5, 1
  • 3, 2, 5, 1, 4
  • 3, 2, 5, 4, 1
  • 4, 1, 5, 2, 3
  • 5, 1, 4, 2, 3

入力例 4

15
1
2
3
1
4
2
7
1
8
2
8
1
8
2

出力例 4

97193524

Score : 1000 points

Problem Statement

ButCoder Inc. is a startup company whose main business is the development and operation of the programming competition site "ButCoder".

There are N members of the company including the president, and each member except the president has exactly one direct boss. Each member has a unique ID number from 1 to N, and the member with the ID i is called Member i. The president is Member 1, and the direct boss of Member i (2 ≤ i ≤ N) is Member b_i (1 ≤ b_i < i).

All the members in ButCoder have gathered in the great hall in the main office to take a group photo. The hall is very large, and all N people can stand in one line. However, they have been unable to decide the order in which they stand. For some reason, all of them except the president want to avoid standing next to their direct bosses.

How many ways are there for them to stand in a line that satisfy their desires? Find the count modulo 10^9+7.

Constraints

  • 2 ≤ N ≤ 2000
  • 1 ≤ b_i < i (2 ≤ i ≤ N)

Input

Input is given from Standard Input in the following format:

N
b_2
b_3
:
b_N

Output

Print the number of ways for the N members to stand in a line, such that no member except the president is next to his/her direct boss, modulo 10^9+7.

Sample Input 1

4
1
2
3

Sample Output 1

2

Below, we will write A → B to denote the fact that Member A is the direct boss of Member B.

In this case, the hierarchy of the members is 1 → 2 → 3 → 4. There are two ways for them to stand in a line that satisfy their desires:

  • 2, 4, 1, 3
  • 3, 1, 4, 2

Note that the latter is the reverse of the former, but we count them individually.

Sample Input 2

3
1
2

Sample Output 2

0

The hierarchy of the members is 1 → 2 → 3. No matter what order they stand in, at least one of the desires of Member 2 and 3 is not satisfied, so the answer is 0.

Sample Input 3

5
1
1
3
3

Sample Output 3

8

The hierarchy of the members is shown below:

There are eight ways for them to stand in a line that satisfy their desires:

  • 1, 4, 5, 2, 3
  • 1, 5, 4, 2, 3
  • 3, 2, 4, 1, 5
  • 3, 2, 4, 5, 1
  • 3, 2, 5, 1, 4
  • 3, 2, 5, 4, 1
  • 4, 1, 5, 2, 3
  • 5, 1, 4, 2, 3

Sample Input 4

15
1
2
3
1
4
2
7
1
8
2
8
1
8
2

Sample Output 4

97193524
B - Increment and Swap

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1500 点

問題文

長さ N の数列 A があります。

この数列に対して、次の 2 種類の操作が可能です。

  • 隣り合う要素をswapする。

  • 好きな要素を 1 つ選んでその値を 1 増やす。

これらの操作を繰り返して数列 A を広義単調増加列にする時、最小で何回の操作が必要か求めてください。

制約

  • 1 ≤ N ≤ 200000
  • 1 ≤ A_i ≤ 10^9
  • A_i は整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1
A_2
:
A_N

出力

数列 A を広義単調増加列にするのに必要な操作の最小回数を出力せよ。

入力例 1

5
4
1
8
8
7

出力例 1

2

以下のように、2 回の操作で A を単調増加にできます。

  • A = \{4, 1, 8, 8, 7\} である。
  • 最初の 2 つの要素を swap すると、A = \{1, 4, 8, 8, 7\} となる。
  • 最後の要素を 1 増やすと、A = \{1, 4, 8, 8, 8\} となる。

入力例 2

20
8
2
9
7
4
6
7
9
7
4
7
4
4
3
6
2
3
4
4
9

出力例 2

62

Score : 1500 points

Problem Statement

We have a sequence A of length N.

On this sequence, we can perform the following two kinds of operations:

  • Swap two adjacent elements.

  • Select one element, and increment it by 1.

We will repeatedly perform these operations so that A will be a non-decreasing sequence. Find the minimum required number of operations.

Constraints

  • 1 ≤ N ≤ 200000
  • 1 ≤ A_i ≤ 10^9
  • A_i is an integer.

Input

Input is given from Standard Input in the following format:

N
A_1
A_2
:
A_N

Output

Print the minimum number of operations required to turn A into a non-decreasing sequence.

Sample Input 1

5
4
1
8
8
7

Sample Output 1

2

We can turn A into a non-decreasing sequence in two operations:

  • Initially, A = \{4, 1, 8, 8, 7\}.
  • Swap the first two elements. Now, A = \{1, 4, 8, 8, 7\}.
  • Increment the last element by 1. Now, A = \{1, 4, 8, 8, 8\}.

Sample Input 2

20
8
2
9
7
4
6
7
9
7
4
7
4
4
3
6
2
3
4
4
9

Sample Output 2

62