求未被覆盖的区间长度即可

给定一只包含 $0\sim9$ 的字符串，求有多少对子串 $(S,T)$ 满足 $len(S)==len(T)$ 且 $S=T+1$ 在字符串上建立后缀自动机，记状态 $u$ 对应子串个数为 $cnt[u]$，递归遍历后缀自动机的每个状态，对每个状态 $u$ 枚举转移 $v_0=(u,0),v_1=(u,1)$, 则当前 $u$ 所对应的子串 $T$ 的贡献 $ans[u]$增加 $cnt[v_0]\times cnt[v_1]$，再设 $v_{09}=(v_0,9),v_{10}=(v_1,1)$，如果状态都存在，则继续累加贡献 $cnt[v_{09}]\times cnt[v_{10}]$，直到至少一个状态不存在。递归遍历后缀自动机会重复经过一个点多次，考虑拓扑排序一遍记录从起点出发到每个状态的路径数 $D[u]$ ，最后的答案即为 $\displaystyle \sum_{u=0}^{tot}D[u]\times ans[u]$

签到题

题目大意：n种物品每种有无数个，第i个物品的体积为$a_i$，求解选择物品总体积不超过m的方案数

此外，有k个限制，第i个限制形如第$b_i$个物品所选的数量二进制表示下从低到高第$c_i$位必须为0

首先，进行二进制分组，将$n$种物品拆分为$logm$组物品，第$i$组物品中有$n$种物品，第$j$种物品的体积为$a_j*2^i$，总共有$n*logm$个物品，然后可以进行$0/1$背包

设$F(i,j,b)$表示，做完了前$i$组物品，选了体积为$V$的物品，满足$j=\lfloor\frac{V}{2^i}\rfloor,b=[(V\ mod\ 2^i)>(M\ mod\ 2^i)]$

发现$i$的最大值约为$logm$，$j$的最大值约为$2*n$，$b$只有$0/1$两种取值

设$g(i,j)$为第$i$组物品，选择了体积为$j*2^i$物品的方案数 $$ g(i,j)=[x^j]\frac{\prod_{l=1}^n(1+x^{a_l})}{\prod_{(l,i)\in Lim}(1+x^{a_l})} $$ 分子可以利用分治NTT预处理，对于所有的$i$都适用

对于每一个限制来说，可以对分子做一次反向$0/1$背包来处理，复杂度为$O(n*k)$

设$B(x,y,z)=[x>y||(x==y\&\&z)]$

对于当前的$F(i,j,b)$，设$m_i$为$m$在二进制下第$i$位的值，可以向后转移贡献： $$ F(i,j,b)\times g(i,l)\rightarrow F(i+1,\lfloor\frac{j+l}{2}\rfloor,B((j+l)mod\ 2,m_i,b) $$ 可以枚举$i$和$b$，然后对$j$和$l$维度进行$NTT$卷积优化，再转移贡献，这部分复杂度为$O(nlognlogm)$

总复杂度为$O(nlog^2n+nk+nlognlogM)$

提前看了题解，于是摆了。主要是看队友切题。