我们定义 \(f_i\) 表示考虑 \(n=i\) 时的答案。
考虑怎样才能使得 Bob 存在一种出题方案使得 \(l\) 与 \(r\) 无法确定。假设包含点 \(i\) 的询问集合为 \(S_i\),那么当 \(S_l=S_r\) 时 \(l\) 与 \(r\) 无法确定。
发现:如果 \(a<b<c<d\),\(S_a=S_c\),\(S_b=S_d\),那么 \(S_a=S_b=S_c=S_d\)。也就是说,如果 \(a,c\) 无法确定,\(b,d\) 无法确定,那么 \(a,b\) 肯定也是无法确定的。
证明:\(S_a\) 肯定是 \(S_b\) 的子集。\(S_d\) 肯定是 \(S_a\) 的子集,因为 \(S_b=S_d\),那么 \(S_a=S_b=S_c=S_d\)。
定义区间 \([l,r]\) 为不可识别段,当且仅当 \(l\) 与 \(r\) 无法确定。特殊地,当 \(l=r\) 时,我们意义上认为 \(l\) 与他自己也无法确定(想象一下你不可能区分你自己和你自己),但实际上可以表示为 \(l\) 不与任何一个点产生关系。那么肯定存在一种划分方法,可以将 \([1,n]\) 不漏地划分为若干个互不相交的不可识别段。
证明:当两个不可识别段相交或包含时,可以使用上面的发现将其化为若干个互不相交的不可识别段。当一个点不与任何其它点产生关系时,可以将其自己作为一个不可识别段。
我们定义 \(g_{i,j}\) 表示将 \([1,i]\) 独立地划分为 \(j\) 个尽量长的不可识别段[1]、不考虑左右端点的询问方案数[2],这里的“独立地”表示每个询问只在不可识别段内,不会跨区间。
那么我们要计算跨区间的方案数。容易发现跨区间的询问的左端只能在区间的左端点,询问的右端只能在区间的右端点(如果询问端点在区间内部,一定不能保证某个 \(S_l=S_r\),不满足条件)。我们可以方便地将这 \(j\) 个区间缩为 \(j\) 个点。那么 \(g_{i,j}\times f_j\) 表示将 \([1,i]\) 划分为 \(j\) 个尽量长的不可识别段的询问方案数。这里乘上 \(f_j\) 是为了将这 \(j\) 个不可识别段区分,以保证不可识别段尽量长[3]。
考虑 \(g\) 数组的转移。我们假设 \([i+1,i+k]\) 是一个新的不可识别段,因为不考虑左右端点,只有 \(k-2\) 个数,那么有 \(2^{\binom{k-1}{2}}\) 种方案。
\[g_{i+k,j+1}\gets g_{i,j}\times2^{\binom{k-1}{2}} \]特殊地,当 \(i=j\) 时,因为每个不可识别段两端都是相同的,我们认为不存在不可识别的数,那么容易发现这就是答案。
但是因为转移需要用到 \(f_i\) 本身,所以我们考虑计算他的补集,再用 \(2^{\binom{i+1}{2}}\) 减去即可。
有:
\[\sum_{j=1}^{i}g_{i,j}\times f_j=2^{\binom{i+1}{2}} \]因为 \(g_{i,i}=1\)。
那么就有:
\[f_i=2^{\binom{i+1}{2}}-\sum_{j=1}^{i-1}g_{i,j}\times f_j \]时间复杂度 \(O(n^3)\)。
当钦定 \(S_a = S_b\) 与 \(S_c=S_d\) 时,也就是不可识别段为 \([a,b]\),\([c,d]\)。但是如果有 \(S_a=S_c\) 时,那么 \([a,d]\) 也可以作为不可识别段。
如果 \([a,d]\) 为不可识别段,那么它也会统计 \([a,b]\),\([c,d]\) 会统计的方案数,就算重了。
所以,当我们将 \([a,b]\),\([c,d]\) 作为不可识别段时,其实就包括一个隐含条件: \(S_a\neq S_c\)。
对于不可识别段 \([a,b]\)。考虑左右端点无非只有一种询问:询问 \([a,b]\)。而这个我们会在下面计算上。
在同一段数下,因为保证了每一个不可识别段尽量长,那么不可确定点对不会算重。举个例子,当 \(n = 6\),分段为 \([1,2,3],[4,5,6],[7,8]\),这里分段表示钦定了 \(S_1=S_3,S_4=S_6,S_7=S_8\),为了保证每一个不可识别段尽量长,那么 \(S_1\neq S_4\);如果我们不将这些不可识别段区分,变成 \(S_1=S_4\) 的话,就有 \(S_1=S_6\),\([1,2,3,4,5,6]\) 就是一个新的尽量长分段,不满足定义。