設\(g[i,j]\)表示底邊長爲\(i\)底部恰好囿\(j\)行全部安全，沒有面積大於\(k\)的子矩陣（下稱：合法）的概率\(s[i,*]\)為\(g[i,*]\)的前綴和，意義為最下面至少有\(j\)行全部安全的合法概率

我們枚舉第一個在第\(i+1\)行的危險點來轉移\(g\)和\(s\)，設這個危險點在第\(k+1\)列那麽左邊\(k\)列的底部就至少有\(j+1\)行是全安全的，而右邊至少有\(j\)行（不重複計數）是然後塖上第\(k+1\)列上的相關概率得到：

k?\)的狀態一定是不合法的，基於這樣的邊界的處理複雜度就不是\(n^3?\)了

定義\(f[i]?\)表示底邊長爲\(i?\)的泳池的合法概率。若第\(i?\)列底部的格子不安全則

這題滿巧妙地把二維上的問題通過預處理變爲一個一維的綫性遞推問題，主要是可以抓住“所判別的矩陣的底部一定是靠在泳池的底部”這一要求；另外邏輯關係上\(s\)應該在\(g\)之前，就是説我們使用差分的方式來處理\(s\)這種”至少“嘚問題，這也是個常見的套路:D

暴力算\(f[0\to K]\)時不要拿\(a\)進去呀而且此時的轉移一個純的\(s[i,1]\)，即沒有任何危險點的情況 TAT