Hey guys I have been working on this question, https://open.kattis.com/problems/sequences.

Basically, the idea of my code is that for each case, the number of inversions needed is simply the sum of all indexes of 0 takeaway the (number of 0s -1)th triangular number. Therefore, all I need to do is add up all of the indexes of 0s, times by the number of cases, and add all indexes of questions marks, times the number of cases/2, since each question mark is a 0 exactly half the time. I then calculate the number of cases that within the question marks, there are 0, 1, 2 ..., (number of question mark) 0s using combinations, times by the (number of 0s -1)th triangular number, and minus this off the total. My code works kind of quickly but as I start putting around 20,000 question marks as my input, it starts to take more than a second. However, I need it to take 500,000 question marks as input and return a value within a second. Any ideas on how to make it faster?

Thanks! Also, tell me if I need to clarify anything.

I have been working on this question, https://open.kattis.com/problems/sequences.

Basically, the idea of my code is that for each case, the number of inversions needed is simply the sum of all indexes of 0 takeaway the (number of 0s -1)th triangular number. Therefore, all I need to do is add up all of the indexes of 0s, times by the number of cases, and add all indexes of questions marks, times the number of cases/2, since each question mark is a 0 exactly half the time. I then calculate the number of cases that within the question marks, there are 0, 1, 2 ..., (number of question mark) 0s using combinations, times by the (number of 0s -1)th triangular number, and minus this off the total. My code works kind of quickly but as I start putting around 20,000 question marks as my input, it starts to take more than a second. However, I need it to take 500,000 question marks as input and return a value within a second. Any ideas on how to make it faster?

You are given a sequence, in the form of a string with characters ‘0’, ‘1’, and ‘?’ only. Suppose there are k ‘?’s. Then there are 2k ways to replace each ‘?’ by a ‘0’ or a ‘1’, giving 2k different 0-1 sequences (0-1 sequences are sequences with only zeroes and ones).

For each 0-1 sequence, define its number of inversions as the minimum number of adjacent swaps required to sort the sequence in non-decreasing order. In this problem, the sequence is sorted in non-decreasing order precisely when all the zeroes occur before all the ones. For example, the sequence 11010 has 5 inversions. We can sort it by the following moves: 11010 → 11001 → 10101 → 01101 → 01011 → 00111.

Find the sum of the number of inversions of the 2k sequences, modulo 1000000007 (109+7).

Input
The first and only line of input contains the input string, consisting of characters ‘0’, ‘1’, and ‘?’ only, and the input string has between 1 to 500000 characters, inclusive.

Output
Output an integer indicating the aforementioned number of inversions modulo 1000000007

You are given a sequence, in the form of a string with characters ‘0’, ‘1’, and ‘?’ only. Suppose there are n ‘?’s. Then there are 2n ways to replace each ‘?’ by a ‘0’ or a ‘1’, giving 2n different 0-1 sequences (0-1 sequences are sequences with only zeroes and ones).

For each 0-1 sequence, define its number of inversions as the minimum number of adjacent swaps required to sort the sequence in non-decreasing order. In this problem, the sequence is sorted in non-decreasing order precisely when all the zeroes occur before all the ones. For example, the sequence 11010 has 5 inversions. We can sort it by the following moves: 11010 → 11001 → 10101 → 01101 → 01011 → 00111.

Find the sum of the number of inversions of the 2n sequences, modulo 1000000007 (109+7).

Input
The first and only line of input contains the input string, consisting of characters ‘0’, ‘1’, and ‘?’ only, and the input string has between 1 to 500000 characters, inclusive.

Output
Output an integer indicating the aforementioned number of inversions modulo 1000000007