模拟赛 数根 题解
题意：
对于一个\(B\)进制数\(x\)定义它的数根为把所有位上的数加在一起的结果。
给出一个长度为\(n\)的\(B\)进制串\(s\)，\(m\)次询问每次给定一个集合\(A\)和一个数\(x\)，计算有多少个\(s[l ... r]\)可以通过将至多一个字符更改为\(A\)中的元素使得数根为\(x\)。
\(n,m\leq 2^{20},B<=16\)，时间限制8s。
首先，考虑快速求一个数的数根\(f(x)\)。
设\(B\)进制数\(x=\sum_{i=0}^{n}a_iB^i\)，\(y=\sum_{i=0}^{n}a_i\)。那么\(y-x=\sum_{i=0}^{n}a_i(B^i-1)\)。由等比数列求和公式，\(B-1|B^i-1\)。因此\(x\equiv y \mod B-1\)，即\(x\equiv f(x) \mod B-1\)。
那么维护总和模\(B-1\)为\(x\)的区间数量，就可以处理不进行修改的情况。
对于修改操作，假设一个区间原来的总和模\(B-1\)为\(y\)，那么只要把其中的一个数字增加\(t=x-y\)，就能满足条件。
设给出的集合为\(A\)，再设\(C=\{x|x+t\in A\}\)，那么只要这个总和为\(y\)的区间内元素的集合与\(C\)的交集不为空，这个区间就满足条件。
我们只要对于所有\(0\leq y
对于这个子问题，我们可以枚举右端点\(r\)，并对于每个\(x\)维护从\(r\)往左第一个等于\(x\)的位置。这些位置把序列分为了若干段，每一段的\(S\)都是相等的。
对于每一段分别求即可。
这个使用前缀和即可优化至\(O(nB^2)\)。
现在我们已经解决了大部分情况，但是还有几个细节：
首先，对于\(x=0\)的询问，要求区间内都是0。这个我们可以维护全是\(0\)的以及只有一个非零位置的区间个数来计算。
对于\(x=B-1\)的询问，需要考虑把所有数字都改为0的情况。
若\(B-1\notin A\)，那么全是0的需要减去。同时若\(0\in A\)，那么长度为1的元素不为0的区间应当减去。
并且对于只有一个非零\(x\)的长度至少为2的区间，若\(B-1-x \notin A\)，那么这个也得减去。
总时间复杂度为\(O((n+m)*B^2)\)。能过。
参考代码：
#include
#include
#define ll long long
char zf[1048580];int ch[300],su[1048580];
int sz[1048580],la[16],he[16][1048580];
void swap(int &a,int &b)
{
int t=a;a=b;b=t;
}
void fmt(ll sz[32768],int B)
{
for(int j=0;j