1836 問(wèn)題 E: 藍(lán)橋杯2016年第七屆真題-圓圈舞
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 119 解決: 79
題目描述
春天溫暖的陽(yáng)光照耀著大地，正是草原上的小動(dòng)物們最快樂(lè)的時(shí)候。小動(dòng)物們?cè)诓菰祥_(kāi)了一個(gè)舞會(huì)，歡度這美好的時(shí)光。
舞會(huì)上最重要的一個(gè)環(huán)節(jié)就是跳圓舞曲，n只小動(dòng)物手拉手圍成一大圈，隨著音樂(lè)跳起來(lái)。在跳的過(guò)程中，小動(dòng)物們可能會(huì)變換隊(duì)形。它們的變換方式是動(dòng)物A松開(kāi)自己右手，動(dòng)物B松開(kāi)自己的左手，動(dòng)物A和B手拉到一起，而它們對(duì)應(yīng)的松開(kāi)的手（如果有的話）也拉到一起。
例如，假設(shè)有10只小動(dòng)物，按順序圍成一圈，動(dòng)物1的右手拉著動(dòng)物2的左手，動(dòng)物2的右手拉著動(dòng)物3的左手，依次類推，最后動(dòng)物10的右手拉著動(dòng)物1的左手。如果通過(guò)動(dòng)物2和8變換隊(duì)形，則動(dòng)物2的右手拉著動(dòng)物8的左手，而對(duì)應(yīng)的動(dòng)物3的左手拉著動(dòng)物7的右手，這樣形成了1-2-8-9-10和3-4-5-6-7兩個(gè)圈。如果此時(shí)通過(guò)動(dòng)物2和6變換隊(duì)形，則將形成1-2-6-7-3-4-5-8-9-10一個(gè)大圈。注意，如果此時(shí)通過(guò)動(dòng)物1和2變換隊(duì)形，那么隊(duì)形不會(huì)改變，因?yàn)閯?dòng)物1的右手和動(dòng)物2的左手松開(kāi)后又拉到一起了。
在跳舞的過(guò)程中，每個(gè)動(dòng)物i都有一個(gè)歡樂(lè)值Hi和一個(gè)感動(dòng)值Fi。
如果兩個(gè)動(dòng)物在一個(gè)圈中，歡樂(lè)值會(huì)彼此影響，產(chǎn)生歡樂(lè)能量。如果兩個(gè)動(dòng)物i, j（i≠j）在同一個(gè)大小為t的圈中，而動(dòng)物i在動(dòng)物j右手的第p個(gè)位置（動(dòng)物j右手的第1個(gè)位置就是動(dòng)物j右手所拉著的動(dòng)物，而第2個(gè)位置就是右手第1個(gè)位置的動(dòng)物右手拉著的動(dòng)物，依次類推），則產(chǎn)生的歡樂(lè)能量為(t-p)*Hj*Fi。在跳舞的過(guò)程中，動(dòng)物們的歡樂(lè)值和感動(dòng)值有可能發(fā)生變化。
圓舞曲開(kāi)始的時(shí)候，所有的動(dòng)物按編號(hào)順序圍成一個(gè)圈，動(dòng)物n右手的第i個(gè)位置正好是動(dòng)物i?，F(xiàn)在已知小動(dòng)物們變換隊(duì)形的過(guò)程和歡樂(lè)值、感動(dòng)值變化的過(guò)程，求每次變換后所有動(dòng)物所產(chǎn)生的歡迎能量之和。
輸入
輸入的第一行包含一個(gè)整數(shù)n，表示動(dòng)物的數(shù)量。
接下來(lái)n行，每行兩個(gè)用空格分隔的整數(shù)Hi, Fi，按編號(hào)順序給出每只動(dòng)物的歡樂(lè)值和感動(dòng)值。
接下來(lái)一行包含一個(gè)整數(shù)m，表示隊(duì)形、歡樂(lè)值、感動(dòng)值的變化次數(shù)。
接下來(lái)m行，每行三個(gè)用空格分隔的整數(shù)k, p, q，當(dāng)k=1時(shí)，表示小動(dòng)物們通過(guò)動(dòng)物p和動(dòng)物q變換了隊(duì)形，當(dāng)k=2時(shí)，表示動(dòng)物p的歡樂(lè)值變?yōu)閝，當(dāng)k=3時(shí)，表示動(dòng)物p的感動(dòng)值變?yōu)榱藂。
輸出
輸出m行，每行一個(gè)整數(shù)，表示每次變化后所有動(dòng)物產(chǎn)生的能量之和。
答案可能很大，你需要計(jì)算答案除以1000000007的余數(shù)。
樣例輸入
10
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
9
1 2 8
1 2 6
2 8 10
3 5 10
1 1 2
1 2 1
2 5 5
1 4 8
1 4 5
樣例輸出
100
450
855
1341
1341
811
923
338
923
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情