AkariDaisukiDiv1
SRM 541 · 2011-11-22 · by semiexp
Problem Statement
Consider the following function:
f(X) = Waai + X + Akari + X + Daisuki
Here, X is a string and + denotes string concatenation.
Waai, Akari and Daisuki are constant non-empty strings.
You are given 5
Compute how many times F occurs in f^k(S) as its substring. (The notation f^k(S) means that f is applied to S exactly k times in a row. See Notes for a formal definition.) Since the number can be quite large, compute the number modulo 1,000,000,007.
Notes
- Formally, we have f^1(X)=f(X) and for k greater than one we have f^k(X)=f(f^(k-1)(X)).
- String A is substring of B if A can be obtained by erasing some (possibly zero) characters from the beginning of B and some (possibly zero) characters from the end of B.
Constraints
- Waai, Akari, Daisuki, S, and F will contain between 1 and 50 characters, inclusive.
- Each character of Waai, Akari, Daisuki, S, and F will be a lowercase letter ('a'-'z').
- k will be between 1 and 10,000,000, inclusive.
"a" "b" "c" "x" "axb" 2 Returns: 2
S = "x", f(S) = "axbxc", f^2(S) = f("axbxc") = "aaxbxcbaxbxcc". This string contains the substring "axb" twice.
"a" "b" "c" "x" "abcdefghij" 1 Returns: 0
The answer can be zero.
"a" "a" "a" "b" "aba" 2 Returns: 4
S = "b", f(S) = "ababa", f^2(S) = f("ababa") = "aababaaababaa". This string contains the substring "aba" four times. You must count overlapping substrings.
"a" "b" "c" "d" "baadbdcbadbdccccbaaaadbdcbadbdccbaadbdcba" 58 Returns: 191690599
"a" "x" "y" "b" "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab" 49 Returns: 1
Submissions are judged against all 240 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AkariDaisukiDiv1 with a public method int countF(string Waai, string Akari, string Daisuki, string S, string F, int k) · 240 test cases · 2 s / 256 MB per case