F. Number of Subsequences Explanation

Правка en1, от YCKC_LCJ, 2020-09-29 16:53:18

We are given a string with the length of N, and the position containing "?" can be replaced by "a" or "B" or "C". Finally, how many subsequences of "ABC" can be obtained, and the modulus of its number is 100000007

First of all, let's consider the case that there is no "?" in the string. Define DP [s [J] — a '+ 1]] [J] to represent the contribution of the current character, and j to the position of the character in the string. For example, if the current character is "a", then DP [1] [J] = (DP [1] [J-1] + pre [CNT])% mods The pre array represents the contribution to "a" after the replacement of "?, which is equivalent to the conversion of"? Into three branches. Similarly, for DP [2] [J] = (DP [2] [J-1] + DP [1] [J-1])% mods represents the contribution made by the previous "a" when the current character is "B". Similarly, for the character "C", since "?" produces three branches, we have to multiply the contribution of "?" by 3
94214264 Please give me some advice if there is something wrong

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский YCKC_LCJ 2020-09-29 16:53:18 1071 Initial revision (published)