set_counting

设有两个集合 \(A,B\subset\mathbb{N}\)，且 \(0\in A,1\in B,|A|=n,|B|=m\)。定义 \(A+B=\{x+y|x\in A,y\in B\}\)，若 \(A+B=[1,nm]\cap\mathbb{N}^{+}\)，则称 \((A,B)\) 是好的。问这样的集合对有多少个。

解：若 \(n=1\) 或 \(m=1\)，方案显然是唯一的。下面讨论 \(n>1\) 且 \(m>1\) 的情况：

若 \(2\notin B\)，那么必有 \(1\in A\)，否则 \(2\notin A+B\)，矛盾。这种情况下，我们把 \(A\) 中所有元素加 \(1\)，\(B\) 中所有元素减 \(1\) 即可（\(n,m\) 互换）。因此下面假定 \(1\in B,2\in B\)。

首先证明，对于一个固定的 \(B\)，至多只有一个 \(A\) 满足要求。不妨从小到大向 \(A\) 集合中填数，设 \(A\) 中一开始只有 \(0\)。考虑当前 \(A+B\) 中的所有元素，如果 \(\{1,2,\cdots,nm\}\subset A+B\)，那么填数终止；否则考虑 \(\{1,2,\cdots,nm\}\) 中最小的不在 \(A+B\) 中的元素，设为 \(x\)，那么我们必须把 \(x-1\) 填进 \(A\)。反证法，假设 \(x-1\notin A\)，那么必然存在某个 \(t>1,t\in B\)，我们要把 \(x-t\) 填进 \(A\)。这样一来，\(x-t+1\) 就有两种表示方法（填 \(x-t\) 之前的一种，和 \((x-t)+(1)\) 的一种），从而最后的集合对不可能是合法的。这样的填法说明了 \(A\) 的取值是唯一的。

接下来的问题就变成了，对于怎样的集合 \(B\)，它恰好有一个 \(A\) 是合法的。

给出一个整数 \(t\)，和两个长度为 \(l\) 的数列 \(\{x_{i}\},\{y_{i}\}\)，其中 \(t>1\)，\(x_{i}>1(1\le i\le l)\)，\(y_{i}>1(1\le i<l)\)，\(y_{l}\ge1\)，\(\displaystyle \prod_{i=1}^{l}x_{i}=n\)，\(\displaystyle t\prod_{i=1}^{l}y_{i}=m\)。我们递归地定义 \(A\) 和 \(B\)，设 \(A_{0}=\{0\}\)，\(B_{0}=\{1,2,\cdots,t\}\)，\(\displaystyle u_{i}=t\prod_{j=1}^{i-1}x_{j}\prod_{j=1}^{i-1}y_{j}\)，\(\displaystyle v_{i}=t\prod_{j=1}^{i}x_{j}\prod_{j=1}^{i-1}y_{j}\)，\(A_{i}=A_{i-1}+\{0,u_{i},2u_{i},\cdots,(x_{i}-1)u_{i}\}\)，\(B_{i}=B_{i-1}+\{0,v_{i},2v_{i},\cdots,(y_{i}-1)v_{i}\}\)，\(A=A_{l},B=B_{l}\)。容易发现，这样的一组 \((A,B)\) 是好的，且对于不同的参数 \(t,x,y\)，生成的 \((A,B)\) 互不相同。

我们从构造上式的角度出发，说明好的 \((A,B)\) 必然满足上面的形式。由于 \(t+1\notin B\)，因此有 \(t\in A\)。可得 \(t+2,\cdots,2t\notin B\)，否则 \(t+i=(0)+(t+i)=(t)+(i)\)。同理若 \(2t+1\notin B\)，则有 \(2t\in A,2t+1,\cdots,3t\notin B\)。设 \(t+1,\cdots,x_{1}t\notin B\)，那么 \(0,t,\cdots,(x_{i}-1)t\in A\)。接下来，若 \(x_{1}t+1\in B\)，那么就有 \([x_{1}t+u\in B]=[u\in B](1\le u\le x_{1}t)\)，另外还有 \(x_{1}t\notin A\)。如此循环往复地构造下去，就能得到上面的结论。

接下来就比较简单了，选择 \(t,x,y\) 的过程，相当于将 \(n,m\) 分解为若干个数的积。\(2\in B\) 部分的答案为 \(\displaystyle f(n,m)=\sum_{i=1}^{+\infty}g_{i}(n)\left(g_{i}(m)+g_{i+1}(m)\right)\)，其中 \(g_{i}(n)\) 表示将 \(n\) 分解为 \(i\) 个大于 \(1\) 的数的乘积的方案数（有序）。最终答案为 \(f(n,m)+f(m,n)\)。