Contest Duration: - (local time) (100 minutes) Back to Home

## 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{eqnarray} 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{eqnarray}$$

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: