AtCoder Beginner Contest 204 F Hanjo 2

H寬，W長(zhǎng)的二維平面上，用1 * 1或者2 * 1的地磚來(lái)鋪，要求鋪滿，求出方案數(shù)。
數(shù)據(jù)范圍H <= 6, W <= 1e12

看到W的范圍就可以想到是一個(gè)矩陣快速冪優(yōu)化的dp轉(zhuǎn)移，問(wèn)題的關(guān)鍵是如何寫出dp的方程以及矩陣的構(gòu)造。

這里題解的巧妙在于狀態(tài)的定義，因?yàn)椴缓锰幚? * 2的地磚橫著擺的情況，因?yàn)檫@會(huì)跨兩行，我開始以為會(huì)有2^12，也就是枚舉兩行的狀態(tài)。不過(guò)這里狀態(tài)的定義是當(dāng)前行的二進(jìn)制狀態(tài)壓縮，并且要保證前一行是已經(jīng)塞滿的情況。所以在構(gòu)造狀態(tài)轉(zhuǎn)移矩陣的時(shí)候，也就是從當(dāng)前的狀態(tài)$dp[i][S]$轉(zhuǎn)移到狀態(tài)$dp[i+1][T]$的時(shí)候，是要搜索找到當(dāng)前的狀態(tài)，也就是S，在加入一些1 * 1和1 * 2的地磚之后變?yōu)槿?的狀態(tài)，這時(shí)候所對(duì)應(yīng)的T就是$dp[i+1][T]$。

而轉(zhuǎn)移矩陣$tran[S][T]$則是從$dp[i][S]$到$dp[i+1][T]$轉(zhuǎn)移的方案數(shù)。構(gòu)造出轉(zhuǎn)移矩陣之后用快速冪來(lái)把M降到log級(jí)別。

dfs那塊在看了別人的題解之后照著寫的，莫名其妙的就過(guò)了。感覺這里比較巧妙，三個(gè)遞歸分別是對(duì)應(yīng)1 * 1,1 * 2橫著放和1 * 2豎著放的情況，并且是永遠(yuǎn)放在當(dāng)前狀態(tài)的最上面的空缺，這樣是為了避免方案數(shù)的重復(fù)統(tǒng)計(jì)，不過(guò)我還沒有完全消化完，先放在這里。

const int N = 6, mod = 998244353, M = (1 << 6) + 10; long long tran[M][M], ans[M][M], temp[M][M]; int n; long long m;void dfs(int from, int now, int to) {if (now == (1 << n) - 1)tran[from][to] ++;else{for (int i = 0; i < n; i ++){if(now & (1 << i))continue;dfs(from, now | (1 << i), to);if (i < n - 1 && !(now & (1 << i + 1)))dfs(from, now | (1 << i) | (1 << (i + 1)), to);dfs(from, now | (1 << i), to | (1 << i));break;}} }int main() {//freopen("in.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);int T = 1;//cin >> T;while (T --){cin >> n >> m;for (int i = 0; i < (1 << n); i ++){dfs(i, i, 0);ans[i][i] = 1;}while (m){if (m & 1){memset (temp, 0, sizeof (temp));for (int i = 0; i < (1 << n); i ++)for (int j = 0; j < (1 << n); j ++)for (int p = 0; p < (1 << n); p ++){temp[i][j] += ans[i][p] * tran[p][j];temp[i][j] %= mod;}for (int i = 0; i < (1 << n); i ++)for (int j = 0; j < (1 << n); j ++)ans[i][j] = temp[i][j];}memset (temp, 0, sizeof (temp));for (int i = 0; i < (1 << n); i ++)for (int j = 0; j < (1 << n); j ++)for (int p = 0; p < (1 << n); p ++){temp[i][j] += tran[i][p] * tran[p][j];temp[i][j] %= mod;}for (int i = 0; i < (1 << n); i ++)for (int j = 0; j < (1 << n); j ++)tran[i][j] = temp[i][j];m >>= 1;}cout << ans[0][0];}return 0; }

總結(jié)

以上是生活随笔為你收集整理的AtCoder Beginner Contest 204 F Hanjo 2的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。