Official

F - Minflip Summation Editorial by physics0523

文字列 \(S\) が ? を含まず、 \(K=1\) である場合

まずは、 0 と 1 のみから文字列 \(S\) について、 \(K=1\) の場合、すなわち文字列 \(S\) に直接操作をかけるのと同等な場合に答えがいくつになるか考えてみましょう。
文字列 \(S=S_1S_2...S_{|S|}\) について、 \(S_i \neq S_{i+1}\) であるような整数 \(i\) の集合を \(X\) とします。例えば、 \(S=\)1110010 について、\(X=\{3,5,6\}\) となります。
すると、問題文中の文字列の \(l\) 文字目から \(r\) 文字目に対する操作は、以下のような操作に言い換えられます。

  • もし、\(l \neq 1\) なら、操作 \(\alpha(l-1)\)を行う。
  • もし、\(r \neq |S|\) なら、操作 \(\alpha(r)\)を行う。
操作 \(\alpha(k)\) : \(X\) に整数 \(k\) が含まれるなら、削除する。含まれないなら、追加する。

例えば、 \(S=\)1110010 について、\(X=\{3,5,6\}\) でしたが、ここに \(l=4,r=7\) として操作を行うと操作後に \(S=\)1111101 、 \(X=\{5,6\}\) となります。この後さらに \(l=3,r=5\) として操作を行うと \(S=\)1100001 、 \(X=\{2,6\}\) となります。

集合 \(X\) が空集合になったとき、かつその時に限って、文字列 \(S\) の全ての文字が等しくなります。
さらに、うまく \(l,r\) を選んで操作を行うと、一度の操作でに \(X\) から要素を \(2\) つまで選んで消せることがわかります。
当たり前のことですが、集合 \(X\) の大きさは、 \(S\) に含まれる隣り合う文字が異なるような箇所の個数と等しいです。例えば、 \(S=\)101011001 について、 \(X\) の大きさは \(6\) です。
なので、求める答えは、 \(S\) に隣り合う文字が異なるような箇所が \(D\) ヶ所あるとき、 \(\lceil \frac{D}{2} \rceil\) となります。

今回の問題の解法

まず、 \(|T|=1\) 、すなわち \(|S| \times K = 1\) の場合、答えは \(0\) です。ここからはこれ以外の場合を考えます。

あるひとつの文字列について必要な操作回数は分かりましたが、今回の問題について、 \(2^{Kq}\) 通りの文字列全てを試すといったことは到底不可能です。よって、効率的な解法を考える必要があります。

ここで、 \(2^{Kq}\) 通りの文字列全てについて、隣り合う文字が異なるような箇所が合計でいくつあるか求めることを考えます。
結論から言うと、求める数を \(A\) とすると、次のように求められます。

\(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|}))\)

ただし、 \(\begin{aligned} f(a,b) = \begin{cases} \frac{1}{2} & (a,bの少なくとも一方が?である) \\ 1 & ( a,b両方が?でなく、 a \neq b ) \\ 0 & ( a,b両方が?でなく、 a = b ) \end{cases} \end{aligned}\)

この議論の詳細は折りたたみに記載します。 まず、各 $1 \le i < |T'|$ について、 $2^{Kq}$ 通りの文字列のうち、何個の文字列について $T'_i \neq T'_{i+1}$ となるか考えます。
まず、 $T_i$ と $T_{i+1}$ の双方が ? でない場合については、全ての文字列について $T'_i=T'_{i+1}$ となるか、全ての文字列について $T'_i \neq T'_{i+1}$ となります。
次に、 $T_i$ と $T_{i+1}$ のうち丁度一方が ? である場合を考えます。この時は、 $T'_i = T'_{i+1}$ となるような置き換えと $T'_i \neq T'_{i+1}$ となる置き換えが同数存在します。
最後に、 $T_i$ と $T_{i+1}$ の双方が ? である場合を考えます。実はこの場合も、 $T'_i = T'_{i+1}$ となるような置き換えと $T'_i \neq T'_{i+1}$ となる置き換えが同数存在します。その理由は、隣接する ? の置き換えが $4$ 通りあるうちの $2$ 通りで置き換えた後の文字が等しくなるからです。

文字列 $T'$ の中に、もともと $S_i$ と $S_{i+1}$ が隣接する箇所に相当していた箇所は $K$ ヶ所存在します。$(1 \le i < |S|)$
さらに、 $S_{|S|}$ と $S_1$ が隣接する箇所に相当していた箇所が $(K-1)$ ヶ所存在します。
これらより、結論の式を得ることができます。

すると、答えはおおよそ \(\frac{A}{2}\) となります。しかし、まだ少し問題が残っています。
例えば、文字列 101100 は隣り合う文字が異なる箇所は \(3\) ヶ所で、文字列 1011001 は \(4\) ヶ所ですが、どちらも全ての文字を等しくするのに \(2\) 回の操作を要します。一般に、隣り合う文字が異なる箇所が奇数個のとき、それよりも \(1\) ヶ所異なる箇所が多い文字列と必要な操作回数が同じになってしまいます。
つまり、 \(A\) に隣り合う文字が異なる箇所が奇数個である文字列の個数を加算すれば、答えは完全に \(\frac{A}{2}\) となります。
隣り合う文字が異なる箇所が奇数個である文字列の個数というのは、実は、 \(S\) の先頭と末尾の文字が異なる文字列の個数と言い換えることができます。
なので、この個数は \(2^{Kq} \times f(S_1,S_{|S|})\) と求めることができます。

よって、この問題を時間計算量 \(O(|S|)\) で解くことができます。
なお、 \(\frac{1}{2}\) をかけるという操作は、\(\mod (10^9+7)\) における \(2\) の逆元である \((5 \times 10^8+4)\) をかけることで実現可能です。

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: