voteplus
【問題描述】
R 君博客上有?個投票板塊,?家可以使?投票的?式來表達??對某些問題的贊成或反對的意見。
投票結果是公開的,但是 R 君會把這個結果化成?個最簡分數,如 1:2,4:3。
注意到同?個最簡分數可能代表了不同的總?數,如: 300 ?贊同, 600?反對與 1 ?贊同, 2 ?反對顯?的都是 1:2。
Neetenin 同學發現了這?點,但是 Neetenin 同學想猜出有多少?參加了投票,他使?的?法是先看結果,??投?票贊同后再看結果。
?如?個當前的投票結果是 1:2,但是 Neetenin 同學投了?票贊成后變成了 301:600, Neetenin 同學就知道?共有 300+600+1=901 ?參加了此次投票。
現在 Neetenin 同學把之前和之后的結果都告訴你,讓你算算?共有多少?參加了投票!
當然, Neetenin 可能也有看錯了的時候,所以當問題?解的時候請輸出”fake”(不含雙引號)。
【輸入格式】
??四個整數 a,b,c,d,表?前?次結果是 a:b,后?次結果是 c:d。
【輸出格式】
輸出?個整數或?個字符串”fake”(不含雙引號),表?參加投票的總?數,包含 Neetenin 同學。
【樣例輸入 1】
1 4 1 3
【樣例輸出 1】
16
【樣例輸入 2】
1 3 1 4
【樣例輸出 2】
fake
【數據規模及約定】
對于前 50% 的數據, 1 ≤ a; b; c; d ≤ 100000。
對于前 50% 的數據, 1 ≤ 答案 ≤ 100000。
對于前 100% 的數據, 1 ≤ a; b; c; d ≤ 10^9。
對于前 100% 的數據, 1 ≤ 答案 ≤ 10^9。
【題解】
設之前是x人投贊成,y人反對,那么不難列出\(\displaystyle\frac x y=\frac a b,\frac{x+1}y=\frac c d\)。
把這個方程組亂搞搞,就能得到\(\displaystyle x=\frac{ad}{bc-ad},y=\frac{bd}{bc-ad}\)。
判斷\(bc-ad>0\),并且ad和bd都能整除即可輸出,否則當然是fake了
fire
【問題描述】
森林著?了,?勢還在不斷蔓延。
R 君作為森林管理員,看到?勢失去控制、在森林中四處蔓延,??很慌。
經過 R 君平?仔細的研究,這個森林的?勢傳播可以看成?個 n 個節點的帶邊權的?向圖 (節點標號為 1-n),每個節點代表森林的?個區域,?條邊 (u,v,w) 代表著?勢從區域 u 傳播到區域 v 需要花費 w 的時間。并且整個森林是?個連通圖,?旦著?,沒有節點可以幸免。
通過?動化的 IoT 設備, R 君觀察到了 0 時刻有 k 處起?點,然后??就按照?勢傳播圖的規則蔓延開來。
不幸的是森林?有 q 個區域存在著居民,所以 R 君?常想知道?勢蔓延到這 q 個區域的時間從?展開營救?動。
然? R 君覺得這個問題太難了,于是找到了學 OI 的你。
【輸入格式】
第??四個整數 n, m, k, q,表?圖的點數、邊數、起?點數量、存在居民的區域數量。
接下來 m ?,每?三個正整數 u, v, w,表??條 u 到 v,邊權為 w 的?向邊。
接下來?? k 個正整數,表? 0 時刻 k 個起?點的節點編號。
接下來?? q 個正整數,表?詢問的 q 個居民區的節點編號。
【輸出格式】
輸出 q ?,每??個整數,表??勢蔓延到該點的時間。
【樣例輸入】
5 5 2 5
1 2 5
1 3 2
2 3 5
2 4 5
3 5 2
2 5
5 4 3 2 1
【樣例輸出】
0 5 2 0 4
【數據規模及約定】
對于前 10% 的數據, 1 ≤ n ≤ 100。
對于另外 20% 的數據,圖為?棵樹。
對于另外 20% 的數據, k=1。
對于另外 20% 的數據, q=1。
對于前 100% 的數據, 1 ≤ n; m ≤ 10000, 1 ≤ k; q; u; v ≤ n, 1 ≤ w ≤10000。
【題解】
建立一個炒雞src,向所有著火的點連邊權為0的邊跑最短路。實際操作的時候可以直接把所有著火的點的dis設為0并放到堆中跑dij。
matrix
【問題描述】
? Y ?分喜歡計數,?天他遇到了這樣的?個問題:
有?個 n ? m 列的矩陣,剛開始每個位置的數字都是 0。? Y ?先進? r 次這樣的操作,選擇?? (可與之前選擇重復) 把這??的每個數字+1。之后? Y 進? c 次這樣的操作,選擇?列 (可與之前選擇重復) 把這?列的每個數字 +1。
最后? Y 數了?下,矩陣?總共有 k 個位置的數字是奇數。
但是? Y 忘了之前是怎么操作的了,所以現在? Y 想知道有多少種操作?案能夠使得最后?共有 k 個位置的數字是奇數。
兩種操作?案不同當且僅當存在某?或某列進?操作的次數不同。
因為答案很?,所以只需輸出這個答案除以 109 + 7 的余數。
【輸入格式】
輸?包含??五個空格隔開的整數, n,m,r,c,k。
【輸出格式】
輸出包含?個整數,表?答案。
【樣例輸入】
2 2 2 2 4
【樣例輸出】
4
【數據規模和約定】
對于 20% 的數據, 1 ≤ n; m; r; c ≤ 4;
對于 50% 的數據, 1 ≤ n; m; r; c ≤ 2000;
對于 100% 的數據, 1 ≤ n; m; r; c ≤ 10^5; 0 ≤ k ≤ nm。
【題解】
很值得思考很有趣的一道題。
我們先假設矩陣操作后,有x行操作了奇數次,有y列操作了奇數次。
那么不難列出x(m-y)+y(n-x)=k,即mx+ny=k+2xy。我們可以枚舉x而推出y,從而得出所有合法的x和y。這里給出根據x求y的式子:\(\displaystyle y=\frac{k-mx}{n-2x}\),很容易推出來。
但是我們觀察到分母是\(n-2x\),如果\(n-2x=0\)那么怎么辦?
我們可以考慮,當\(n-2x=0\)時,相當于操作完所有的行后,恰好有一半的行是奇數,另一半的行是偶數。那么如果再操作列,奇數元素的數量是不改變的。。所以當2k=mn時,y可以取任意合法值,否則y無解。
注意到還有\(m-2y=0\)的情況,也要考慮一下。我們可以直接枚舉x求y枚舉y求x,把所有合法的(x,y)塞到一個set里不就得了。。。其實最完美的做法是只枚舉x,并判斷那種情況。但是這里再告訴你一個事實,其實那種情況只需要判斷是否有2k=mn即可,如果有,那么那種情況一定存在,且其他情況不存在。這個結論可以通過GeoGebra探索出來。
我們處理出所有合法的(x,y)后,就枚舉剛才處理的所有(x,y)并計算貢獻。顯然的是行和列的貢獻是獨立的,這里只考慮行的貢獻。首先我們一共有n行,最后有x行被操作奇數次,那么方案數為\(\mathrm{C}_{n}^x\)。我們先把這x次操作干完,然后剩下的就可以每兩個操作組成一對去操作同一行,操作完成之后那行還是偶數,一共有\(\displaystyle\frac {r-x}{2}\)個操作對。由于每一行可以操作多次,那么就是多重集的組合數:\(\mathrm{C}_{n+\frac{r-x}{2}-1}^{\frac{r-x}{2}}\)了。
所以最后一個(x,y)的貢獻為\(\mathrm{C}_{n}^x\times\mathrm{C}_{n+\frac{r-x}{2}-1}^{\frac{r-x}{2}}\times\mathrm{C}_{m}^y\times\mathrm{C}_{m+\frac{c-y}{2}-1}^{\frac{c-y}{2}}\)。答案為所有(x,y)的貢獻。
注意如果\(r-x\)或者\(c-y\)不是偶數,那么貢獻為0