2296 . 旅遊

Submit out of contest
Status
Discussion / Solution
Back to Problems List

Description

小 N 是一個喜好旅遊的人。他最近發現 NPSC 島十分適合旅遊，因此他決定規劃一個在 NPSC 島旅遊的行程。

經過詳細的調查之後，發現 NPSC 島總共有 $N$ 個主要的城鎮，由 $0$ 編號到 $N−1$，並且每個城鎮都有至少一條通往其它城鎮的單向道路，有些城鎮甚至會有超過一條通往同一個城鎮的道路。為了得到最佳的旅遊體驗，小 N 把從每個城鎮出發的所有道路都排好順序。小 N 計畫了 $T$ 天的行程，每天遊覽一個城鎮，並且要按照自己排的道路順序選擇隔天的要前往的城鎮。

具體來說，小 $N$ 在行程開始前會先用八個幸運數字 $A, B, C, D, E, F, a_0, a_1$ 產生一個數列 $a_0, a_1, \cdots, a_{T −1}$，其中對於所有 $i\geq 2$，$a_i=Aa_{i-1}^ 2+Ba_{i-1}a_{i-2}+Ca_{i-2}^ 2+Da_{i-1}+Ea_{i-2}+F$。接著，假設小 N 第 $i$ 天在編號 $x$ 的城鎮，且在小 $N$ 的排序之後由該城鎮出發的各個道路分別通往編號 $p_{x,0}, p_{x,1}, \cdots, p_{x,m_x−1}$ 的城鎮，那麼他隔天就會前往編號 $p_{x,q}$ 的城鎮，其中 $q$ 是 $a_i$ 除以 $m_x$ 的餘數。

然而因為小 N 的行程實在是太長了，而且他的數列中數字也都非常大，所以請你幫小 N 寫一個程式，方便他用自己排的道路順序和第 1 天所在的城鎮計算出這 $T$ 天分別會在哪個城鎮。

Input Format

本題沒有輸入，如果你輸入了任何東西，可能會導致各種不可預期的結果。

請#include "lib2296.h"之後實作下列函數：
void city_sequence(int N, int S, int T, int A, int B, int C, int D, int E, int F, int a0, int a1, const int m[], const int *const p[], int ans[]);

其中 S 為小 N 第 1 天所在的城鎮編號、m 陣列代表每個城鎮 $x$ 分別有幾條由該城鎮出發的道路（即題目中的 $m_x$）、p 陣列每個元素 p[x] 指向一個長度為 $m_x$ 的陣列，即由城鎮 $x$ 出發的每條道路通往的城鎮編號（題目中的 $p_{x,i}$）。
這個函數須將小 N 這 $T$ 天所在的城鎮編號依序填入 ans 陣列中，ans[0] 是第 1 天、ans[1] 是第 2 天，以此類推（因此 ans[0] == S）。

每次執行中，city_sequence 只會被呼叫一次。

對於所有測資：

  • $0\leq S<N\leq 3\times 10^ 4$
  • $1\leq T\leq 5\times 10^ 6$
  • $m_i\geq 1$
  • $m_0+m_1+\cdots+m_{N-1}\leq 10^ 5$。
  • $0\leq a_0,a_1,A,B,C,D,E,F\leq 10^ 5$

Output Format

本題沒有輸出，如果你輸出了任何東西，你將會獲得一個WA。

對於所有測資，若你的程式執行時間為時限的 $x$ 倍（$0\leq x\leq 1$），該筆測資的分數為 $A\times (p+qf(x))$，其中 $A$ 為該筆測資標示的分數，並給定常數 $a=0.5,b=0.15,p=1,q=2$，

\[f(x)=\left(s(x) \frac{(b x)^ a - b^ a}{(b x)^ a - 1.1x^ a}+\big(1-s(x)\big)\left(1-\frac{x^ 2}{2}\right)\right)\]

\[s(x)=\begin{cases}x, & x\in\{0,1\} \\ \frac{1}{1+\exp\left(\frac{8a}{b}\cot\left(\pi x^ {-\frac{\ln2}{0.1+\ln b}}\right)\right)}, & \text{otherwise}\end{cases}\]

你只需要知道 $f(0)=1,f(1)=0$，且 $f(x)$ 嚴格遞減就可以了。不過如果想要詳細了解這些函數在幹嘛的話，可以參考這個連結。

Sample Input 1

注意：本題沒有輸入，本輸入為提供測試標頭檔（參見Hints）使用。
4 0 9
1 0 0 0 0 0 1 2
3 1 3 2
1 0
2 0 0
1 0

Sample Output 1

注意：本題沒有輸出，本輸入為提供測試標頭檔（參見Hints）使用。
0
2
0
3
0
3
0
3
0

Hints

這裡有一個測試用的標頭檔，可以用來測試。
該標頭檔接受以下輸入，數字間皆以空白分隔：
第一行：$N,S,T$
第二行：$A,B,C,D,E,F,a_0,a_1$
接下來 $N$ 行：$m_x,p_{x,0},p_{x,1},\cdots,p_{x,m_x-1}$

程式將會輸出 $T$ 行，即是回傳的 ans 陣列的內容。

Problem Source

2020 NPSC 高中組決賽 pD / TIOJ 終極壓常數大賽 pE

Subtasks

No. Testdata Range Score
1 0 3
2 1 6
3 2 6
4 3 3
5 4 6
6 5 8
7 6 7
8 7 3
9 8 8
10 9 8
11 10 3
12 11 3
13 12 3
14 13 7
15 14 7
16 15 7
17 16 7
18 17 5

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 524288 65536 1
1 5000 524288 65536 2
2 5000 524288 65536 3
3 5000 524288 65536 4
4 5000 524288 65536 5
5 5000 524288 65536 6
6 5000 524288 65536 7
7 5000 524288 65536 8
8 5000 524288 65536 9
9 5000 524288 65536 10
10 5000 524288 65536 11
11 5000 524288 65536 12
12 5000 524288 65536 13
13 5000 524288 65536 14
14 5000 524288 65536 15
15 5000 524288 65536 16
16 5000 524288 65536 17
17 5000 524288 65536 18
Submit out of contest
Back to Top