Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Help needed in a problem

Revision en1, by meiniak, 2020-01-22 22:33:24

Given an array of strings, each of the same length and a target string construct the target string using characters from the strings in the given array such that the indices of the characters in the order in which they are used form a strictly increasing sequence. Here the index of a character is the position at which it appears in the string. Note that it is acceptable to use multiple characters from the same string. Determine the number of ways to construct the target string. One construction is different from another if either the sequences of indices they use are different, or the sequences are the same but there exists a character at some index such that it is chosen from a different string in these constructions. Since the answer can be very large, return the value modulo (109 + 7). Consider an example with n = 3 strings, each of length 3. Let the array of strings be words = ["adc", "aec", "erg"], and the target string target = "ac". There are 4 ways to reach the target.

  1. Select the 1st character of "adc" and the 3rd character of "adc".
  2. Select the 1st character of "adc" and the 3rd character of "aec".
  3. Select the 1st character of "aec" and the 3rd character of "adc".
  4. Select the 1st character of "aec" and the 3rd character of "aec".
Tags #strings, #combinatorics

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English meiniak 2020-01-22 22:33:24 1306 Initial revision (published)