枚举border集合

例题：CF gym100958 I

按照从小到大确定每种长度的前缀是否是一个 border，同时对于当前已经确定的 border $l_0,l_1,\cdots l_k$，统计长度为 $l_k$ 且以 $\{l_0,l_1,\cdots l_k\}$ 为 border 的字符串数。

新加入的一个 border $l_{k+1}$ 的时候，分如下情况讨论：

• $2l_k \le l_{k+1}$
  • 方案数为 $A^{l_{k+1}-2l_k}$，然后再减去大于 $l_k$ 的最小 border 不是 $l_{k+1}$、但是的 border 集合包含了 $l_{k+1}$ 的字符串数
• $2l_k > l_{k+1}$
  • 此时长度为 $l_k$ 的前缀和后缀会有重复的部分
  • 显然对于任意的 $2v > l_{k+1}$，如果 $v$ 是一个 border 那么 $2v-l_{k+1}$ 肯定也是
  • 而如果任意 border $v$，$2v-l_{k+1}$ 也是 border，那么长度为 $v$ 的前缀和后缀的重合部分显然是相同的
  • 所以如果对于任意的 $2v > l_{k+1}$，$v$ 是 border，都有 $2v-l_{k+1}$ 也是 border，方案数就是确定长度为 $l_k$ 的前缀的方案数；否则方案数为 $0$
  • 然后此时得到的方案数还要减去大于 $l_k$ 的最小 border 不是 $l_{k+1}$、但是的 border 集合包含了 $l_{k+1}$ 的字符串数

这个“大于 $l_k$ 的最小 border 不是 $l_{k+1}$、但是的 border 集合包含了 $l_{k+1}$ 的字符串数”可以通过从小到大枚举下一个 border 的长度来提前算得。

参考代码：

/*
S 的每一位分别表示长度为 i 的前缀是否为 border
ways 表示长度为 l_k 且以 {l_0,l_1, ... l_k} 为 border 的串的数量
R[i] 表示以 S 为 border 集合的前缀的、大于 L 的第一个 border 长度小于 x 的、长度为 x 的串的数量
*/
vector<int> getborder(ll S,int ways) {
	int L=m; while(L&&!(S>>L-1&1)) L--;
	vector<int> R(m+1);
	R[L]=ways;
	if(L==m) return (ans=(ans+1ll*ways*DP(S))%mod,R);
	for(int x=L+1;x<=m;++x) {
		int tmp=ways;
		if(L*2>x) {
			for(int j=L;j*2>x&&tmp;--j)
				if((S>>j-1&1)&&(!(S>>j*2-x-1&1)))
					tmp=0;
		}
		else tmp=1ll*tmp*pw[x-2*L]%mod;
		if(!tmp||!(tmp=(tmp-R[x]+mod)%mod)) continue;
		vector<int> y=getborder(S|1ll<<x-1,tmp);
		for(int i=x;i<=m;++i)
			R[i]=(R[i]+y[i])%mod;
	}
	return R;
}