Hi Friends! Here is the problem created by one of the user's at my site. I don't ask for solution (at least yet, ha-ha, going to try thinking a bit more) — but invite you to check your skills, presumably, at DP.

It has somewhat lengthy description, but boils down to counting number of differing subsequences in 01-string with required balance of zeroes and ones. I quickly started scratching typical DP-like double loop, but soon found it doesn't account for possible duplicates: i.e. in the sequence 1010 we can pick 10 subsequence in two ways but they are not considered different. Results seemingly can grow somewhere to 10^18 so naively keeping all sequences in hashtable doesn't look like a viable approach. Sorry for my naive thoughts, I'm obviously lame at this and perhaps there is a known solution. However if you, like me, don't know it, you can spend some time on it...