AtCoder Beginner Contest 071 D - Coloring Dominoes

时间:2022-03-08 14:44:44

Problem Statement

We have a board with a N grid. Snuke covered the board with N dominoes without overlaps. Here, a domino can cover a 1×2 or 2×1 square.

Then, Snuke decided to paint these dominoes using three colors: red, cyan and green. Two dominoes that are adjacent by side should be painted by different colors. Here, it is not always necessary to use all three colors.

Find the number of such ways to paint the dominoes, modulo 1000000007.

The arrangement of the dominoes is given to you as two strings S1 and S2 in the following manner:

  • Each domino is represented by a different English letter (lowercase or uppercase).
  • The j-th character in Si represents the domino that occupies the square at the i-th row from the top and j-th column from the left.

Constraints

  • 1≤N≤52
  • |S1|=|S2|=N
  • S1 and S2 consist of lowercase and uppercase English letters.
  • S1 and S2 represent a valid arrangement of dominoes.

Input

Input is given from Standard Input in the following format:

N
S1
S2

Output

Print the number of such ways to paint the dominoes, modulo 1000000007.


Sample Input 1

Copy
3
aab
ccb

Sample Output 1

Copy
6

There are six ways as shown below:

AtCoder Beginner Contest 071 D - Coloring Dominoes


Sample Input 2

Copy
1
Z
Z

Sample Output 2

Copy
3

Note that it is not always necessary to use all the colors.


Sample Input 3

Copy
52
RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn
RLLwwdWIxxNNQUUXXVVMMooBBaggDKqcimmeYrhAljOOTTJuuzzn

Sample Output 3

Copy
958681902

题解:
只有两行,简单题哈,就不多解释了.
定义F[i]为前i列的方案数
我们可以先压缩一下,s[i]=s[i+1]的缩成一个
可以开始讨论:
如果s1[i]==s2[i] & s1[i-1]==s2[i-1] F[i]=F[i-1]*2 i-1固定后,i有两种方案对应
s1[i]==s2[i] & s1[i-1]!= s2[i-1] F[i]=F[i-1] 表示i这个位置和i-1一一对应
s1[i]!= s2[i] & s1[i-1]==s2[i-1] F[i]=F[i-1]*2
s1[i]!= s2[i] & s1[i-1]!= s2[i-1] F[i]=F[i-1]*3 都不相同时有三种方案对应,可以手画下
 #include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=,mod=;
char s1[N],s2[N];long long f[N];
void work()
{
int l,n=;
scanf("%d",&l);
scanf("%s",s1+);
scanf("%s",s2+);
for(int i=;i<=l;i++){
if(s1[i]!=s1[i+]){
s1[++n]=s1[i];
s2[n]=s2[i];
}
}
if(s1[]==s2[])f[]=;
else f[]=;
for(int i=;i<=n;i++){
if(s1[i]==s2[i]){
if(s1[i-]!=s2[i-])f[i]+=f[i-];
else f[i]+=(f[i-]+f[i-])%mod;
}
else{
if(s1[i-]==s2[i-])f[i]+=(f[i-]+f[i-])%mod;
else f[i]+=(f[i-]*)%mod;
}
f[i]%=mod;
}
printf("%lld\n",f[n]);
} int main()
{
work();
return ;
}

 

AtCoder Beginner Contest 071 D - Coloring Dominoes的更多相关文章

  1. AtCoder Beginner Contest 071 ABCD

    1001 求个绝对值比较大小喽 1002 把字符串出现的字母记录一下,然后遍历a-z,谁第一个没出现就输出谁 1003 Problem Statement We have N sticks with ...

  2. AtCoder Beginner Contest 100 2018&sol;06&sol;16

    A - Happy Birthday! Time limit : 2sec / Memory limit : 1000MB Score: 100 points Problem Statement E8 ...

  3. AtCoder Beginner Contest 052

    没看到Beginner,然后就做啊做,发现A,B太简单了...然后想想做完算了..没想到C卡了一下,然后还是做出来了.D的话瞎想了一下,然后感觉也没问题.假装all kill.2333 AtCoder ...

  4. AtCoder Beginner Contest 053 ABCD题

    A - ABC/ARC Time limit : 2sec / Memory limit : 256MB Score : 100 points Problem Statement Smeke has ...

  5. AtCoder Beginner Contest 136

    AtCoder Beginner Contest 136 题目链接 A - +-x 直接取\(max\)即可. Code #include <bits/stdc++.h> using na ...

  6. AtCoder Beginner Contest 137 F

    AtCoder Beginner Contest 137 F 数论鬼题(虽然不算特别数论) 希望你在浏览这篇题解前已经知道了费马小定理 利用用费马小定理构造函数\(g(x)=(x-i)^{P-1}\) ...

  7. AtCoder Beginner Contest 076

    A - Rating Goal Time limit : 2sec / Memory limit : 256MB Score : 100 points Problem Statement Takaha ...

  8. AtCoder Beginner Contest 079 D - Wall【Warshall Floyd algorithm】

    AtCoder Beginner Contest 079 D - Wall Warshall Floyd 最短路....先枚举 k #include<iostream> #include& ...

  9. AtCoder Beginner Contest 064 D - Insertion

    AtCoder Beginner Contest 064 D - Insertion Problem Statement You are given a string S of length N co ...

随机推荐

  1. 文字处理TX Text Control X10独家揭秘(二):图像占位符合并

    在前面一篇文章<TX Text Control X10独家揭秘(一):数据源自动处理>中已经对即将发布的TX Text Control X10的数据源自动处理做了一些了解,接下来述说它的图 ...

  2. cocos2d-x3&period;x屏蔽遮罩层屏蔽触摸button

    cocos2d-x3.x触摸方法改变后,.屏蔽掉的层实际上触摸事件的非常easy,首先touchbegan一定要回true,第二,该事件被设定为听吞没触摸true.最近登录触摸水平必须低于0,现在,我 ...

  3. 第二章:shiro身份验证

    身份验证,即在应用中谁能证明他就是他本人.一般提供如他们的身份ID一些标识信息来表明他就是他本人,如提供身份证,用户名/密码来证明. 在shiro中,用户需要提供principals (身份)和cre ...

  4. hdu-2328(暴力枚举&plus;kmp)

    题意:给你n个字符串,问你这n个串的最长公共子串 解题思路:暴力枚举任意一个字符串的所有子串,然后暴力匹配,和hdu1238差不多的思路吧,这里用string解决的: 代码: #include< ...

  5. Linux&sol;Unix下的任务管理器-top命令

    Windows下的任务管理器虽然不好用(个人更喜欢Process Explorer些),但也算方便,可以方便的查看进程,CPU,内存...也可以很容易的结束进程 没有图形化界面下的Linux,也有命令 ...

  6. Spring框架中Bean管理的常用注解

    1. @Component:组件.(作用在类上)可以作用在任何一个类上 2. Spring中提供@Component的三个衍生注解:(功能目前来讲是一致的) * @Controller -- 作用在W ...

  7. SQL2008″Unable to read the list of previously registered servers on this system”

    打开SQL2008,弹出”Unable to read the list of previously registered servers on this system”错误, 微软官方的解决方法:h ...

  8. Android网络开发之HttpURLConnection

    http是一个可靠的传输,建立在TCP/IP连接之上,缺省端口是80,其他端口号也可以用.Android可以用HttpURLConnection或HttpClient接口来开发http程序. http ...

  9. webrtc--stun-turn

    .WebRTC后台服务: 通话的房间服务器(Room Server) 房间服务器是用来创建和管理通话会话的状态维护,是双方通话还是多方通话,加入与离开房间等等,我们暂时沿用Google部署在GAE平台 ...

  10. PAT乙级1091-1095

    1091 N-自守数 (15 分) 如果某个数 K 的平方乘以 N 以后,结果的末尾几位数等于 K,那么就称这个数为“N-自守数”.例如 3,而 2 的末尾两位正好是 9,所以 9 是一个 3-自守数 ...