Analysis

瞎推了一波

显然, (A,B)中同为 (0) 的项没有用的, 且答案只与 (A,B)中同为(1)的数量, 以及 (A,B)不同的数量有关

注意到求解的问题与原串的顺序无关, 我们调换成一种符合自己的思维方式的序列

A:  111111100010001000100
B:  111111100000100010001
a:  1111111   1   1   1 
b:  1111111     1   1   1  
      n个         m对

这是初始的 (a,b)可选 交换点 的位置

定义一次交换为 : 选择一个未使用的交换点(a), 再选择一个未使用的交换点(b), 将他们match, 然后, 交换(A)中的对应位置

如图

a:  1  1  1  1     1   1   1               a:  1  0  1  1     1   1   1 
		                                          
         ------------               =>              ------------ 
                                                               
b:  1  1  1  1        1   1   1            b:  1  1  1  1        0   1   1
         n                m                         n                m

观察到

(1) (a) 中的 (1) 对应着 (A)中的 (1), (B)中的(0), (b) 中的 (1) 对应着 (A)中的 (0), (B)中的(1)

(2) (n)中的每个位置, 每个位置有两个交换点可选. (m) 中的位置, 每个位置仅有一个交换点可选

因此, 我们不可以选择 (n) 中的 (b) 交换点与 (m) 中的 (a) 交换点进行匹配. 否则会使 (a) 中的该位置变成 (1), 而该位置需要是 (0), 后续又没有交换点来跟其他位置交换, 永远不能合法

考虑被(match)的位置组成若干连通块. 因为操作是依次进行, 考虑连通块中的第一个操作

(1) (n - n) : 此时, 若被匹配的是同一位置. 连通块只有一条边. 否则, 两个位置各剩余了一个交换点, 一个 (a), 一个 (b). 此时:

这个 (a) 不能与 (m) 中的 (b) 连, 否则永远是 (0) (目前只剩一个交换点了)

这个 (b) 不能与 (m) 中的 (a) 连, 这个是之前观察的结果

因此, 只能继续和 (n) 内部连, 接着又有一对 (a,b), 又只能在内部连

因此, 第一步选择了n-n连, 则只能在n内组成连通块

注意到(A)中这些位置都是(1) , 排列顺序是可以任意的

(2) (m-m) : 由于位置均只有一个交换点, 连通块只有一条边

(3) (n- m) : 此时(m)中的点合法了, 但导致一个(n)中的位置变成了(0)

接着这个 (0) 可以在 (n) 被踢皮球传来传去

然后最后必须在 (m) 中的某个 (a) 结束, 即

a:  1  1  1  1     1   1   1               a:  1  1  1  0     1   1   1 
		                                                
               ------               =>                    ------ 
                                                               
b:  1  1  1  1        1   1   1            b:  1  1  1  1        0   1   1 
         n                m                         n                m

														  |
														  v

a:  0  0  0  0     1   1   1               a:  1  1  1  0     1   1   1 
		          /                                   
     -------------                  <=                 ------ 
    /                                                        
b:  1  0  0  0        0  1   1            b:  1  1  1  1        0   1   1 
        n                m                         n                m

注意, 上图是交换点的可用状态, 对应(A)中的(0) 从右往左一直被踢到了某个位置, 回归合法

第一步选择了n-m, 则只能在n中转一转, 然后回到m结束

Solution

因此, 一个连通块内的至多一对 (m) 中的点,

我们先用 (m!) 将 (m)中的点分成 (m)对, 钦定好m中的匹配方法

然后我们先不考虑只含 (n) 的连通块

考虑块内的排列方案数, 对于含 (m) 连通块, 若含有 (0) 个 (n) 中的点, 则方案数(=1)

否则, 方案数 (n)个点组成一条链, (n!)

考虑到最后要多项式系数把 (n)分入不同的连通块, 多项式系数把连通块插在一起

构造生成函数 $$F(i) = i! frac{1}{i!}frac{1}{(i+1)!}=frac{1}{(i+1)!}$$ 第一个阶乘是连通块内顺序, 第二个是把 (i) 分入不同连通块的多项式系数分母, (i+1) 是连通块大小, 算得是连通块插在一起的分母

那么答案为

[m! sum_{i=1}^n F^m(i) frac{n!}{(n-i)!} frac{(n+m)!}{(n-i)!}[(n-i)!]^2=m! sum_{i=1}^n F^m(i) ~n!~(n+m)! ]

剩下的随意排列, 随意组成连通块, 所以是阶乘的平方