題目鏈接：bzoj點我:-) 洛谷點我:-) 題目描述: 在C 部落，雙十字是非常重要的一個部落標志。所謂雙十字，由兩條水平的和一條豎直的”1“線段組成，要求滿足以下幾個限制： ·兩條水平的線段不能在相鄰的兩行。 ·豎直線段上端必須嚴格高于兩條水平線段，下端必須嚴格低于兩條水平線段。 ·豎直線段必須將兩條水平線段嚴格劃分成相等的兩半。 ·上方的水平線段必須嚴格短于下方的水平線段。 現在給定一個 R*C的01 矩陣，要求計算出這個 01 矩陣中有多少個雙十字。注意最終的結果可能很大，只要求輸出雙十字的個數 mod 1,000,000,009 的值

輸入格式： 第一行為用空格隔開的兩個正整數 R和C，分別表示01矩陣的行數和列數。輸入文件第二行是一個非負整數N,表示01矩陣中”0“的個數。接下來的N行，每行為用空格隔開的兩個正整數x和y(1<=x<=R,1<=y<=C)，表示(x,y)是一個”0“。數據保證N個”0“的坐標兩兩不同。數據保證R,C,N<=10,000,R*C<=1,000,000.(事實上R*C可能稍大于原設定)

輸出格式： D mod 1,000,000,009 的結果，其中D 為要求的 01矩陣中雙十字的個數。

思路： 首先因為R與C不確定，所以我們需要將點們放在一個一維數組中，算算編號就好了 接下來記錄lr[i]$lr[i]$與down[i]$down[i]$分別表示點i$i$最多可以向左右延伸和向下延伸多少個1(不包括自己)

然后我們枚舉雙十字的下面那個交點，推一推公式：

{注：len是下面橫線的長度，top表示能到達的最上的位置（連續的1），j是上面的橫線的中心位置} 對于一個點i$i$，它對答案的貢獻是： ∑lr[i]len=1min(lr[j],len?1)×down[i]×(j?top)$/sum_{len=1}^{lr[i]} min(lr[j], len-1)×down[i]×(j-top)$ 顯然這個min非常惡心，我們考慮把它拆開成下面的樣子： 1.當(lr[j] <= len-1) 貢獻是∑lr[i]len=1lr[j]×down[i]×(j?top)$/sum_{len=1}^{lr[i]} lr[j]×down[i]×(j-top)$ 2.當(lr[j] > len-1) 貢獻是∑lr[i]len=1(len?1)×down[i]×(j?top)$/sum_{len=1}^{lr[i]} (len-1)×down[i]×(j-top)$

再進一步變形： 1.當(lr[j] <= lr[i]) 貢獻是(lr[i]×lr[j]?lr[j]×(lr[j]+1)/2)×down[i]×(j?top)$(lr[i]×lr[j]-lr[j]×(lr[j]+1)/2)×down[i]×(j-top)$ 2.當(lr[j] > lr[i]) 貢獻是lr[i]×(lr[i]?1)/2×down[i]×(j?top)$lr[i]×(lr[i]-1)/2×down[i]×(j-top)$ （對于1的解釋:　lr[i]×lr[j]是總方案數，lr[j]×(lr[j]+1)/2是不合法方案數）

現在，需要解決的是所有帶j$j$的式子，我們定義3個樹狀數組t1, t2, t3，分別記錄: 1.?lr[j]?(lr[j]+1)/2)×(j?top)$-lr[j]*(lr[j]+1)/2)×(j-top)$ 2.lr[j]×(j?top)$lr[j]×(j-top)$ 3.(j?top)$(j-top)$ 把lr[i]作為位置插入，先枚舉列再枚舉行，每次注意清空。 并且因為兩根橫線不能挨在一起，所以枚舉點(i, j)插入(i-1, j)的值

感想： 啊我是湖南的為什么這么難qwq 這題我初一的時候抄了一遍題解，然后高一又抄了一遍題解。。 比較懷疑小時候到底看懂了沒。。 其實也不是特別難吧，還是可以想一想推一推的 下方程序中的top與解釋有一點點不一樣，是解釋的top-1

代碼：