统计 $[L,R]$ 之间的数的拆分方案的总和，可以变成统计有多少个数 $x$，满足 $L\le x + \operatorname{rev}x \le R$，按照套路变成 $[0,R]-[0,L-1]$，下面考虑如何计算 $[0,R]$ 的方案数。

令 $y = x + \operatorname{rev}x$，设 $x$ 的位数为 $n$，那么 $y\lt 2K^n$。

若 $R\ge 2K^n$ 可以直接计算方案，下面考虑 $2K^{n-1}\le R \lt 2K^n$ 的情况。

若 $R$ 有 $n+1$ 位，则第 $n+1$ 位 $a_{n+1}=1$，将 $a_n$ 变成 $a_n+K$，当成 $n$ 位数看待。

若不考虑加法进位，则 $y$ 的第 $i$ 位和第 $n-i+1$ 位是 $x$ 的第 $i$ 位和第 $n-i+1$ 位相加，即 $y_i=y_{n-i+1}=x_i+x_{n-i+1}$，$0\le y_i\le 2K-2$。

要求是 $y\le R=\overline{a_1 a_2\cdots a_n}$，考虑从两边往中间依次确定 $y_i$，最后在中间拼成完整的数。

假设我们现在已经确定了 $[1,l-1]$ 和 $[r+1,n]$（满足 $r=n-l+1$），要确定 $y_l$ 和 $y_r$。

首先要保证 $\overline{y_r y_{r+1}\cdots y_n}\le \overline{a_r a_{r+1}\cdots a_n}$，因此需要记录 $S=\overline{a_{r+1}\cdots a_n}-\overline{ y_{r+1}\cdots y_n}$。若 $S\ge 2$，那么 $x_l\sim x_r$ 随便填都满足要求，可以直接统计答案。所以我们只要考虑 $S\in \{0,1\}$ 的情况。

如果 $l+1\ge r$，那么我们已经拼出了完整的数，如果 $\overline{y_r y_{r+1}\cdots y_n}=\overline{a_r a_{r+1}\cdots a_n}$，就需要比较 $\overline{y_1 y_2\cdots y_l}$ 和 $\overline{a_1 a_2\cdots a_l}$ 的大小关系，因此需要记录 $y_{l-1}$ 是否进位，以及 $\overline{y_1 y_2\cdots y_{l-1}}$ 和 $\overline{a_1 a_2\cdots a_{l-1}}$ 的大小关系。

采用记忆化搜索，状态数是 $O(n)$ 的。 转移时枚举 $y_l=y_r=w$，$O(1)$ 计算出 $x_l+x_r=w$ 的方案数，时间复杂度 $O(nK)$。

记 $T=\overline{a_r a_{r+1}\cdots a_n}-\overline{ 0y_{r+1}\cdots y_n}$，若 $y_r \le T-2$，则剩余位置随便填，可以直接计算出答案。因此转移只需要分为 $y_r\le T-2,y_r=T-1,y_r=T$ 这 $3$ 种情况。可以通过容斥 $O(1)$ 计算出 $x_l+x_r\le T-2$ 的方案数，时间复杂度优化至 $O(n)$。

代码不算长，但细节比较多，下面是需要注意的一些点：

• 因为要求 $x$ 不能有前导 $0$ ，$y_1$ 和 $y_n$ 的转移要特殊处理。
• 中间合并时要根据 $n$ 的奇偶性分类讨论。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,P=20110521;
int K,n,a[N],ans,pw[N],va[N],f[N][2][2][2];
inline int md(int x){
	return x>=P?x-P:x;
}
inline void Add(int &x,int y){
	if((x+=y)>=P)x-=P;
}
int S2(int x){
	return 1ll*x*(x+1)/2%P;
}
int calc(int l,int w){
	int res=w+1;
	if(w>=K)Add(res,P-2*(w-K+1));
	if(l==1&&w<K)Add(res,P-2+(!w));
	return res;
}
int calc2(int l,int w){
	int res=S2(w+1);
	if(w>=K)Add(res,P-md(2*S2(w+1-K)));
	if(l==1)Add(res,P-2*min(K-1,w)-1);
	return res;
}
int DP(int l,int r,int vl,int vr,bool t){
	if(l>r)return (vr>vl||vr==vl&&!t)?1:0;
	if(~f[l][vl][vr][t])return f[l][vl][vr][t];
	int &res=f[l][vl][vr][t];
	res=0;
	if(l==r){
		int wr=vr*K+a[l]-vl-t;
		if(wr<0)return res=0;
		return res=wr/2+(l>1);
	}
	int wr=vr*K+a[r];
	if(wr>1)res=1ll*pw[r-l-1]*calc2(l,wr-2)%P;
	for(int i=max(0,wr-1);i<=wr;++i){
		int u=(i+vl)%K,v=(i+vl)/K,w=calc(l,i);
		if(w)Add(res,1ll*w*DP(l+1,r-1,v,wr-i,(u>a[l]||u==a[l]&&t))%P);
	}
	return res;
}
int solve(){
	if(!n)return 0;
	if(n==1)return a[1]/2;
	int res=0;
	memset(f,-1,sizeof(f));
	if(a[n]==1)return md(va[n-2]+DP(1,n-1,0,1,0));
	else return md(va[n-1]+DP(1,n,0,0,0));
}
int main(){
	scanf("%d%d",&K,&n);
	va[1]=K-1,pw[0]=1,pw[1]=K;
	for(int i=2;i<N;++i)pw[i]=1ll*pw[i-1]*K%P,va[i]=1ll*va[i-1]*K%P;
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=n;++i){
		if(!a[i])a[i]=K-1;
		else {--a[i];break;}
	}
	if(!a[n])--n;
	ans=md(P-solve());
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	Add(ans,solve());
	printf("%d\n",ans);
	return 0;
}