Official

F - Minflip Summation Editorial by en_translator

If the string \(S\) does not contain ? and \(K=1\)

First, for a string \(S\) consisting only from 0 and 1, if \(K=1\), that is, if it is equivalent to applying the operation directly, what will the answer be?
For a string \(S=S_1S_2...S_{|S|}\), let \(X\) be a set of integer \(i\) such that \(S_i \neq S_{i+1}\). For example, if \(S=\)1110010, \(X=\{3,5,6\}\).
Then, the operation for the \(l\)-th through \(r\)-th characters described in the problem statement can be rephrased as follows:

  • If \(l \neq 1\), perform an operation \(\alpha(l-1)\).
  • If \(r \neq |S|\), perform an operation \(\alpha(r)\).
Operation \(\alpha(k)\) : If \(X\) contains an integer \(k\), remove it. If not, add it.

For instance, we’ve seen that when \(S=\)1110010, \(X=\{3,5,6\}\), and if you apply an operation with \(l=4\) and \(r=7\), \(S\) will become 1111101 and \(X\) will become \(\{5,6\}\). If you apply another operation of \(l=3\) and \(r=5\), \(S\) becomes 1100001 and \(X\) becomes \(\{2,6\}\).

All the characters in string \(S\) is the same if and only if the set \(X\) is empty.
Also, if you choose appropriate \(l\) and \(r\), you can remove at most \(2\) elements from \(X\).
Obviously, the size of set \(X\) is equal to the pair of adjacent and different characters in \(S\). For example, if \(S=\)101011001, the size of \(X\) is \(6\).
So, the desired answer is \(\lceil \frac{D}{2} \rceil\), where \(D\) denotes the number of adjacent and different characters in \(S\).

The solution of this problem

First, when \(|T|=1\), that is, \(|S| \times K = 1\), the answer is \(0\). We will consider otherwise.

We figured out the necessary number of operations for a string, but for the problem this time, it is quite impossible to try all the \(2^{Kq}\) patterns of strings. Accordingly, we have to come up with an efficient solution.

Here, for all \(2^{Kq}\) strings, let us count the sum of the numbers of adjacent different characters.
To come to the point, the desired number \(A\) can be calculated as follows:

\(A = 2^{Kq} \times ( ( K \times \displaystyle \sum_{i=1}^{|S|-1} f(S_i,S_{i+1}) ) + (K-1) \times f(S_1,S_{|S|}))\)

Here, \(\begin{aligned} f(a,b) = \begin{cases} \frac{1}{2} & \text{(if at least one of }a\text{ and }b\text{ is ?)} \\ 1 & \text{(if neither }a\text{ nor }b\text{ is ? and }a\neq b\text{)} \\ 1 & \text{(if neither }a\text{ nor }b\text{ is ? and }a = b\text{)} \\ \end{cases} \end{aligned}\)

The details of the discussion is collapsed here. First, for each $1 \le i < |T'|$, we will consider how many of the $2^{Kq}$ strings satisfy $T'_i \neq T'_{i+1}$.
First, for the case where neither $T_i$ nor $T_{i+1}$ is ?, then $T'_i=T'_{i+1}$ for all the string, or $T'_i \neq T'_{i+1}$ for all the string.
Next, we consider the case where exactly one of $T_i$ and $T_{i+1}$ is ?. In such case, there are the same number of substitutions such that $T'_i = T'_{i+1}$ and such that $T'_i \neq T'_{i+1}$.
Finally, we will consider the case where both $T_i$ and $T_{i+1}$ are ?. In fact, in such case, there are the same number of substitutions such that $T'_i = T'_{i+1}$ and such that $T'_i \neq T'_{i+1}$ too. This is because, out of four substitutions of adjacent ?, two of them will yield the same characters.

String $T'$ has $K$ pairs of adjacent characters that originates from $S_i$ and $S_{i+1}$. $(1 \le i < |S|)$
Moreover, there are $(K-1)$ pairs of adjacent characters that originates from $S_{|S|}$ and $S_1$.
Therefore, one can obtain the equation in the conclusion.

Then, the answer will be approximately \(\frac{A}{2}\). However, a little problem still remains.
For example, there are \(3\) pairs of adjacent different characters in 101100, while 1011001 has \(4\) of them, but both strings requires two operations to make all the characters equal. Generally, if there are odd number of adjacent different characters in a string, the number of operations required will be same to that for the string with one more such pairs.
Therefore, if you add to \(A\) the number of strings which contains odd number of pairs of adjacent different characters, then the answer will exactly \(\frac{A}{2}\).
The number of string which contains odd number of pairs of adjacent different characters is, actually, equal to the number of string \(S\) whose the first and the last characters are different.
Therefore, the number can be calculated as \(2^{Kq} \times f(S_1,S_{|S|})\).

Therefore, the problem can be solved in a total of \(O(|S|)\) time.
Note that the operation of dividing by \(\frac{1}{2}\) can be achieved by multiplying \((5 \times 10^8+4)\), which is the inverse of \(2\) modulo \((10^9+7)\).

Sample code in C:

#include<stdio.h>
#include<string.h>
#define mod 1000000007
#define inv2 500000004

long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}

long long f(char a,char b){
  if(a=='?' || b=='?'){return inv2;}
  if(a!=b){return 1;}
  return 0;
}

int main(){
  char s[131072];
  long long k;
  scanf("%s%lld",s,&k);
  int len=strlen(s);
  if(k*len==1){printf("0\n");return 0;}
  long long q=0;
  for(int i=0;i<len;i++){
    if(s[i]=='?'){q++;}
  }
  
  long long res=0;
  long long pat=power(2,k*q);
  for(int i=0;i<len;i++){
    res+=((pat*k)%mod)*f(s[i],s[(i+1)%len]);
    res%=mod;
  }
  res*=inv2;res%=mod;
  printf("%lld\n",res);
  return 0;
}

posted:
last update: