题目链接:E. Colorings and Dominoes
思路:我们先考虑一种最简单的情况:oooooo,我们用1代表红色,0代表蓝色,我们先计算他对于5个o的情况来说,多增加了几个,因为一个多米诺骨牌占2格,所以形如000011这种情况,这在他的上一种情况(00001)中是显然多增加了1,那么我们就看究竟有多少种这样的情况,先上图片帮助理解:
答案很显然,应该是\(2^{k-3}+2^{k-5}+...\)直到加到0次方为止,不过还有一点细节需要注意的就是依据上图这种方式进行计算,当数量为偶数时,总情况数需要额外再+1,当数量为奇数时,需要先减掉偶数对其的影响,这是因为111111这个对于他的上一种情况(11111)来说多增加了1种,而1111111却不会,注意我们到目前为止所说的所有情况都是对于上一种情况的增量,得到增量后我们可以很轻松的算出来总的情况。然后我们发现式子\(2^{k-3}+2^{k-5}+...\)是可以由上一项得到的,进而该式也能写成递推式。最后需要注意的一点是我们只计算了一条链上的ans,如果要计算该链对于总情况数的贡献,我们必须将该链的ans*\(2^{除该链之外o的个数}\),这样才是该链对于总的贡献值。
\(Code:\)
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int N = 3e5+10;
const ll mod = 998244353;
ll f[N],a[N],c[N];
void iniv(){
f[0] = 1;
rep(i,1,N-4)f[i] = f[i-1]*2,f[i]%=mod;
a[3] = 1;
int d = 5;
c[3] = 3;c[2] = 1;
rep(i,4,N-4){
if(i%2==1){
a[i] = (a[i-1]-1)*2+1;
}
else {
a[i] = a[i-1]*2+1;
}
a[i] %= mod;
c[i] = (c[i-1]*2)%mod + a[i]%mod;
c[i] %= mod;
}
}
int n,m;
string str[N];
void solve(){
ll ans = 0ll;
iniv();
read(n);read(m);
rep(i,1,n){
cin>>str[i];
}
int num = 0;
rep(i,1,n){
for(auto p:str[i])if(p == 'o')num++;
}
rep(j,1,n)
rep(i,0,m-1){
int cnt = 0;
ll sum = 0ll;
while(i<m and str[j][i] == 'o')cnt++,i++;
(sum = c[cnt])%=mod;
(sum *= f[num - cnt])%=mod;
(ans += sum)%=mod;
}
rep(i,0,m-1){
rep(j,1,n){
int cnt = 0;
ll sum = 0ll;
while(j<=n and str[j][i] == 'o')cnt++,j++;
sum = c[cnt];
(sum *= f[num-cnt])%=mod;
(ans += sum)%=mod;
}
}
write(ans%mod);pc('\n');
}
signed main()
{
solve();
return 0;
}