E. Colorings and Dominoes(思維,dp）

E. Colorings and Dominoes

題意：
n × m n\times m n×m的棋盤，有黑白兩種顏色的位置，我們能將白色的位置涂成紅色或藍色，
我們要把多米諾牌放在這些位置上，每兩個連續位置能放一個，水平放兩個位置，這兩個位置必須是紅色，垂直放兩個位置，這兩個位置必須是藍色的，
定義在對每個白色位置涂色后，能最多放的多米諾牌的數量為這種情況下的價值，
問在這 2 k 2^k 2k（k為白位置個數）種情況下價值總和是多少，對998244353 取模，

如何確定對行進行貢獻的統計和對列進行貢獻的統計不會產生影響，

：計算貢獻的最小單位是一行或一列，
我們求出某一行(列)的貢獻時會乘以 2 s u m ? c n t 2^{sum-cnt} 2sum?cnt代表剩下的 s u m ? c n t sum-cnt sum?cnt個o有多少種可能，在每種可能下這一行產生的貢獻始終不會改變，

d p dp dp狀態轉移方程
： d p [ i ] dp[i] dp[i]表示連續的i個o能產生多少貢獻，
舉例： o o o o oooo oooo，假設我們已知前3個 o o o的貢獻 d p [ 3 dp[3 dp[3]，我們假設第4個 o o o涂上藍色， d p [ 4 ] + = d p [ 3 ] dp[4]+=dp[3] dp[4]+=dp[3]，假設第4個涂上紅色，我們把這4個 o o o分成兩部分，左邊兩個 o o oo oo，右邊兩個 o o oo oo，

1. 右邊兩個 o o oo oo只有在都是紅色的時候才能產生貢獻，對 d p [ 4 dp[4 dp[4]產生的貢獻就是 2 2 2^2 22.
2. 左邊兩個 o o oo oo產生的貢獻：因為第3個 o o o可以涂兩種顏色，對 d p [ 4 dp[4 dp[4]產生的貢獻就是 2 ? d p [ 3 ] 2*dp[3] 2?dp[3]，

綜上： d p [ n ] = d p [ n ? 1 ] + 2 ? d p [ n ? 2 ] + 2 n ? 2 dp[n] = dp[n-1]+2*dp[n-2]+2^{n-2} dp[n]=dp[n?1]+2?dp[n?2]+2n?2;

\\ \\
參考代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+10;
const int mod = 998244353;
ll dp[N], f[N];
//dp[i]表示連續的i個o能產生多少貢獻，
string s[N];
ll qpow(ll x, ll y) {
    ll ans = 1;
    while(y) {
        if(y & 1) ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ans;
}
int main() {
#ifndef ONLINE_JUDGE 
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif  
    int n, m;
    cin >> n >> m;
    f[0] = 1, f[1] = 2;
    for(int i=0; i<n; i++) cin >> s[i];
    for(int i=2; i<N; i++) {
        dp[i] = ((dp[i-1] + 2ll*dp[i-2] % mod) % mod + f[i-2]) % mod;
        f[i] = f[i-1] * 2 % mod;
    }
    ll cnt = 0, ans1 = 0, ans2 = 0, sum = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(s[i][j] == 'o') sum++;
        }
    }
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(s[i][j] == 'o') cnt++;
            if(s[i][j] != 'o' || j == m-1) {
                if(cnt != 1) {
                    ans1 = (ans1 + dp[cnt]*f[sum-cnt]%mod) % mod;
                }
                cnt = 0;
            }
        }
    }
    cnt = 0;
    for(int j=0; j<m; j++) {
        for(int i=0; i<n; i++) {
            if(s[i][j] == 'o') cnt++;
            if(s[i][j] != 'o' || i == n-1) {
                if(cnt != 1) {
                    ans2 = (ans2 + dp[cnt]*f[sum-cnt]%mod) % mod;
                }
                cnt = 0;
            }
        }
    }
    cout << (ans1 + ans2) % mod << endl;
    return 0;
}