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