回分類題庫
c049: 6.排隊
關鍵字: 108校內初賽

測資點 : 10 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 183 Times / 157 Users | Submit : 609 Times / 205 Users | Accepted rate : 77%
題目加入時間 : 2019-08-10 01:25

Content: 简体中文

原本有 N 個編號為 1 到 N 號的人排成一列,因為一場大地震大家四處去避難,地震結束之後又重新回來排隊,這時候排隊的順序已經不是原本從 1 到 N 的順序,而是依照回來之後的順序來排隊。

為了怕再次地震導致隊伍又重新排過,所以主辦單位請每個人記下自己前、後一位的編號,並將這個資料傳給附近的工作人員。由於每個人都不知道自己是第幾位,身為主辦單位的你,可否依照每個人前後一位的編號而還原出整個隊伍的排列。

Input:

輸入資料第一行有一個正整數 N (1<=N<=200000),代表這個隊伍總共有多少人(編號從 1 到 N)。

接下來有 N-1 行資料,每行有兩個正整數 A、B,代表A號排在B號的前面。

Output:

由於隊伍非常的長,所以要全部印完資料也會非常的長,因此只要輸出最後一位的H值即可。這邊H值的計算方式如下:

  1. 第一位的H值為他自己的編號除以997的餘數,即 H1=K1%997,其中 K1 是第一位的編號。
  2. 第二位以後的H值為前一位的H值乘上7倍加上自己的編號,最後再取除以997的餘數,即 Hi=(Hi-1*7+Ki)%997
以下面的範例1來說,隊伍的順序是1 2,H1=1%997=1,H2=(1*7+2)%997=9,故答案為9。
而下面的範例2,隊伍的順序是3 2 1,H1=3%997=3,H2=(3*7+2)%997=23,H3=(23*7+1)%997=162,故答案為162。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
輸入1:
2
1 2

輸入2:
3
3 2
2 1

Sample Output :

輸出1:
9

輸出2:
162

Hint :

Author :

108校內初賽 (管理員:sagit)

  Solve it!   Status Forum