Tough DP (I think) problem

Revision en2, by Alex7, 2017-06-01 00:34:26

Given 2 binary strings A and B of each with length at most 175, we want to combine them to produce a new string C the following way: As long as either one of strings A, B choose one of them (as long as it's non empty) add the first character in the chosen string to the end of C and then delete from that string. The task is for each distinct possible resulting C sum the square of the number of ways you can arrive at it with that procedure modulo some prime.

This problem was presented in a local IOI selection in 2012, we suspect it was ripped from some USACO related contest (since all other problems that year were also stolen from there), so I don't really have a link for it but I know it's possible to solve it. Any ideas? Thanks in advance.


  Rev. Lang. By When Δ Comment
en2 English Alex7 2017-06-01 00:34:26 30 Tiny change: ' solve it.' -> ' solve it. Any ideas? Thanks in advance.'
en1 English Alex7 2017-06-01 00:32:43 749 Initial revision (published)