TopCoder

餘切
$\Huge\text{freeh1}$

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

29.6% (8/27)

Tags

Description

  $\text{Aaw}$ 是一名高才生,作為橫掃全臺首學各項競賽、免修的戰神,他決定要挑戰沒有人會寫的地科免修。
$\text{OXO}$ 是一名享譽國際的地科名師,特色是他那回文的名字,而 $\text{Aaw}$ 為了判斷一名老師是不是 $\text{OXO}$,決定寫一個程式來判定一個名字是否為回文,你可以幫他寫出來嗎?

如果可以的話很棒,但 $\text{Aaw}$ 又不是白癡,作為臺北市科展以火車排點為題奪得特優晉級國展的戰神,他用腳都可以寫出 $\mathcal O(1)$ 判斷字串是否為回文的程式碼。但 $\text{Aaw}$ 不會野外考察,而 $\text{OXO}$ 又剛好出了一題地層位態的測量,$\text{Aaw}$ 覺得老師實在是太過份了,但老師對於 $\text{Aaw}$ 的指控只冷冷回了一句:「我覺得你說的對,但是我要補充一下,首先地層位態的測量得是利用傾斜儀,而慣性座標系並沒有任何科氏參數的作用,因此所有渾沌系統皆可用系集預報來做近似。其次自由落體是在 $2023$ 年,在成大天文被來自物理來的掉落常數超人給發明的,所以才有了後面著名的壓常數大賽,但是 $21\text{ cm}$ 譜線是紅的,因為 $Acxr$ 跟宇宙一樣是一臺紅機,而我認為疊置定律和行星引力場有關,而且「得」的師傅把向量外積丟到內積處理的話會讓更多國手破臺,另外原始水平定律的適用性只在地層為時間的非週期性函數時,這事也不能全靠 $QQ$,畢竟建國中學資訊社學術長借教室沒有把本來就在那的垃圾拿去丟不是成為虛幻可以解決的問題,需要用 $RMR$ 指數配合玻璃心一起推論出為何老師心碎滿地,月球半徑只要你站在上面就不會只有半角分,再少就不能產生恆星視差了!總的來說我個人還是比較喜歡月球內部結構的,當然也不介意去月海上面的頭盔裡面游泳會不會咬人,這個月球節理恐怕長的像一個面而不像是線,因為我在題目原始敘述看到區間資料結構進化的痕跡,而你卻在測量位態時候使用內建函式庫進行反三角函數運算!可是這份題目所問的,並不是兩個純量的乘積,所以你說《快速傅立葉轉換的地震波轉換》其實不是錯的,但是我只想說:「建中地科讀書會的教室在哪都可以被借來使用。」我作為一個野外考察超人得出了一個結論:你是會搞心態的資奧國手兼解出千禧年七大問題的數學家,且你會地科,從農夫留在教室的飲料可以判斷你絕對會地科。因為昨天的英文野外考察報告非常複雜,但其實真正導致這個問題的起源是大家的簡報大綱都一樣,我認為這個現象可能跟臉書發家教文案沒有人理會的現象有關係,因為隱沒帶倒轉地層導致傾角具有時變率,你能理解嗎?我最開始為什麼不認可你,因為 abyss 嗑夠多藥所以不會很現實。但是有一說一地科免修的優酪乳實作很正常,因為沒有喝就可以進入神的領域,而我旁邊的地層走向是不能用對的焦距觀察出來的,因此得出偃臥褶皺和地層倒轉後就可以計算地層年齡。你的考慮不是不可能的,但我只能說你的腦袋忘在鼻頭角的機率很低。總而言之這個和智商梯度有關,你可以試一試把內積換外積。你的分數要被扣完了,這並不影響大地水準面的博文反應序列。太現實的學生是十五平方加三立方的笨,因此下禮拜停借地科教室,我認為我的邏輯沒有問題因為根據 $\text{Stoke}$ 方程你的腦在水中會屬於懸浮載,而你的期末考成績可以得出我屬於可悲載,如果你不確定的話可以用 $\text{Hjulström}$ 曲線進行驗算。準確來說根據結合律資料結構定理的規定,十年之內稀疏表都不會產生區間極值。我先會地科,再會資訊,最後大勝你;地層位態真的只是一個時間的函數,只要有「?」時輸出夾角就好。你還違背了我都不會的英文因為最近學生上課發表讓我水課的簡報是超時的,你不在乎,你只在乎地科免修要拌 $42$ 號高嶺土。」

$\text{Aaw}$ 滿臉問號的拿起手上的傾斜儀,決定先量出兩個地層與水平面的高維法向量後計算他們的夾角,但 $\text{OXO}$ 是個煩人的老師,他不停在 $\text{Aaw}$ 量到一半時問他量好了沒,地層的傾角 $\theta$ 是多少,因此不耐煩的 $\text{Aaw}$ 決定先告訴 $\text{OXO}$ 他量到的 $\cos \theta$ 是多少,不過由於 $\text{Aaw}$ 是個有理的人,他會告訴 $\text{OXO}$ 的不是 $\cos \theta$,而是 $\cos ^ 2 \theta$!

在測量的過程中,$\text{Aaw}$ 會對傾斜儀進行微調,改變他目前兩個高維法向量的一些連續的維度。$\text{Aaw}$ 的腦袋動的很快,但你跟不上他的速度,所以你決定寫一個程式來看他有沒有算錯,同時告訴 $\text{OXO}$ 他在此刻量到的數值。

如果你對於 $\text{Aaw}$ 的向量空間使用什麼基底感到疑惑,那麼你問了一個很好的問題,$\text{Aaw}$ 平常使用的是正則基底(orthogonal basis),但因為 $\text{OXO}$ 很討厭地科讀書會正則人,所以僅限於這次的任務,$\text{Aaw}$ 使用了一種他自創的「負責基底」。負責基底基本上就是高中學過的向量操作常用的基底拓展到高維的情況,所以會有一些好用的性質,舉例來說若在 $n$ 維空間中有兩個向量 $\vec u = (u_1, u_2,...,u_n),\ \vec v=(v_1, v_2,...,v_n)$,則:

$$ |\vec u| = \sqrt{u_1 ^ 2+u_2 ^ 2+...+u_n ^ 2}\
\vec u \cdot \vec v=u_1v_1+ u_2v_2+...+ u_nv_n = |\vec u||\vec v|\cos \theta$$
等性質皆會成立。

Input Format

第一行會有一個整數 $n$,代表 $\text{Aaw}$ 現在測量的向量有多高維,而重力等位面的法向量 $g$ 和岩層的法向量 $s$ 一開始每個維度皆為 $0$。
接下來會有若干行(有幾行不會告訴你):
若一行為 g l r x 則代表 $\text{Aaw}$ 現在要修正重力等位面的法向量,$g_l \sim g_r$ 都要被增加 $x$。
若一行為 s l r x 則代表 $\text{Aaw}$ 現在要修正岩層面的法向量,$s_l \sim s_r$ 都要被增加 $x$。
若一行為 ? 則回答當前測量的 $\cos ^ 2 \theta$
由於數字可能很大,若答案為 $ \frac{p}{q} $ (不用約分,把你算的原始分子分母當成 $p, q$),請輸出 $p \times q\text{ mod } 10 ^ 9 + 7$。

Output Format

對於每個 ?,輸出一個整數 $p \times q\text{ mod } 10 ^ 9 + 7$

Sample Input 1

2
g 1 2 1
s 1 1 1
?

Sample Output 1

2

Hints

算出來不用約分,要取模你也約不出來

hint 1
測量地層時,不會有傾角超過 $90 ^ \circ$ 的情況發生;測量到的夾角 $\theta$ 一定要滿足 $0 ^ \circ \le \theta < 90 ^ \circ$,沒有的話不代表 $\text{Aaw}$ 量錯了,只是代表你要幫他換成正確的數值。

hint 2
可以假設所有測量的傾角皆有意義。

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536
16 1000 65536 65536
17 1000 65536 65536
18 1000 65536 65536
19 1000 65536 65536
20 1000 65536 65536
21 1000 65536 65536
22 1000 65536 65536
23 1000 65536 65536
24 1000 65536 65536
25 1000 65536 65536
26 1000 65536 65536
27 1000 65536 65536
28 1000 65536 65536
29 1000 65536 65536
30 1000 65536 65536
31 1000 65536 65536
32 1000 65536 65536
33 1000 65536 65536
34 1000 65536 65536
35 1000 65536 65536
36 1000 65536 65536
37 1000 65536 65536
38 1000 65536 65536
39 1000 65536 65536
40 1000 65536 65536
41 1000 65536 65536
42 1000 65536 65536
43 1000 65536 65536
44 1000 65536 65536
45 1000 65536 65536
46 1000 65536 65536
47 1000 65536 65536
48 1000 65536 65536
49 1000 65536 65536