本文主要是介绍cf Educational Codeforces Round 106 E. Chaotic Merge,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
原题:
E. Chaotic Merge
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given two strings x and y, both consist only of lowercase Latin letters. Let |s| be the length of string s.
Let’s call a sequence a a merging sequence if it consists of exactly |x| zeros and exactly |y| ones in some order.
A merge z is produced from a sequence a by the following rules:
if ai=0, then remove a letter from the beginning of x and append it to the end of z;
if ai=1, then remove a letter from the beginning of y and append it to the end of z.
Two merging sequences a and b are different if there is some position i such that ai≠bi.
Let’s call a string z chaotic if for all i from 2 to |z| z i ≠ z i − 1 z_i ≠ z_{i-1} zi=zi−1.
Let s[l,r] for some 1 ≤ l ≤ r ≤ ∣ s ∣ 1≤l≤r≤|s| 1≤l≤r≤∣s∣ be a substring of consecutive letters of s, starting from position l and ending at position r inclusive.
Let f ( l 1 , r 1 , l 2 , r 2 ) f(l1,r1,l2,r2) f(l1,r1,l2,r2) be the number of different merging sequences of x [ l 1 , r 1 ] x[l1,r1] x[l1,r1] and y [ l 2 , r 2 ] y[l2,r2] y[l2,r2] that produce chaotic merges. Note that only non-empty substrings of x and y are considered.
Calculate ∑ f ( l 1 , r 1 , l 2 , r 2 ) \sum f(l1,r1,l2,r2) ∑f(l1,r1,l2,r2),其中 1 ≤ l 1 ≤ r 1 ≤ ∣ x ∣ a n d 1 ≤ l 2 ≤ r 2 ≤ ∣ y ∣ 1≤l_1≤r_1≤|x| and 1≤l_2≤r_2≤|y| 1≤l1≤r1≤∣x∣and1≤l2≤r2≤∣y∣ Output the answer modulo 998244353.
Input
The first line contains a string x(1≤|x|≤1000).
The second line contains a string y (1≤|y|≤1000).
Both strings consist only of lowercase Latin letters.
Output
Print a single integer — the sum of f(l1,r1,l2,r2) over 1≤l1≤r1≤|x| and 1≤l2≤r2≤|y| modulo 998244353
.
Examples
Input
Copy
aaa
bb
Output
Copy
24
Input
Copy
code
forces
Output
Copy
1574
Input
Copy
aaaaa
aaa
Output
Copy
0
Input
Copy
justamassivetesttocheck
howwellyouhandlemodulooperations
Output
Copy
667387032
Note
In the first example there are:
6
pairs of substrings “a” and “b”, each with valid merging sequences “01” and “10”;
3
pairs of substrings “a” and “bb”, each with a valid merging sequence “101”;
4
pairs of substrings “aa” and “b”, each with a valid merging sequence “010”;
2
pairs of substrings “aa” and “bb”, each with valid merging sequences “0101” and “1010”;
2
pairs of substrings “aaa” and “b”, each with no valid merging sequences;
1
pair of substrings “aaa” and “bb” with a valid merging sequence “01010”;
Thus, the answer is 6⋅2+3⋅1+4⋅1+2⋅2+2⋅0+1⋅1=24.
中文:
给你两个字符串,x和y。然后再给你一个由01组成的字符串z,根据字符串x和y以及01序列z可以拼成另一个字符串s,如果z[i]等于0那么从x开头拿一个字符串放到s,如果是1那么从y拿一个字符放到s。这里要求所有的s必须满足s[i] != s[i-1],现在问你
在字符串x中截取一段[x1,y1]在字符串y中截取[x2,y2]可以满足s[i] != s[j] 且所有s各不相同的z有多少种?
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000 + 5;
const ll mod = 998244353;
char x[maxn], y[maxn];
ll dp[maxn][maxn][2];
ll px[maxn], py[maxn];int main()
{ios::sync_with_stdio(false);while(cin>>x + 1 >> y + 1){int ans = 0;int n = strlen(x+1);int m = strlen(y+1);memset(dp,0,sizeof(dp));memset(px,0,sizeof(px));memset(py,0,sizeof(py));for (int i=1;i<=n;i++){px[i] = 1;if (x[i - 1] != x[i]){px[i] += px[i-1];px[i] %= mod;}}for (int i=1;i<=m;i++){py[i] = 1;if (y[i - 1] != y[i]){py[i] += py[i-1];py[i] %= mod;}}for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){if (x[i] != y[j]){dp[i][j][0] = (dp[i][j][0] + py[j]) % mod;dp[i][j][1] = (dp[i][j][1] + px[i]) % mod;dp[i][j][0] = (dp[i][j][0] + dp[i-1][j][1]) % mod;dp[i][j][1] = (dp[i][j][1] + dp[i][j-1][0]) % mod;//cout <<"i = " << i << " j = " << j << " dp[i][j][0] = " << dp[i][j][0] << std::endl;}if (x[i-1] != x[i]){dp[i][j][0] += dp[i-1][j][0];dp[i][j][0] %= mod;}if (y[j-1] != y[j]){dp[i][j][1] += dp[i][j-1][1];dp[i][j][1] %= mod;}ans = (ans + dp[i][j][0] + dp[i][j][1]) % mod;}}cout << ans << endl;}return 0;
}
思路:
组合计数问题,一看就是dp。
容易考虑到设置状态dp[i][j]表示取到x的第i个字符,取到y的第j个字符时有多少种01序列满足,但是题目中要求z[i]!=z[i-1],所以要增加一个状态用来标记最后一个字符是什么
设置dp[i][j][k] 其中k等于0或者1,当k为0表示最后一个字符是x的最后一个字符结尾,k为1表示最后一个字符是y的最后一个。
这里如果考虑dp[i][j][k]表示字符串x从第一个连续拿到第|x|个,字符串y从第一个连续拿到第|y|个有多少中构造01序列的方法,状态转移方程还是很容易得到的,但是现在题目中要求的是x与y的任意连续字串能构造出多少个满足条件的z,如何解决呢?
仍然可以使用上面上面的状态进行进行计数,那么上面的状态表示的是:
x取[a,i],y取[b,j],且最后一个字符是x结尾或者是y结尾时,能构成的01序列的个数,即取以i结尾x的字串,以j结尾y的字串构成01序列。
当x[i]!=x[i-1]是,有状态转移方程:
d p [ i ] [ j ] [ 0 ] + = d p [ i − 1 ] [ j ] [ 0 ] dp[i][j][0] += dp[i-1][j][0] dp[i][j][0]+=dp[i−1][j][0] 表示以x串结尾,且x的第i个字符与x的第i-1个字符不相同的情况。
同理y[j]!=y[j-1]
d p [ i ] [ j ] [ 1 ] + = d p [ i ] [ j − 1 ] [ 1 ] dp[i][j][1] += dp[i][j-1][1] dp[i][j][1]+=dp[i][j−1][1]
当x[i]!=y[j]时
d p [ i ] [ j ] [ 0 ] + = d p [ i − 1 ] [ j ] [ 1 ] dp[i][j][0] += dp[i-1][j][1] dp[i][j][0]+=dp[i−1][j][1] 表示x的第i个字符加到y的第j个字符的后面
同理
d p [ i ] [ j ] [ 1 ] + = d p [ i ] [ j − 1 ] [ 0 ] dp[i][j][1] += dp[i][j-1][0] dp[i][j][1]+=dp[i][j−1][0]
上面的累计计数是不完整的,还需考虑如下的两种情况:
- d p [ i ] [ j ] [ 0 ] + = p y [ j ] dp[i][j][0] += py[j] dp[i][j][0]+=py[j]
- d p [ i ] [ j ] [ 1 ] + = p x [ i ] dp[i][j][1] += px[i] dp[i][j][1]+=px[i]
其中py[j]表示以y[j]结尾,仅使用字符串y能构成y[j]!=y[j-1]的字符粗的数量,同理px[i]
那么,上面第一种情况补充的是字符串x仅使用第x[i]个字符加到py[j]的后面
同理第二种情况
最后累计全部中间的字符串数量即可
这篇关于cf Educational Codeforces Round 106 E. Chaotic Merge的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!