2350 . Best Photo

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

0.0% (0/1)

Submission's AC Ratio

0.0% (0/2)

Tags

Description

We are going to take a photo of N students in a line. We want to take the best photo. A photo is considered to be the best when the maximum number of students are satisfied. A student is satisfied if he is the right neighbor of his best friend. Each student has only one best friend. You have to find the number of satisfied students in the best photo and the number of different best photos. Print these values modulo (109+7).

Input Format

The first line contains an integer T indicating the total number of test cases. Each test case begins with an integer N, the number of students.

The second line contains N integers denoting the array A where A[i] is the best friend of the ith student.

Constraints

  • T ≤ 16
  • 2 ≤ N ≤ 106
  • 1 ≤ A[i] ≤ N
  • A[i] ≠ i

    • Output Format

    Print two integers, the number of satisfied students in the best photo and the number of different best photos. Print these values modulo 1000000007.

    Sample Input 1

    1
3
2 3 1

    Sample Output 1

    2 3

    Hints

    Maximum two students can be satisfied. There are three possible arrangements of students that result in a photo with maximum number of satisfied students:
    1) 1 3 2
    2) 3 2 1
    3) 2 1 3

    Problem Source

    Migrated from old NTUJ.

    CounterCode 2015

    Subtasks

    No. Testdata Range Score

    Testdata and Limits

    No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
    0 4000 65536 131072
    Submit
    Back to Top