Figureoutthesequence

The Coronavirus is evil and loves to store everything into its RNA, which is why it often has genetic mutation.

One day the Coronavirus get two RNA sequences, and it decided to add them to its RNA. It will add the first sequence to the end of its current RNA, and next turn it will add the another one.

For the following turns, the virus will always add the sequence it got in the previous turn to the beginning of the current sequence.

Suppose the virus has nothing in its RNA initially, and two RNA sequences are: $\{"abc","def"\}$ (The virus has no sanity, so the RNA sequence can be far more than "agcu" ! ) , the final RNA sequence after each turn will be:

$F[1] = “abc”$

$F[2 ] = “def”$

$F[3 ] = “abcdef”$

$F[4 ] = “defabcdef”$

$F[5 ] = “abcdefdefabcdef”$

……

As an expert in biochemistry, GGG has been devoting himself into analyzing this virus since its outbreak, whose task is to figure out the exact composition of this virus (That is: how many times does each letter appear in the final sequence). However, what he can get is only how many turns the virus has changed its RNA and the initial two sequences. can you help him to solve this problem?

The input only consists of one test case.

The first line and the second line will be two string $s$ and $t$ , which are the initial RNA sequences, the sequences are both made up of lower-case Latin letters and upper-case Latin letters. The virus starts with string $s$ .

The third line will be an integer $n$ , which is the number of turns that the virus has taken to modify its RNA.

It's guaranteed that $1\le n \le 40$ , the length of two strings $0\lt |s|,|t| \le 20$ .

The output should contain several lines for each letters in the final RNA sequence in lexicographical order.

Each line should be in format like $letter: num$ , the first letter is the related lower-case letter, the second one is a colon, the third one is a space and then is an integer $num$ which is the number of occurrences of this letter in the final RNA sequence.

If a letter doesn't appear in the sequence, you can simply ignore it.

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll a[45][200]; string s1, s2; int main() { ll n; cin >> s1 >> s2 >> n; for (auto x : s1) a[1][x]++; for (auto x : s2) a[2][x]++; for (ll i = 3; i <= n; i++) for (ll j = 'A'; j <= 'z'; j++) a[i][j] = a[i - 1][j] + a[i - 2][j]; for (ll i = 'A'; i <= 'z'; i++) if (a[n][i]) printf("%c: %d\n", i, a[n][i]); return 0; }

详情