c618: 快冷靜下來啊我自己!
Tags :
Accepted rate : 6人/6人 ( 100% ) [非即時]
評分方式:
Strictly

最近更新 : 2018-05-26 05:45

Content

「不過沒想到……澪喝醉酒竟然會變成這樣——」我無奈地說道。

「…………喵☆咕嚕咕嚕咕嚕……世界在轉耶,好好玩歐……」

澪的臉頰磨蹭著我的後頸,大膽地向我撒嬌。

「平常那麼文靜,這反差就顯得更大了……四千,你還可以吧?」

「——當然,因為澪比想像中的還輕啊。」

這絕不是謊言,事實上澪真的很輕,所以要背她是完全沒問題的,但是……

「嗯,我完全不擔心這個啊,問題在於——」

「……喵,四千~?……喵☆」

抱緊!擠壓!磨蹭磨蹭!

「………………」

「——你的理性……或者該說男孩子的難言之隱?那方面沒問題嗎?」

老實說問題大得很……!

密著度本來就很高了,她又對我臉頰磨蹭,在我耳邊吐氣;而且最不妙的是……明明隔著衣服與內衣,我卻仍能夠清楚感受到觸碰到背上的那個感觸……!!

——嗚!背質數——因為有 $\color{black}{83}$ (澪的胸圍),太危險了,那麼……

「$\color{black}{3.14159265358979323846\ldots}$」

「啊~是圓周率,真是老套的方法呢!那麼四千,請問圓周率的符號是?」

——$\color{black}{\pi}$ (ぱい)

「呼哇啊啊!!」

——哼!我不可以輸!!

……依靠固定方法本來就是個錯誤,那麼……隨便什麼都好,找個難解的麻煩問題——有了!微甲期中考!!

「嗯,我想想……你現在大概想隨便找個比較難的問題吧?大概是微積分那一類」

——嗚!但,但是即使妳知道,也沒有任何妨礙手段……

「請問一下:設 $\color{black}{f: [a, b]\to\mathbb{R} \in \mathscr{C}^1}$ 是一個嚴格凸函數,則 $\color{black}{y=f(x)}$ 在 $\color{black}{(c, f(c))}$ 這點的切線會怎麼隨著 $\color{black}{c}$ 從 $\color{black}{a}$ 跑到 $\color{black}{b}$ 變動?」

——因為 $\color{black}{f}$ 是凸的,$\color{black}{y=f(x)}$ 始終在切線上方;另一方面,隨著 $\color{black}{c}$ 往右移,被擠到切點左邊的部分會越來越多……

「咕哇啊啊啊啊啊!!!」

不要再想到胸部了,快冷靜下來啊我自己!有沒有什麼方法……有了有了!給定一個 $\color{black}{1}$ 到 $\color{black}{n}$ 的排列 $\color{black}{p_1, p_2, \ldots, p_n}$,請問對於每個 $\color{black}{i \geq 2}$,$\color{black}{q_i := \min\{|p_i-p_j|: 1 \leq j \leq i-1\}}$ 分別是多少?

Input

本題的輸入有多筆測資,其中每筆測資佔兩行,請讀至檔案尾。
每筆測資的第一行有一個正整數 $\color{black}{n}$,代表四千找到了一個 $\color{black}{1}$ 到 $\color{black}{n}$ 的排列。第二行有三個正整數 $\color{black}{a, c, m}$,代表這個排列可以用下面這個函數生成:

void reisei(int *p, int n, unsigned int a, unsigned int c, unsigned int m){
    for(int i=1; i<=n; i++) p[i] = i;
    unsigned int x = 0;
    for(int i=1; i<=n-1; i++){
        x = ((unsigned long long)a*x+c)%m;
        int j = i + x%(n-i+1);
        int t = p[i]; p[i] = p[j]; p[j] = t;
    }
}
  • $\color{black}{2 \leq n \leq 10^7}$
  • $\color{black}{0 < a, c, m < 2^{32}}$
Output

你只要幫四千驗算就好了。對於每筆測資,輸出一個非負整數 $\color{black}{Q := (q_2+2)\oplus(q_3+3)\oplus\ldots\oplus(q_n+n)}$,其中 $\color{black}{\oplus}$ 為 bitwise-xor。

Sample Input
3
2 3 7
10
23 19 17
Sample Output
7
8
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (100%): 3.0s , <1K
Hint :
  1. 第一筆測資 $\color{black}{q = 1,1}$,故答案為 $\color{black}{3\oplus4=7}$。
    第二筆測資 $\color{black}{q = 4,1,1,2,2,1,1,1,1}$,故答案為 $\color{black}{6\oplus4\oplus5\oplus7\oplus8\oplus8\oplus9\oplus10\oplus11=8}$。
  2. 題敘改編自《前略。我與貓和天使同居》。
Tags:
出處:
[管理者:
xavier13540 (柊 四千)
]


ID User Problem Subject Hit Post Date
14032
xavier13540 (柊 四千)
c618
作者提供的解法
392 2018-06-02 23:54