1. 部分問題を解く

まずは，文字列 \(s_1,s_2\in S_{n,m}\) が与えられたときに，\(f(s_1,s_2)\) を \(O(n+m)\) で求める問題を考えます．

文字列 \(s\in S_{n,m}\) に対して，長さ \(n\) の数列 \(P(s)\) を次で定めます．

• \(s\) の \(i\) 番目の \(0\) までに登場する \(1\) の個数を \(P(s)[i]\) とする．

例えば，\(s=\) 01011001 \(\in S_{4,4}\) のとき \(P(s)=(0,1,3,3)\) です．

事実1. \(s\in S_{n,m}\) の部分列 \(01\) を swap することは，\(P(s)\) のある値を \(1\) 増やすことに対応する．また，\(s\) の部分列 \(10\) を swap することは，\(P(s)\) のある値を \(1\) 減らすことに対応する．（ただし，値を増減させたあとの \(P(s)\) は常に広義単調増加である．）

事実2. \(s,t \in S_{n,m}\) に対して，\(d(s,t)=\displaystyle \sum _{i=1}^n |P(s)[i]-P(t)[i]|\) である．

事実3. \(s,t\in S_{n,m}\) に対して，\(s<t\) と \(P(s)<P(t)\) は同値である．

よって，\(f(s_1,s_2)\) を求める問題は次のように言い換えられます．

長さ \(n\) の広義単調増加列 \(A(=P(s_1)),B(=P(s_2))\) が与えられる．ここで，\(A[1],B[1]\geq0,A[n],B[n]\leq m\) である．

\(\displaystyle \sum _{i=1}^n |A[i]-C[i]|=\sum _{i=1}^n |B[i]-C[i]|\) かつ \(C[1]\geq 0,C[n]\leq m\) となる広義単調増加列 \(C\) のうち辞書順最小のものを求めよ．

以降の議論では，一般性を失わず \(\sum A\geq \sum B\) とし，\(\Delta=\sum A -\sum B(\geq 0)\) とします．また，長さが等しい数列 \(a,b\) に対して，\(\mathrm{diff}(a,b)=\displaystyle \sum_{i=1}^{|a|} |a[i]-b[i]|\) と定義します．

事実4. \(\Delta\) が奇数なら，条件を満たす \(C\) は存在しない．

よって，\(C\) が存在するためには \(\Delta\) は偶数である必要があります．

次に \(\Delta\) が偶数のとき，辞書順最小の \(C\) の構築方法を示します． 数列 \(X\) を \(X[i]=\min(A[i],B[i])\) で定めます．このとき，\(\Delta=\mathrm{diff}(A,X)-\mathrm{diff}(B,X)\) になります．\(C\) を構築するための方針としては，\(\mathrm{diff}(A,X)-\mathrm{diff}(B,X)\) の値が \(0\) になるように \(X\) の値を調整することです．

事実5. \(X\) のある値を変化させると，\(\mathrm{diff}(A,X)-\mathrm{diff}(B,X)\) の値は以下のように変化する．（値を変化させたあと，必ずしも \(X\) が広義単調増加である必要はない．）

1. \(X[i]<A[i],X[i]<B[i]\) を満たす \(i\) に対して，\(X[i]\) の値を \(1\) 増加させても \(\mathrm{diff}(A,X)-\mathrm{diff}(B,X)\) の値は変化しない．
2. \(X[i]\leq A[i],X[i]\leq B[i]\) を満たす \(i\) に対して，\(X[i]\) の値を \(1\) 減少させても \(\mathrm{diff}(A,X)-\mathrm{diff}(B,X)\) の値は変化しない．
3. \(B[i]\leq X[i]<A[i]\) を満たす \(i\) に対して，\(X[i]\) の値を \(1\) 増加させると \(\mathrm{diff}(A,X)-\mathrm{diff}(B,X)\) は \(2\) 減少する．
4. \(B[i]<X[i]\leq A[i]\) を満たす \(i\) に対して，\(X[i]\) の値を \(1\) 減少させると \(\mathrm{diff}(A,X)-\mathrm{diff}(B,X)\) は \(2\) 増加する．
5. \(A[i]\leq X[i]<B[i]\) を満たす \(i\) に対して，\(X[i]\) の値を \(1\) 増加させると \(\mathrm{diff}(A,X)-\mathrm{diff}(B,X)\) は \(2\) 増加する．
6. \(A[i]<X[i]\leq B[i]\) を満たす \(i\) に対して，\(X[i]\) の値を \(1\) 減少させると \(\mathrm{diff}(A,X)-\mathrm{diff}(B,X)\) は \(2\) 減少する．
7. \(A[i]\leq X[i],B[i]\leq X[i]\) を満たす \(i\) に対して，\(X[i]\) の値を \(1\) 増加させても \(\mathrm{diff}(A,X)-\mathrm{diff}(B,X)\) の値は変化しない．
8. \(A[i]< X[i],B[i]<X[i]\) を満たす \(i\) に対して，\(X[i]\) の値を \(1\) 減少させても \(\mathrm{diff}(A,X)-\mathrm{diff}(B,X)\) の値は変化しない．

上で示した \(8\) つの操作のうち，辞書順最小を目指すうえで本質的な操作は \(2\) つ目と \(3\) つ目のみです． 以下のアルゴリズムによって辞書順最小の \(C\) を構築することができます．

• \(i\) の降順に見ていき，\(\mathrm{diff}(A,X)-\mathrm{diff}(B,X)>0\) かつ \(B[i]\leq X[i]<A[i]\) である限り \(X[i]\) に \(1\) 加える（このとき \(\mathrm{diff}(A,X)-\mathrm{diff}(B,X)\) は \(2\) 減少する）．
• 上の操作が終わった後，\(i\) の昇順に見ていき，\(X[i]\leq A[i],X[i]\leq B[i]\) を満たすものについて，\(X[i]\leftarrow X[i-1]\) とする．
• 最終的に得られた \(X\) が辞書順最小の \(C\) である．

これは \(O(n+m)\) で行うことができます．得られた \(C\) に対して \(P(s)=C\) を満たす \(s\) は容易に求めることができます．

def P(n, m, s):
    a = [0] * n
    now = 0
    for i in range(n):
        while s[i + now] == "1":
            now += 1
        a[i] = now
    return a


def f(n, m, s1, s2):
    A = P(n, m, s1)
    B = P(n, m, s2)

    d = sum(A) - sum(B)
    if d % 2 == 1:
        return -1
    if d < 0:
        A, B = B, A
        d = -d

    X = [min(A[i], B[i]) for i in range(n)]
    for i in range(n - 1, -1, -1):
        res = max(0, min(d // 2, A[i] - B[i]))
        X[i] += res
        d -= 2 * res

    for i in range(n):
        if i == 0:
            if X[i] <= min(A[i], B[i]):
                X[i] = 0
        elif X[i] <= min(A[i], B[i]):
            X[i] = X[i - 1]

    now = 0
    ans = []
    for i in range(n):
        while now < X[i]:
            ans.append("1")
            now += 1
        ans.append("0")

    while now < m:
        ans.append("1")
        now += 1

    return "".join(ans)

2. 本問題の解法

問題で与えられる \(T\) に対して，\(C=P(T)\) とします．上で示したアルゴリズムを踏まえると，以下を満たす長さ \(n\) の整数列の組 \((A,B)\) の個数が求められれば良いです．

• \(A,B\) は広義単調増加
• \(A[1],B[1]\geq 0, A[n],B[n]\leq m\)
• \(\sum A\geq \sum B\)
• \(C[0]=0\) として \(C[i-1]<C[i]\) を満たす \(i(\geq 1)\) を昇順に \(i_1,i_2,i_3,\ldots\) とする．このとき，
  • \(B[i_1]<C[i_1]\leq A[i_1]\)
  • \(j=i_2,i_3,\ldots\) に対して \(B[j]<C[j]=A[j]\)
  • \(j>i_1\) に対して \(\max(B[j], C[j]) \geq A[j]\)
• \(\displaystyle \sum _{i=1}^n A[i]=\sum _{i=1}^n B[i] + 2\sum _{i=1}^n \max(0,C[i]-B[i])\)

これは，動的計画法によって必要な情報を持たせることで求めることができます．具体的には \(\mathrm{dp}[i][d][a][b]\) で， \(C\) の \(i\) 項目まで見たときに，\(\displaystyle \sum _{j=1}^i A[j] - \sum _{j=1}^i B[j] - 2\sum _{j=1}^i \max(0,C[j]-B[j])=d, A[i]=a, B[i]=b\) であり，かつ上の条件を満たす組 \((A[:i],B[:i])\) の個数とすればよいです．状態数は \(O(n^2m^3)\) あり，愚直に遷移すると各遷移に対して \(O(m^2)\) かかりますが，二次元累積和によって高速化することができます．計算量は \(O(n^2m^3)\) です．