#1262. [经开区 ] 相同字母(same.cpp)

[经开区 ] 相同字母(same.cpp)

时间限制:1000ms  空间限制:256MB

题目描述

给定两组由小写字母x和y构成的字符串,其长度都一样,为m。经过n次变换以后,成为两组新的字符串。请统计变换后的两组字符串有多少个对应位置是相同的。变换规则,x变成xx,y变成xy。

输入格式

共3行。第一行n和m;第二行为第一个字符串;第三行为第二个字符串。

输出格式

一行,一个整数,表示n次变换以后有多少个对应位置字母是相同的。

样例

输入#1

2 3
xyy
yxy

输出#1

10

解释#1

一共需要经过2次变换,字符串初始长度为3。第一次变换后分别是xxxyxy和xyxxxy;第二次变换后分别是xxxxxxxyxxxy和xxxyxxxxxxxy。第二次变换后的长度为12,一共有10个位置是相同的,因此,输出10。

数据范围/约定

60%的数据,1<=n<=20,1<=m<=10 100%的数据,1<=n<=30,1<=m<=1000