当前位置:网站首页>Educational Codeforces Round 107 (Rated for Div. 2) E. Colorings and Dominoes
Educational Codeforces Round 107 (Rated for Div. 2) E. Colorings and Dominoes
2022-07-05 05:27:00 【solemntee】
Our idea on this question is , Look at the picture horizontally and vertically .
Obviously, only one color needs to be considered horizontally and vertically .
The problem became 1*n Of all the o square value and .
We can dp Find out , Regard red and blue as 01 strand .
The length is i Of value and
Equal to the length of i-1 Of value and *2 Plus the length is i-1 Of 01 The end of the string is continuous 1 Is the number of odd strings .
And then it's fun ac 了
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
ll dp[300005];
char s[300005];
ll poww[300005];
vector<int>pos1[300005],pos2[300005];
int main()
{
ll ji=1,ou=1;
dp[1]=0;
poww[0]=1;
poww[1]=2;
for(int i=2;i<=300000;i++)poww[i]=poww[i-1]*2%mod;
for(int i=2;i<=300000;i++)
{
ll tj=ji,to=ou;
ou=(tj+to+tj)%mod;
ji=to;
dp[i]=(2*dp[i-1]+tj)%mod;
}
int n,m;
scanf("%d%d",&n,&m);
int cnt=0;
ll ans=0;
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
for(int j=1;j<=m;j++)
if(s[j]=='o')pos1[i].push_back(j),pos2[j].push_back(i),cnt++;
}
for(int i=1;i<=n;i++)
{
int temp=0,last=-1;
for(auto x:pos1[i])
{
if(x==last+1)temp++,last=x;
else
{
ans=(ans+poww[cnt-temp]*dp[temp])%mod;
temp=1,last=x;
}
}
if(temp)
{
ans=(ans+poww[cnt-temp]*dp[temp])%mod;
}
}
for(int i=1;i<=m;i++)
{
int temp=0,last=-1;
for(auto x:pos2[i])
{
if(x==last+1)temp++,last=x;
else
{
ans=(ans+poww[cnt-temp]*dp[temp])%mod;
temp=1,last=x;
}
}
if(temp)
{
ans=(ans+poww[cnt-temp]*dp[temp])%mod;
}
}
printf("%lld",ans);
return 0;
}
边栏推荐
- object serialization
- [to be continued] [UE4 notes] L3 import resources and project migration
- 搭建完数据库和网站后.打开app测试时候显示服务器正在维护.
- 浅谈JVM(面试常考)
- 剑指 Offer 53 - I. 在排序数组中查找数字 I
- sync.Mutex源码解读
- Summary of Haut OJ 2021 freshman week
- MySQL数据库(一)
- Support multi-mode polymorphic gbase 8C database continuous innovation and heavy upgrade
- [es practice] use the native realm security mode on es
猜你喜欢
随机推荐
[to be continued] [UE4 notes] L1 create and configure items
Binary search basis
远程升级怕截胡?详解FOTA安全升级
PMP candidates, please check the precautions for PMP examination in July
Palindrome (csp-s-2021-palin) solution
Demonstration of using Solon auth authentication framework (simpler authentication framework)
C语言杂谈1
剑指 Offer 09. 用两个栈实现队列
Insert sort
Remote upgrade afraid of cutting beard? Explain FOTA safety upgrade in detail
Introduction to memory layout of FVP and Juno platforms
Improvement of pointnet++
二十六、文件系统API(设备在应用间的共享;目录和文件API)
Haut OJ 1221: a tired day
[binary search] 69 Square root of X
[allocation problem] 455 Distribute cookies
[转]:Apache Felix Framework配置属性
Support multi-mode polymorphic gbase 8C database continuous innovation and heavy upgrade
Haut OJ 1352: string of choice
Solon Logging 插件的添加器级别控制和日志器的级别控制