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,
- 右边两个 o o oo oo只有在都是红色的时候才能产生贡献,对 d p [ 4 dp[4 dp[4]产生的贡献就是 2 2 2^2 22.
- 左边两个 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;
}