题解：P11487 「Cfz Round 5」Gnirts 10

枚举 \(S\) 每个前缀，计算其对答案的贡献。

把枚举出来的前缀 \(S[1\dots i]\) 看成已有的串，我们要插入一些字符使得它有 \(n\) 个 \(0\)，\(m\) 个 \(1\)，且 \(S[1\dots i]\) 为 \(T\) 的子序列，而 \(S[1\dots i + 1]\) 不是。问方案数（统计到最后答案的时候要乘长度）。

发现在 \(1\) 前插 \(0\) 和在 \(0\) 前插 \(1\) 都不会对合法性造成影响。判断 \(S[1\dots i]\) 是否为 \(T\) 的子序列可以看成一个匹配的过程，如果 \(T\) 当前的字符和 \(S\) 当前的字符不同就看 \(T\) 中的下一个字符（称匹配失效），如果相同，就都看下一个字符。\(T\) 中和 \(S\) 当前位不同的都会被略过，其实也就是最初那些“看成已有串”的字符被我们钦定为 \(T\) 中组成 \(S[1\dots i]\) 的字符，其他新插入的都是匹配失效的字符。

按理说我们在最后匹配完成的时候可以肆意放字符，但我们要求 \(S[1\dots i+1]\) 不是 \(T\) 的子序列，所以最后的位置只能放与 \(S_{i+1}\) 不同的字符。

把 \(0\) 和 \(1\) 单独考虑，根据乘法原理，最终方案数为两者方案数相乘。知道放的位置，知道放的个数，最后就是经典的不同小盒放同样的球可以为空的问题了。

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define IL inline
IL int _R() { int x; cin >> x; return x; }

const int N = 3e6;
const int maxN = N * 2 + 3;

const int mod = 2933256077;

int n, m;

int fc[maxN], ifc[maxN];
IL int ksm(int a, int b = mod - 2) {
  int res = 1;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}

string s;

int ans;

IL int C(int n, int m) {
  if (n < 0 || m < 0 || n < m) return 0;
  return fc[n] * ifc[m] % mod * ifc[n - m] % mod;
}
IL int F(int n, int m) { // n 个小球放 m 个盒中
  if (!n) return 1; // 注意放 0 个球到任意盒中也可以看做一个方案。
  return C(n + m - 1, m - 1);
}

signed main() {
  n = _R(), m = _R();

  fc[0] = 1;
  for (int i = 1; i <= n + m; i++)
    fc[i] = fc[i - 1] * i % mod;
  ifc[n + m] = ksm(fc[n + m]);
  for (int i = n + m - 1; i >= 0; i--)
    ifc[i] = ifc[i + 1] * (i + 1) % mod;

  cin >> s;
  s = '@' + s + '$';
  int c0 = 0, c1 = 0;
  for (int i = 1; i <= n + m; i++) {
    c0 += s[i] == '0', c1 += s[i] == '1';
    
    auto r1 = F(m - c0, c1 + (s[i + 1] == '0' ? 0 : 1));
    auto r2 = F(n - c1, c0 + (s[i + 1] == '1' ? 0 : 1));

    // cerr << r1 << ' ' << r2 << '\n';

    ans += i * r1 % mod * r2 % mod, ans %= mod;
  }

  cout << ans << '\n';
}