给定 N、S 和长度为 N 的序列 A,找到满足以下条件的序列 X 的个数对 998244353 取模后的结果:
- X 的每个元素都是正奇数
- ∑Xi=S
- 设 Yi=j=1∑iXj,那么对于所有 1≤i≤∣X∣,1≤j≤N 的 i,j,都满足 Yi=Aj
1≤N≤105
1≤A1<A2<⋯<AN<S≤1018
发现 Yi 的奇偶性和 i 的奇偶性相同,设 dpi 表示总和为 i 的 X 的个数,那么有转移:
dpi=⎩⎨⎧0≤j≤i−1,j≡i(mod2)∑dpj0∄Aj=i∃Aj=i
这样做时间复杂度是 O(S) 的,完美爆炸。考虑换一下 dp 的定义,设 dp0/1,i 为总和是奇数/偶数,并且小于等于 i 的方案数,那么有转移:
{dp0,i=dp0,i−1+[imod2=0∧∄Aj=i]dp1,i−1dp1,i=dp1,i−1+[imod2=1∧∄Aj=i]dp0,i−1
观察到对于所有满足 Aj<i<Aj+1 的 i,dp0/1,i 的转移是完全不受到 [∄Aj=i] 的影响的,这时有:
⎩⎪⎪⎨⎪⎪⎧[dp0,i−1,dp1,i−1]×[1,10,1]=[dp0,i,dp1,i][dp0,i−1,dp1,i−1]×[1,01,1]=[dp0,i,dp1,i]imod2=1imod2=0
考虑把两次转移合并,有:
⎩⎪⎪⎨⎪⎪⎧[dp0,i−2,dp1,i−2]×[1,11,2]=[dp0,i,dp1,i][dp0,i−2,dp1,i−2]×[2,11,1]=[dp0,i,dp1,i](i−2)mod2=1(i−2)mod2=0
那么可以枚举 j,手动做一次转移,用矩阵乘法做 Aj+1−Aj−1 次转移,再手动做一次转移即可。
时间复杂度 O(NlogS)。