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.
The answer is the number of ways we can choose 2 equal strings from the list of all strings generated by this procedure. Consider 4-dimensional dp: dp[pos1A][pos1B][pos2A][pos2B] = the number of ways we can generate 2 equal strings such that the first one has used pos1A characters from the string A and pos1B characters from B, and the second one has used pos2A characters from A and pos2B from B. The answer is dp[|A|][|B|][|A|][|B|]. We can compress this dp to O(n3) states by using only states where the first and the second string have the same length.
Wow, thank you :D
http://wcipeg.com/problem/noi09p5
Yesss, I remember the organizes switched AB with HG to trick copyrights lol