某島

… : "…アッカリ~ン . .. . " .. .
February 21, 2013

培養皿問題

這個模型最早見到是在 SRM 493 … 參見 hhanger 的題解。。。 ..

Brief description:

給一個 n*m 矩形,其中有些格子可以選,有些不能選。現在要求在可選的格子中選一些組成一個凸物,凸物要求所選的所有格子是相互聯通的,並且如果同一行/列選取了兩個格子的話,和它們在同一行/列,並且在它們之間的所有格子都需要被選。問一共有多少種不同的選法。(n, m <= 100)

Analysis:

我們需要好好研究下這個所謂凸物的性質。首先,它是個聯通體,然後,由於凸性,其每一行/每一列一定是連續的一段。想想一下這個圖形,它的每一行我們都可以用一個三元組來表示(r, a, b),表示第r行選取的是從第a列到第b列的所有元素。我們選取的一定是連續的一些行,我們考察這些行各自的a和b所組成的A和B序列的性質。

A數列是每一行最左邊元素的列坐標組成的數組,B則是最右邊元素的列坐標數組。為了保證每一列也是連續的一段,A數組必須是一個先非遞增,再非遞減的數組,而B數組也類似。根據這一點,一個唯一的凸物對應一對唯一的A和B數組。因此我們就可以來考慮dp解法來選取A和B數組了。dp[i][j][k][b1][b2]表示最後一行為第i行的,第i行選取第j到第k列的方法數(b1和b2用來表示A序列和B數列分別是否已經在非遞減/非遞增狀態)。對於第i行,一種情況是整個凸物只有第i行的元素,這個是很naive的情況;另外一種是除了第i行,還有前i-1行的一些元素,這樣我們就可以利用到dp[i-1][?][?][?][?]的值了。具體狀態轉移要根據後兩維的不同來分別處理。實際上,在求dp[i]時,我們需要求的都是某一段dp[i-1][j1 to j2][k1 to k2][?][?]所有元素的和,這是一個很經典的二維數組求子矩陣和問題,可以O(n^2)處理,之後O(1)計算。狀態轉移的時候還需要特別注意到,相等序列即符合非遞增又符合非遞減,所以A和B數組出現轉折點的情況一定是出現了一個嚴格遞增/嚴格遞減的狀態,這樣可以保證每個狀態被唯一表示,避免了重複計算。

dp[0/1][0/1][l][r]: 表示左右的增減狀態為 b1, b2 ,當前區間為 [l, r] 時的狀態。。
。。狀態的時候先從上一輪預處理二維部分和數組。。之後分四種情況討論即可。。。
Petr 的代碼通過調整轉移方向。。可以避免這步操作。。很優越。。)。。

。。實現的時候寫了一個 Int 整數類。。自帶取模。。
代碼盡量保持對稱可避免敲錯。。。。

//}/* .................................................................................................................................. */

const int N = 109;

struct Int{
    int val;

    operator int() const{return val;}

    Int(int val = 0):val(val){
        val %= MOD; if (val < 0) val += MOD;
    }
    inline Int& operator +=(const Int& rhs){
        INC(val, rhs);
        return *this;
    }
    inline Int operator +(const Int& rhs) const{
        return sum(val, rhs.val);
    }
    inline Int operator -(const Int& rhs) const{
        return dff(val, rhs);
    }
};

Int F[2][2][N][N], S[2][2][N][N]; bool A[N][N];
int n, m;

Int SS(int b1, int b2, int x1, int x2, int y1, int y2){
    return S[b1][b2][x2+1][y2+1] - S[b1][b2][x2+1][y1] - S[b1][b2][x1][y2+1] + S[b1][b2][x1][y1];
}

class AmoebaDivOne {
public:
	int count(vector <string> T) {

	    n = SZ(T), m = SZ(T[0]); REP_2(i, j, n, m){
	        int t = isdigit(T[i][j]) ? T[i][j] - '0' : T[i][j] - 'a' + 10;
            A[2*i][2*j] = t & 1, A[2*i][2*j+1] = t & 2;
            A[2*i+1][2*j] = t & 4, A[2*i+1][2*j+1] = t & 8;
	    }

	    n <<= 1, m <<= 1; RST(F); Int res; REP(i, n){

            RST(S); REP_4(b1, b2, l, r, 2, 2, m, m) S[b1][b2][l+1][r+1] = S[b1][b2][l][r+1] + S[b1][b2][l+1][r] - S[b1][b2][l][r] + F[b1][b2][l][r];

            RST(F); REP(l, m) FOR(r, l, m){

                if (A[i][r]) break;

                F[0][0][l][r] = SS(0, 0, l, r, l, r) + Int(1);
                F[0][1][l][r] = SS(0, 0, l, r, r+1, m-1) + SS(0, 1, l, r, r, m-1);
                F[1][0][l][r] = SS(0, 0, 0, l-1, l, r) + SS(1, 0, 0, l, l, r);
                F[1][1][l][r] = SS(0, 0, 0, l-1, r+1, m-1) + SS(0, 1, 0, l-1, r, m-1) + SS(1, 0, 0, l, r+1, m-1) + SS(1, 1, 0, l, r, m-1);

                REP_2(b1, b2, 2, 2) res += F[b1][b2][l][r];
            }
		}

		return res;
	}
};

補充:

Codeforces Round #167 DIV 1 D. Dima and Figure
數據範圍擴大。。但是沒有障礙。。
SGU 167. I-country.
最值問題。。需要列印方案。。