Pythonで文字列を分割する方法の数を見つけるためのプログラム

バイナリ文字列sがあるとすると、sを3つの空でない文字列s1、s2、s3に分割して（s1連結s2連結s3 =s）することができます。文字数「1」がs1、s2、およびs3で同じになるように、sを分割できる方法の数を見つける必要があります。答えは非常に大きい可能性があるため、答えmod 10 ^ 9+7を返します。

したがって、入力がs ="11101011"の場合、出力は2になります。これは、「11 | 1010|11」と「11|101|011」のように分割できるためです。

これを解決するには、次の手順に従います。

• count：=sの1の数を数える
• m：=10 ^ 9 + 7
• ans：=サイズ2の配列で、0で埋めます
• count mod 3が0と同じでない場合、
  • 0を返す
• それ以外の場合、カウントが0と同じ場合、
  • return（nCrはs -1のサイズ、rは2）mod m
• 左：=0
• 右：=sのサイズ-1
• cum_s：=0、cum_e：=0
• cum_s <=count/3の商またはcum_e<=count / 3の商、do
  • s[left]が"1"と同じ場合、
    • cum_s：=cum_s + 1
  • s[right]が"1"と同じ場合、
    • cum_e：=cum_e + 1
  • cum_sがcount/3の商と同じ場合、
    • ans [0]：=ans [0] + 1
  • cum_eがcount/3の商と同じ場合、
    • ans [1]：=ans [1] + 1
  • 左：=左+ 1
  • right：=right-1
• return（ans [0] * ans [1]）mod m

理解を深めるために、次の実装を見てみましょう。

例

def solve(s):
   count = s.count("1")
   m = 10**9 + 7
   ans = [0, 0]
   if count % 3 != 0:
      return 0
   elif count == 0:
      return comb(len(s)-1,2) % m
   left = 0
   right = len(s)-1
   cum_s = 0
   cum_e = 0
   while(cum_s <= count//3 or cum_e <= count//3):
      if s[left] == "1":
         cum_s+=1
      if s[right] == "1":
         cum_e+=1
      if cum_s == count//3:
         ans[0]+=1
      if cum_e == count//3:
         ans[1]+=1
      left += 1
      right -= 1
   return (ans[0]*ans[1]) % m
s = "11101011"
print(solve(s))

入力

"11101011"

出力

2