数位dp | Reincarnation

不问来处，不寻去路。

基于位的计数问题

观前提醒

请保证你在阅读此文前已经掌握了基本的动态规划算法以及一些数论的基础知识。如果已经掌握了基本的数位，则可以直接开始阅读例题，跳过本节。

基于位的计数问题，指的是求出中满足某一种特殊性质的数的个数，而这个往往会很大，例如等等，这意味着我们不能在线性时间内解决这个问题，一般需要做到的时间。

一般有预处理式实现和记忆化搜索两种实现方式。

在实现中，我们都已下面这个题目作为模板：

题目简介

题目名称：数

题目来源：四川省选具体不详

评测链接：https://www.luogu.com.cn/problem/P2657

形式化题意：求区间内所有数满足的个数。例如：等等。

数据范围：

预处理实现

预处理实现的精髓在于，我们需要在一定是内求出所有可能成为询问的状态的贡献记录出，并在询问中挑选状态进行答案贡献。口语化地讲，我先把所有的可能都给你计算出来，然后你问我什么，我就答什么的感觉，然后对两部分的时间复杂度进行一个平衡规划。

拿上题而言，我们记录的状态应当表示为表示第位是的个数，也就是所有 $个$ 中满足条件的个数。然后通过基本的递推得到所有的结果。

这一部分非常简单：

参考实现

inline void init()
{
    for(int i=0;i<=9;++i) Dp[1][i]=1;
    for(int i=2;i<=10;++i) for(int j=0;j<=9;++j)
        for(int l=0;l<=9;++l) if(underAbs(l-j)>=2)
            Dp[i][l]+=Dp[i-1][j]; //这一位填l，上一位填j
}

设，则时间复杂度不会超过。

但难就难在我们应该怎么挑选答案。利用差分思想，答案可以表示为，证明显而易见。

那我们如果现在要求，就需要进行分类讨论。

为了方便，我们设，即的第位表示为。

~~根据数学常识~~，我们知道，可以拆分为和两个部分，这意味着，在没有最高位限制时，我们的答案贡献应当是全局性的，这样的话，我们就可以利用预处理出的对答案进行贡献。而根据递推的思想，通过拆位，我们可以把拆分成众多个全局性贡献的部分和一个被位数限制的部分，对于这个限制部分，实际上就是，也就是对的每一位都要进行限制，从而更新答案。

参考实现

inline int solve(int x)
{
    if(!x) return 0;
    std::vector<int>Nums;
    Nums.clear();
    int n=x,res=0;
    while(n) Nums.push_back(n%10),n/=10;
    int last=-2;
    for(int i=Nums.size()-1;i>=0;--i)
    {
        int x=Nums[i];
        for(int j=i==Nums.size()-1;j<x;++j)
            if(std::abs(j-last)>=2) res+=Dp[i+1][j];
        if(std::abs(x-last)>=2) last=x;
        else break;
        if(!i) ++res;
    }//限制位贡献
    for(int i=Nums.size()-2;i>=0;--i)
        for(int j=1;j<=9;++j)
            res+=Dp[i+1][j];//全局性贡献
    return res;
}
//int main()
//return solve(r)-solve(l-1);

看起来很迷惑？觉得这份代码实现得难以理解？~~我也觉得~~。所以就有了更为浅显易懂的记忆化式数位。

记忆化搜索

一般的状态分为三部分：，表示，当前最高位是位，根据题目而定，是所限制的状态，可能是一个，可能是多个。表示当前计算是否超过了限定区间。

这里不会被预处理所限制（因为根本就没有预处理），所以至上从下或是反向枚举都是没有问题的，笔者更习惯自高位至低位枚举，这样对的限制理解更容易一些。

参考实现

int Dfs(int pos,int lst,bool limit,bool _0)
{
	if(!pos) return 1;
	if(~Dp[pos][lst][limit][_0]) return Dp[pos][lst][limit][_0];
	int num=limit?Nums[pos]:9,ret=0;
	for(int i=0;i<=num;++i)
	{
		if(!_0) ret+=Dfs(pos-1,i,limit&(i==num),_0|(i!=0));
		else if(abs(i-lst)>=2) ret+=Dfs(pos-1,i,limit&(i==num),_0|(i!=0));
	}
	return Dp[pos][lst][limit][_0]=ret;
}
inline int solve(int x)
{
	if(!x) return 0;
	std::memset(Dp,-1,sizeof(Dp));
	int ret=0;
	for(Len=0;x;x/=10) Nums[++Len]=x%10;
	for(int i=0;i<=Nums[Len];++i) ret+=Dfs(Len-1,i,(i==Nums[Len]),i!=0);
	return ret;
}

对于两者的比较的话，个人猜测，对于预处理式计数，可能在多组询问上会体现优势，反之，单组询问记忆化会显得更加快速。

例题

数位与状态压缩

题目简介

题目名称：

题目来源：

评测链接：https://www.luogu.com.cn/problem/P9092
评测链接：https://sio2.mimuw.edu.pl/c/pa-2020-1/p/lic/

形式化题意：求内所有的数满足能被其位上的所有数整除，显然，中不能存在。

数据范围：

显然的数位。

对于每一位，肯定都是，所以一定只有种除数，可以考虑一个状态压缩的过程，记录当前状态下某一个数是否存在过，然后在最后进行判定，但是这样下来的空间复杂度为，显然是过不了的，所以考虑一点优化。

如果对于每一个除数都记录一个其模数显然是赘余的，因为如果我们已经知道的下的余数，那么的余数显然是也知道了的，同理，也存在这样的关系。所以，实际上我们可以仅仅通过记录的余数即可知道所有的模数。这样下来，空间复杂度可以优化到，因为是没有必要状压的。

当然，因为只能出现在前导部分，所以还需要加上和判的部分。

AC Code

// ----- Eternally question-----
// Problem: P9092 [PA2020] Liczba Potyczkowa
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9092
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// Written by: Eternity
// Time: 2023-02-27 21:38:18
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=19,MAXS=1<<8|10,MAXNUM=2520;
const int Mod=2520;
ll Dp[MAXN][MAXS][MAXNUM][2][2];
int Nums[20],Len;
ll ql,qr;
//pos,state(2~9),mod 7,8,9
int gcd(int a,int b)
{ return !b?a:gcd(b,a%b); }
inline int lcm(int a,int b)
{ return a*b/gcd(a,b); }
ll dfs(int pos,int state,int mod,bool limit,bool _0)
{
	if(!~pos)
	{
		int _lc=1;
		for(int i=2;i<=9;++i) if(state>>(i-2)&1) _lc=lcm(_lc,i);
		return mod%_lc==0;
	}
	if(~Dp[pos][state][mod][limit][_0]) return Dp[pos][state][mod][limit][_0];
	ll ret=0;int st=_0?1:0,num=limit?Nums[pos]:9;
	for(int i=st;i<=num;++i)
	{
		int nxd=(mod*10+i)%Mod,_st=state;
		if(i>1) _st|=1<<(i-2);
		ret+=dfs(pos-1,_st,nxd,limit&(i==num),_0|(i>0));
	}
	return Dp[pos][state][mod][limit][_0]=ret;
}
inline ll solve(ll x)
{
	if(!x) return 0;
	std::memset(Dp,-1,sizeof(Dp));
	ll ret=0;
	for(Len=0;x;x/=10) Nums[Len++]=x%10;
	ret=dfs(Len-1,0,0,1,0);
	return ret;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(ql,qr);
	int delta=(ql==1);
	write(solve(qr)-solve(ql-1)-delta);
	return 0;
}
/*

*/

不基于限制的记忆化

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/55/D

形式化题意：求内所有的数满足能被其位上的所有非数整除。多测。

数据范围：

容易发现，这道题与上一道题是极其类似的，但扩大了数据范围，且有多测，在空间上也进行了一定的限制（只有了），所以很可惜，上面的代码就并不能通过这道题了，我们需要进行一定的调整，发现时间复杂度的瓶颈在于每一次询问上的 std::memset，如果能够在多组询问中只进行一次清空，则就有过的可能。

然后我们考虑 std::memset 的实质，那就是每一组询问下的不一致，所以我们每一次都需要重置，那么，我们考虑把的记忆化给去掉，也就是舍去一部分记忆化的可能，而换取多测中答案一致的结果。而我们每一次提取记忆化的时候，也必须要保证不在的限制范围内。

~~虽然我觉得平时可能大多数人就是这么写的。~~

AC Code

// ----- Eternally question-----
// Problem: D. Beautiful numbers
// Contest: Codeforces - Codeforces Beta Round #51
// URL: https://codeforces.com/problemset/problem/55/D
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// Written by: Eternity
// Time: 2023-03-02 16:38:55
// ----- Endless solution-------

#pragma GCC optimize("O2")
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=20,MAXS=1<<8,MAXNUM=2520;
const int Mod=2520;
int Test,Len,Nums[MAXN];
ll ql,qr,Dp[MAXN][MAXS][MAXNUM];
ll Dfs(int pos,int state,int md,bool limit)
{
	if(!pos)
	{
		for(int i=2;i<=9;++i)
			if((state>>(i-2)&1)&&(md%i)) return 0;
		return 1;
	}
	if(!limit&&(~Dp[pos][state][md])) return Dp[pos][state][md];
	int num=limit?Nums[pos]:9;ll ret=0;
	for(int i=0;i<=num;++i)
	{
		if(i<2) ret+=Dfs(pos-1,state,(md*10+i)%Mod,limit&(i==num));
		else ret+=Dfs(pos-1,state|(1<<(i-2)),(md*10+i)%Mod,limit&(i==num));
	}
	if(!limit) Dp[pos][state][md]=ret;
	// pre.push_back((Node){pos,state,md,limit});
	return ret;
}
inline ll solve(ll x)
{
	if(!x) return 0;
	ll ret=0;
	// std::memset(Dp,-1,sizeof(Dp));
	// for(auto x:pre) Dp[x.a][x.b][x.c][x.d]=-1;
	// pre.clear();
	for(Len=0;x;x/=10) Nums[++Len]=x%10;
	for(int i=0;i<=Nums[Len];++i)
	{
		if(i<2) ret+=Dfs(Len-1,0,i,i==Nums[Len]);
		else ret+=Dfs(Len-1,1<<(i-2),i,i==Nums[Len]);
	}
	return ret;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	std::memset(Dp,-1,sizeof(Dp));
	while(Test--)
	{
		read(ql,qr);
		write(solve(qr)-solve(ql-1)-(ql==1),'\n');
	}
	return 0;
}
/*

*/

这道题还有一个极其卡常（）的恶心版（代码长度不超过），将状压的优化掉，记录为仅有的种情况，也是进行多测下的预处理，就可以通过该加强版。

加强版链接：https://www.spoj.com/problems/JZPEXT/

数位与回文

题目简介

题目名称：

题目来源：

评测链接：https://www.luogu.com.cn/problem/P6754

形式化题意：求出中所有的满足中不存在长度大于的回文子串的个数。

数据范围：

考虑一个回文串拥有什么性质，显而易见的，一个回文串的中心子串也是回文串，具体来讲的子串也是子串，所以，如果存在一个回文串，那一定存在其中三个位置满足或，所以我们只需要记录上一个位置的数和上上个位置的数即可。注意前导。

~~求成回文串个数调半天QAQ~~。虽然不知道为什么我每次写数位时只要总得出点错。

AC Code

// ----- Eternally question-----
// Problem: P6754 [BalticOI 2013 Day1] Palindrome-Free Numbers
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6754
// Memory Limit: 128 MB
// Time Limit: 100000 ms
// Written by: Eternity
// Time: 2023-03-06 15:30:29
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=20,MAXS=10;
ll ql,qr,Dp[MAXN][MAXS][MAXS][2];
int Nums[MAXN],Len;
ll Dfs(int pos,int fr,int sc,bool ok,bool limit,bool _0)
{
	if(!pos) return ok;
	if((~fr)&&(~sc)&&(!limit)&&(~Dp[pos][fr][sc][ok])) return Dp[pos][fr][sc][ok];
	ll ret=0;int num=limit?Nums[pos]:9;
	for(int i=0;i<=num;++i)
	{
		if(!_0)
		{
			if(i) ret+=Dfs(pos-1,i,fr,ok,limit&(i==num),1);
			else ret+=Dfs(pos-1,fr,sc,ok,limit&(i==num),0);
		}
		else ret+=Dfs(pos-1,i,fr,ok|(i==sc)|(i==fr),limit&(i==num),1);
	}
	if((~fr)&&(~sc)&&(!limit)) Dp[pos][fr][sc][ok]=ret;
	return ret;
}
inline ll solve(ll x)
{
	if(!~x) return 0;
	if(!x) return 0;
	ll ret=0;
	for(Len=0;x;x/=10) Nums[++Len]=x%10;
	ret+=Dfs(Len-1,-1,-1,0,0,0);
	for(int i=1;i<=Nums[Len];++i) ret+=Dfs(Len-1,i,-1,0,i==Nums[Len],1);
	return ret;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(ql,qr);
	std::memset(Dp,-1,sizeof(Dp));
	write((qr-ql+1)-(solve(qr)-solve(ql-1)),'\n');
	return 0;
}
/*

*/

稍暴力思想

题目简介

题目名称：同类分布
题目来源：安徽省选具体不详

评测链接：https://www.luogu.com.cn/problem/P4127

形式化题意：求出中所有的使得其各位数的和能够整除。

数据范围：

容易发现，当我们在枚举数位的时候，如果记录当前模数，模数也是在变化的，这让我们这个思路并不能成功实现，但容易发现，模数的范围在内，是一个勉强可接受的常数范围内，所以我们可以尝试暴力枚举模数，并在搜索结束的时候，我们既要判断当前数是否能被我们钦定的当前模数整除，还要判断当前个位数和是否等于钦定模数。

AC Code

// ----- Eternally question-----
// Problem: P4127 [AHOI2009]同类分布
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4127
// Memory Limit: 125 MB
// Time Limit: 3000 ms
// Written by: Eternity
// Time: 2023-03-08 11:39:32
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=20,MAXMOD=180;
ll ql,qr,Dp[MAXN][MAXMOD][MAXMOD],Mod;
int Nums[MAXN],Len;
ll Dfs(int pos,int sum,int md,bool limit)
{
	if(sum>Mod) return 0;
	if(sum+9*pos<Mod) return 0;
	if(!pos) return sum==Mod&&(!md);
	if(!limit&&~Dp[pos][sum][md]) return Dp[pos][sum][md];
	ll ret=0;int num=limit?Nums[pos]:9;
	for(int i=0;i<=num&&i+sum<=Mod;++i) ret+=Dfs(pos-1,sum+i,(md*10+i)%Mod,limit&(i==num));
	if(!limit) Dp[pos][sum][md]=ret;
	return ret;
}
inline ll solve(ll x)
{
	if(!x) return 0;
	ll ret=0;
	for(Len=0;x;x/=10) Nums[++Len]=x%10;
	for(Mod=1;Mod<=Len*9;++Mod)
	{
		std::memset(Dp,-1,sizeof(Dp));
		ret+=Dfs(Len,0,0,1);
	}
	return ret;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(ql,qr);
	write(solve(qr)-solve(ql-1));
	return 0;
}
/*

*/

数位与平衡规划

题目简介

题目名称：

题目来源：

评测链接：https://www.luogu.com.cn/problem/P6371

形式化题意：求出中的倍数的个数。

数据范围：

时空限制：

我们以前做过这类题，令表示当前最高第位且模余数为，但显然在的时候是没法做的。但是呢，当很大的时候，我们可以确保的倍数个数不会很多（不超过个）。

所以，我们考虑一手平衡规划，当时，我们考虑用上述的数位，而当时，我们则进行暴力计算。因为有极小的空间限制，所以取到就差不多了。

容易发现数位中最令人头疼的就是关于前导和限制记忆化的问题了，~~相信厉害的读者应该不会像我一样弄得晕头转向。~~

AC Code

// ----- Eternally question-----
// Problem: P6371 [COCI2006-2007#6] V
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6371
// Memory Limit: 31 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-03-06 16:25:14
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=13,MAXX=1e5+10;
ll X,ql,qr;
namespace Below
{
	ll Dp[MAXN][MAXX][2];
	char Str[MAXN];
	int Nums[MAXN],Len;
	bool Vis[MAXN];
	ll Dfs(int pos,int lf,bool limit,bool _0)
	{
		if(!pos) return !lf&&_0;
		if(!limit&&~Dp[pos][lf][_0]) return Dp[pos][lf][_0];
		ll ret=0;int num=limit?Nums[pos]:9;
		for(int i=1;i<=num;++i) if(Vis[i]) ret+=Dfs(pos-1,(lf*10+i)%X,limit&(i==num),_0|(i!=0));
		if(!_0) ret+=Dfs(pos-1,0,limit&(Nums[pos]==0),0);
		else if(Vis[0]) ret+=Dfs(pos-1,lf*10%X,limit&(Nums[pos]==0),1);
		if(!limit) Dp[pos][lf][_0]=ret;
		return ret;
	}
	inline ll solve(ll x)
	{
		if(!x) return 0;
		ll ret=0;
		for(Len=0;x;x/=10) Nums[++Len]=x%10;
		ret+=Dfs(Len,0,1,0);
		return ret;
	}
	inline bool main()
	{
		std::memset(Vis,0,sizeof(Vis));
		std::memset(Dp,-1,sizeof(Dp));
		scanf("%s",Str);
		int N=std::strlen(Str);
		for(int i=0;i<N;++i) Vis[Str[i]-'0']=1;
		write(solve(qr)-solve(ql-1),'\n');
		return 0;
	}
};
namespace Beyond
{
	char Str[MAXN];
	bool Vis[MAXN];
	inline bool main()
	{
		scanf("%s",Str);
		int N=std::strlen(Str);
		for(int i=0;i<N;++i) Vis[Str[i]-'0']=1;
		ll ans=0;
		for(ll i=X;i<=qr;i+=X)
			if(i>=ql)
			{
				ll x=i;bool ok=1;
				while(x)
				{
					if(!Vis[x%10]){ ok=0;break; }
					x/=10;
				}
				ans+=ok;
			}
		write(ans);
		return 0;
	}
};
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(X,ql,qr);
	if(X<=1e5) return Below::main();
	return Beyond::main();
	return 0;
}
/*

*/

数位与回文 II

题目简介

题目名称：

题目来源：

评测链接：https://www.spoj.com/problems/MYQ10/

形式化题意：求出中所有的数，满足无论左右翻转，上下反转，都是原数的个数。请注意，这里的反转指的是完全反转，而不是数字交换位置。

数据范围：

容易发现，现在的并不是某一段是回文串，而是整个都是回文串，所以那个记录上两位的做法在这里是不适用的。我们现在需要记录整个数字串的状态，但用于记忆化肯定是行不通的。

我们考虑在记忆化的过程中记录一个表示第位数是多少，如果对于我们当前的搜索已经处于了整个数字串的后半部分，则我们就需要与前半部分进行比较，判断是否有，否则就不是一个回文串。

而显然的，有前导的情况时，我们并不知道真正的数字串究竟是从多少开始的。所以我们在搜索同时，需要一个参数表示我们的前导是在第位结束，也就是我们的字符串最高位是。这也就是我们比对回文串的终点。

而上下翻转也存在要求，所以数字串中只能出现，容易发现答案不超过，合法答案又少之又少，所以 __int128_t 或者 long long 都可以过。

AC Code

// ----- Eternally question-----
// Problem: MYQ10 - Mirror Number
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP10649
// Memory Limit: 1 MB
// Time Limit: 1830 ms
// Written by: Eternity
// Time: 2023-03-13 19:45:05
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using int128=__int128_t;
const int MAXN=46,MAXS=11;
int Test;
int Nums[MAXN],Len,Pre[MAXN];
int128 Dp[MAXN][MAXN][2];
int128 Dfs(int pos,int st,bool limit,bool ok)
{
	if(!~pos) return ok;
	if(!limit&&~Dp[pos][st][ok]) return Dp[pos][st][ok];
	int128 ret=0;int num=limit?Nums[pos]:9;
	for(int i=0;i<=num;++i)
	{
		if(i!=0&&i!=1&&i!=8) continue;
		Pre[pos]=i;
		if(st==pos&&!i) ret+=Dfs(pos-1,st-1,limit&(i==num),ok);
		else if(ok&&pos<(st+1)/2) ret+=Dfs(pos-1,st,limit&(i==num),i==Pre[st-pos]);
		else ret+=Dfs(pos-1,st,limit&(i==num),ok);
	}
	if(!limit) Dp[pos][st][ok]=ret;
	return ret;
}
char Str[MAXN];
inline int check()
{
	for(int i=0;i<Len;++i)
	{
		if(Nums[i]!=0&&Nums[i]!=1&&Nums[i]!=8) return 0;
		if(Nums[i]!=Nums[Len-i-1]) return 0;
	}
	return 1;
}
inline int128 solve(int op)
{
	// if(!op) write("L:",' ');
	// else write("R:",' ');
	scanf("%s",Str);
	Len=std::strlen(Str);
	for(int i=0;i<Len;++i) Nums[i]=Str[Len-i-1]-'0';
	// for(int i=Len;i;--i) write(Nums[i]);
	// puts("");
	int delta=0;
	if(!op) delta=check();
	return Dfs(Len-1,Len-1,1,1)-delta;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	std::memset(Dp,-1,sizeof(Dp));
	while(Test--)
	{
		ll retl=solve(0);
		ll retr=solve(1);
		write(retr-retl,'\n');
	}
	return 0;
}
/*

*/

数位与求和

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/1073/E

形式化题意：求出中所有的的和，满足由至多种数字组成（不计前导）。

数据范围：

容易发现不定，所以没法在 Dfs 种传参具体数字，所以考虑状压，可以解决数数的问题。

但我们要求的是求和，当我们在第位填了时，答案应当加上，但肯定不止个。我们还需要知道当前已经统计了的个数。我们设下一层的个数为，当前层答案为，当然这个是个泛指。我们可以得到以下式子：

$\begin{align} \nonumber f[pos][s]&=10^{pos}x\sum{cnt[pos-1][s']}+\sum{f[pos][s']} \\ \nonumber cnt[pos][s]&=\sum cnt[pos-1][s'] \end{align}$

然后就是日常的记忆化和转移了。建议的是，如果时空充裕，其实可以把和前导给记忆化掉。

AC Code

// ----- Eternally question-----
// Problem: E. Segment Sum
// Contest: Codeforces - Educational Codeforces Round 53 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/1073/E
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-03-09 14:41:36
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
#define popcount(x) __builtin_popcount(x)
const int MAXN=20,MAXS=1<<10|10;
const int Mod=998244353;
ll ql,qr;
int K,Nums[MAXN],Len,Pw[MAXN];
struct Node
{
	int cnt,val;
	Node(){}
	Node(int c,int v):cnt(c),val(v){}
	inline void clear(){ cnt=val=0; }
	inline bool check(){ return ~cnt&&~val; }
}Dp[MAXN][MAXS][2][2];
inline void add(Node &a,Node b,int num,int pos)
{
	a.cnt=(a.cnt+b.cnt)%Mod;
	a.val=(a.val+(ll)num*Pw[pos]%Mod*b.cnt%Mod+b.val)%Mod;
}
Node Dfs(int pos,int state,bool limit,bool _0)
{
	if(!pos) return Node(1,0);
	Node &ret=Dp[pos][state][limit][_0];
	if(ret.check()) return ret;
	ret.clear();
	int num=limit?Nums[pos]:9;
	for(int i=0;i<=num;++i) if(popcount(_0&&!i?0:state|1<<i)<=K)
		add(ret,Dfs(pos-1,_0&&!i?0:state|1<<i,limit&(i==num),_0&!i),i,pos-1);
	return ret;
}
inline ll solve(ll x)
{
	std::memset(Dp,-1,sizeof(Dp));
	for(Len=0;x;x/=10) Nums[++Len]=x%10;
	return Dfs(Len,0,1,1).val;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(ql,qr,K),Pw[0]=1;
	for(int i=1;i<=19;++i) Pw[i]=(ll)Pw[i-1]*10%Mod;
	write((solve(qr)-solve(ql-1)+Mod)%Mod);
	return 0;
}
/*

*/

数位与平方和

题目简介

题目名称：恨不成妻

题目来源：一本通练习

评测链接：http://acm.hdu.edu.cn/showproblem.php?pid=4507
评测链接：https://loj.ac/p/10168

形式化题意：求出中所有数，满足不是的倍数，各位数和不是的倍数，不包含的的平方和。对取模。多测。

数据范围：

容易发现对于数：

不由任意一个组成；
不是的倍数；
各位数和不是的倍数。

这是一个极好的数位，仅限于统计个数。但现在要求我们得到平方和，这就比和更难做了。考虑到我们之前做过一道题，是用线段树维护区间平方和，具体在哪里我忘了，但思路是有的，我们知道：

以此类推可以得到：

所以对于我们的数位记忆化，我们需要记录个参数：，表示个数，和，平方和。然后用上述方法进行维护即可。

AC Code

// ----- Eternally question-----
// Problem: #10168. 「一本通 5.3 练习 3」恨 7 不成妻
// Contest: LibreOJ
// URL: https://loj.ac/p/10168
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-03-17 21:31:54
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int Mod=1e9+7,P=7;
template<class T>
inline void add(T &a,T b){ a=a+b>=Mod?a+b-Mod:a+b; }
template<class T>
inline T sum(T a,T b){ return a+b>=Mod?a+b-Mod:a+b; }
const int MAXN=20,MAXK=10;
ll ql,qr,Pw[MAXN];
struct Node
{
	ll cnt,val,squ;
	Node(ll c=-1,ll v=0,ll s=0):cnt(c),val(v),squ(s){}
}Dp[MAXN][MAXK][MAXK];
int Test,Nums[MAXN],Len;
Node Dfs(int pos,int cnt7,int val7,bool limit)
{
	if(!pos) return Node(cnt7&&val7,0,0);
	if(!limit&&~Dp[pos][cnt7][val7].cnt) return Dp[pos][cnt7][val7];
	int num=limit?Nums[pos]:9;Node ret=Node(0,0,0);
	for(int i=0;i<=num;++i) if(i!=P)
	{
		Node tmp=Dfs(pos-1,(cnt7+i)%P,(val7*10+i)%P,limit&(i==num));
		add(ret.cnt,tmp.cnt),add(ret.squ,tmp.squ);
		add(ret.val,sum((Pw[pos-1]*i%Mod)*tmp.cnt%Mod,tmp.val));
		add(ret.squ,(Pw[pos-1]*i%Mod*i%Mod)*Pw[pos-1]%Mod*tmp.cnt%Mod);
		add(ret.squ,(Pw[pos-1]*i%Mod*2%Mod)*tmp.val%Mod);
	}
	if(!limit) Dp[pos][cnt7][val7]=ret;
	return ret;
}
inline ll solve(ll x)
{
	if(!x) return 0;
	for(Len=0;x;x/=10) Nums[++Len]=x%10;
	return Dfs(Len,0,0,1).squ;
}
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test),Pw[0]=1;
	for(int i=1;i<MAXN;++i) Pw[i]=Pw[i-1]*10%Mod;
	while(Test--)
	{
		read(ql,qr);
		write(sum(sum(solve(qr),-solve(ql-1)),(ll)Mod),'\n');
	}
	return 0;
}
/*

*/

高阶数位

题目简介

题目名称：淘金
题目来源：山东省选具体不详

评测链接：https://www.luogu.com.cn/problem/P3303

形式化题意：令表示各位上的乘积（如），令表示的的个数，对于，求出前大的和。取模。

数据范围：

容易发现，任意的都可以拆分为，所以我们可以转化到求中有多少个满足由个组成的数的个数即可。

维护数位状态为即可。预处理出所有的质因数分解情况，一一进行计算即可。

对于最后，我们用一个优先队列贪心维护前大贡献并累计和即可。容易发现初始值在范围内，而显然超了范围，用 __int128_t 又使时空没有保证，所以可以考虑一个乘法原理的思想，将一个数拆分为两个进行贡献。具体实现参照代码。

AC Code

// ----- Eternally question-----
// Problem: P3303 [SDOI2013] 淘金
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3303
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-03-06 21:23:17
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using int128=__int128_t;
const int MAXL=2e5+10,MAXN=14;
const int Mod=1e9+7;
ll N,K;
int Tot,Len,Nums[MAXN];
ll Q[MAXL],Dp[MAXN][45][28][20][16][2],res[MAXL],ans;
int Cnt[10][4]={
	{0,0,0,0},{0,0,0,0},{1,0,0,0},{0,1,0,0},{2,0,0,0},
	{0,0,1,0},{1,1,0,0},{0,0,0,1},{3,0,0,0},{0,2,0,0}
};
std::map<ll,bool>Hash;
void Divide(ll x)
{
	if(Hash.find(x)!=Hash.end()) return ;
	Hash[x]=1;
	if(x>N) return ;
	Q[++Tot]=x;
	Divide(x<<1),Divide((x<<1)+x),Divide((x<<2)+x),Divide((x<<2)+(x<<1)+x);
}
ll Dfs(int pos,int _2,int _3,int _5,int _7,bool limit,bool _0)
{
	if(_2<0||_3<0||_5<0||_7<0) return 0;
	if(!pos) return !_2&&!_3&&!_5&&!_7&&!_0;
	if((!limit)&&~Dp[pos][_2][_3][_5][_7][_0]) return Dp[pos][_2][_3][_5][_7][_0];
	ll ret=0;int num=limit?Nums[pos]:9;
	for(int i=!_0;i<=num;++i)
		ret+=Dfs(pos-1,_2-Cnt[i][0],_3-Cnt[i][1],_5-Cnt[i][2],_7-Cnt[i][3],limit&(i==num),_0&(!i));
	if(!limit) Dp[pos][_2][_3][_5][_7][_0]=ret;
	return ret;
}
struct Node
{
	int x,y;
	const bool operator<(const Node &_)const
	{ return (int128)res[_.x]*res[_.y]>(int128)res[x]*res[y]; }
};
std::priority_queue<Node>Pq;
inline ll calc(ll x)
{
	int _2=0,_3=0,_5=0,_7=0;
	ll Copy=x;
	while(!(x&1)) x>>=1,++_2;
	while(!(x%3)) x/=3,++_3;
	while(!(x%5)) x/=5,++_5;
	while(!(x%7)) x/=7,++_7;
	return Dfs(Len,_2,_3,_5,_7,1,1);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,K);ll X=N;
	for(Len=0;X;X/=10) Nums[++Len]=X%10;
	Divide(1);
	std::memset(Dp,-1,sizeof(Dp));
	for(int i=1;i<=Tot;++i) res[i]=calc(Q[i]);
	std::sort(res+1,res+Tot+1);
	for(int i=1;i<=Tot;++i) Pq.push((Node){i,Tot});
	for(int i=1;i<=K;++i)
	{
		Node u=Pq.top();Pq.pop();
		ans=(ans+res[u.x]%Mod*res[u.y]%Mod)%Mod;
		if(u.y>1) Pq.push((Node){u.x,u.y-1});
	}
	write(ans);
	return 0;
}
/*

*/

高阶数位 II & 类数位dp

题目简介

题目名称：普通数学题
题目来源：洛谷月赛
评测链接：https://www.luogu.com.cn/problem/P3791

形式化题意：给定，求，其中表示的约数个数。对取模。

数据范围：

看着就像个莫反，可惜不是。考虑将问题转换为求，也就是我们需要求出的是所有的即可。那这就是个计数问题了，用二进制数位可以解决。

假设现在我们先不管的限制，考虑的贡献，也就是需要计算一个二进制数形如，而给定，随意的计数问题，而这一段对答案的贡献也就形如。

我们发现，我们记录的前缀和为，就可以将答案转换为，也就是能够在的时间内进行转移。容易发现，这个过程可以扩展为二维。

如果，手玩一下，会发现会把内的数各取次，此时答案为。

会发现，这个答案与无关。按照这个思路，我们将进行二进制拆分，并将其转换为上述式子进行运算，一个数不会超过次拆分，所以计算不会超过次。

于是我们对的每一位进行计算，当前位为时，则对其所有低位进行答案统计，就用上述式子即可。每一次计算对上位进行固定，每一个异或得到的值的指数都是当前能够随意填的位数和，那我们卡住上界，对下界进行计算即可。

因为有，所以进行数论分块可以做到。对进行记忆化可以做到。

AC Code

// ----- Eternally question-----
// Problem: P3791 普通数学题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3791
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-04-04 16:38:34
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=51;
const int Mod=998244353;
ll N,M,X;
std::unordered_map<ll,ll>Hash;
inline ll calc(ll x)
{
	if(Hash.find(x)!=Hash.end()) return Hash[x];
	ll ans=0;
	for(ll l=1,r=0;l<=x;l=r+1)
	{
		r=(x/(x/l));
		ans=(ans+(x/l)*(r-l+1)%Mod)%Mod;
	}
	return Hash[x]=ans;
}
inline ll solve(ll n,ll m,ll nl,ll ml)
{
	if(nl>ml) std::swap(n,m),std::swap(nl,ml);
	ll r=(n^m^X)&(~((1ll<<ml)-1));
	return (calc(r+(1ll<<ml)-1)-calc(r-1)+Mod)%Mod*(1ll<<nl)%Mod;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M,X);++N,++M;
	ll ans=0;
	for(int i=0;i<MAXN;++i)
	{
		if(N>>i&1) for(int j=0;j<MAXN;++j)
			if(M>>j&1) ans=(ans+solve(N^(1ll<<i),M^(1ll<<j),i,j))%Mod;
	}
	write(ans);
	return 0;
}
/*

*/

高阶数位 III

题目简介

题目名称：数位
题目来源：陕西省选第四题

评测链接：https://loj.ac/p/3730
评测链接：https://www.luogu.com.cn/problem/P8362

形式化题意：给定一个长度为的序列，满足，求所有的，满足的数位从高到低递减，也就是单增（例如等）。个数对取模。

数据范围：

时空限制：

首先考虑，那这就是一个较常规的数位。

那我们如果当前已经知道了的值，就会解一个元一次不定方程，用隔板法可以知道答案为，当然，我们这里的被限制在之间。

但我们的实际取值是在，需要规定一手的上界，这是不好做的。然后我们借鉴一下各路神仙的做法，进行一波容斥，枚举当前有个突破了上界，可以得到：

$ans=\sum_{i=0}^{k}(-1)^i\binom{k}{i}\binom{s-k(l-1)-i(r-l+1)-1}{k-1}$

这样的话，我们可以枚举，并对每一个计算出后面那一坨式子的值。也就是用数位找出所有的并维护的值。这看起来是一个极其困难的问题。

考虑设，化简式子为，那这就是一个关于的未知系数的次多项式。

然后通过一系列二项式拆分将多项式化为数位用数位求解，最后可以用高斯消元合并答案，也可以直接用二项式定理。

时间复杂度不是这道题的瓶颈，能过的都能过。

高阶数位 IV

题目简介

题目名称：圆滚滚的算术占卜
题目来源：集训队互测第六天第一题

评测链接：https://loj.ac/p/3641

形式化题意：定义为自然数十进制表示下各位数字之和。定义运算为十进制依次拼接所得的数（如），当时，。令的权值如下计算：

$f(n)= \begin{cases} 0,&n=0 \\ n\oplus f\big(n-S(n)\big),&n\neq 0 \end{cases}$

求中，对取模。多测。

数据范围：

			特殊性质
			无



			无
			无

时空限制：

~~能找到的数位动态规划最难的题了吧……~~

我认为应该循序渐进，所以我们一个一个过……

Subtask1

~~我超我居然会第一个Sub。~~

考虑一手的计算方式，如果我们只需要得到一个单独的，可以考虑递归求解，容易发现对于计算时间复杂度是不会超过的，但很可惜的是是过不了的。

转化递归为递推，对进行预处理。对其进行递推，得到，那就直接递推算就行了。注意可以预处理每个数的位数，以免复杂度里多一个或者。时间复杂度。

Subtask2

~~我超我居然会第二个Sub。~~

考虑到就只需要计算一个的值，且多测数较小，每一次可以直接计算，期望下每一次的计算次数不会超过，所以是可以过的。

附上的代码。过不了，~~因为样例没过。~~，超差点忘了有跳过样例的功能。

至于每一次转移，可以选择对当前答案与的位数一起进行转移，对于计算，的话，可以钦定一个可以接受的，并进行预处理，用的时间转移，而对于的次幂，可以通过的时间预处理，并转移。

~~太菜而且鸽了太久所以就没写代码了。~~

参考代码

namespace Subtask1
{
	const int MAXN=1e5+10,N=1e5;
	bool flag=1;
	int f[MAXN],Sum_f[MAXN],S[MAXN],Pw[MAXN];
	int Log10[MAXN],Dig[MAXN];
	inline int Ln(int x)
	{
		if(x<=N) return Log10[x];
		int res=0;
		while(x) x/=10,++res;
		return res;
	}
	inline void init()
	{
		Pw[0]=1;
		for(int i=1;i<=9;++i) Dig[i]=1,S[i]=i,f[i]=i;
		for(int i=1;i<=N;++i) Pw[i]=10ll*Pw[i-1]%Mod,Log10[i]=Log10[i/10]+1;
		for(int i=10;i<=N;++i) S[i]=S[i-(i/Pw[Ln(i)-1])*Pw[Ln(i)-1]]+(i/Pw[Ln(i)-1]);
		for(int i=10;i<=N;++i) Dig[i]=Ln(i)+Dig[i-S[i]];
		for(int i=10;i<=N;++i) f[i]=((ll)i*Pw[Dig[i-S[i]]]%Mod+f[i-S[i]]%Mod)%Mod;
		for(int i=1;i<=N;++i) Sum_f[i]=(Sum_f[i-1]+f[i])%Mod;
		flag=0;
	}
	inline void solve()
	{
		if(flag) init();
		write((Sum_f[qr]-Sum_f[ql-1]+Mod)%Mod,'\n');
		return ;
	}
};
namespace Subtask2
{
	inline void solve()
	{
		if(Subtask1::flag) Subtask1::init();
		write(calc(qr),'\n');
	}
};

单点查询

之后就是正解相关了。

我们首先钦定进制，并用表示当前数的位数，在本题中。

首先容易得到的是，，因为我们可以知道，对于一段长度不小于的区间，的转移过程必有至少一次经过了区间，这是不难想到的。

如果可以表示为的形式，并当时我们称是一个关键位置，那么，所有的关键位置所构成的集合一定是很多个长度为组成的不交区间的并。而，计算时都会经过这个区间。

通过的手玩，我们发现关键位置十分密集，而，在计算途中递归不超过次（甚至次）就至少会到达个关键位置。所以我们可以考虑对关键位置的答案进行预处理，并用一个近似常数的算法去回答每一个询问。

我们记表示第一次成为关键位置的值。每一次转移的只和相关，意思在于，如果我们当前并没有向高位进位的话，那么高位对该过程的影响只与高位数位和有关。

再考虑一个拼数的过程，我们需要第二个数的位数，并乘上某一个的次幂，所以我们的状态需要记录当前总位数，而对于拼数的第一个数我们设为，这个在当前转移是一个关键位置，也就是当前并不会向位借位，可以发现，和其之上的高位是呈线性关系的。

设计状态，表示当前这个数一共有位，将这个数从第位划开，低位的数值为，高位数位和为。这个状态维持到需要向位借位为止。

这个状态为我们提供一下两种操作：

当前的转移需要进位时。我们设此时的低位差值为，显然，那么我们可以将转移为下一次的。
我们当前数字串对整个数字的答案的影响，我们设定原来的数字串为，当前的最高位为，我们可以用一个三元组来表示拼接之后的数字串值，表示为，此合并不具有交换律。

这个动态规划的状态数是的。暴力求出的情况，并对的情况进行有效转移，此时预处理复杂度为。而对于查询，暴力转移至关键位置，然后进行每一位的答案计算，时间复杂度为，这样可以通过所有的数据点。

对于上述转移，我们通过一下方式转移：

一般情况（不退位），可以从向转移，也就是将第位从低位视作高位：如果，则低位变成了，状态视为，还要给状态中的加上一个，向高位拼接转移，以此类推，将的情况列出来即可。

当比较小的时候，可能会出现为负数的情况，那么我们直接钦定转移至，并在时进行一次拼接，此时转移方程视作，此时的数变为，向下转移为。

而当，也就是高位变成前导零，没有高位了，特殊处理，记录状态，表示数为，通过对的讨论从转移。

求前缀和

如果我们从低位开始转移的话，每一次转移固定一段高位，并处理所有与当前除去最低位相同的元素，这些位处理结束后转移至，且高位与高位相同的情况。然后枚举，在时，同样用进行转移。

然后我们考虑当时，令，通过和的互相转移进行预处理，进行特殊处理。

时间复杂度。可以通过本题。进行优化的话，预处理表示这一状态中所有第位小于的数的转移之和，可以少枚举一个，做到。

至于，提到了一个求单项的优化，就是把所有需要求单项的点剔除并对其建虚树，然后对虚树进行树型能够在线性时间内得到前缀和，而一个比较漂亮的性质是，所有的父结点编号小于子结点，所以可以直接倒序扫描。

参考资料

出题人陈于思的官方题解：https://qoj.ac/download.php?type=solution&id=4904
$Double subscripts: use braces to clarify\text{418}_{254}_\text{3731’s blog}$ （张隽恺）：https://4182543731.github.io/post/LullabyforTiuLii/#d6-t1-11-圆滚滚的算数占卜

参考代码

// ----- Eternally question-----
// Problem: #3641. 「2021 集训队互测」圆滚滚的算术占卜
// Contest: LibreOJ
// URL: https://loj.ac/p/3641
// Memory Limit: 2048 MB
// Time Limit: 3000 ms
// Written by: Eternity
// Time: 2023-03-23 15:20:51
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int Mod=998244353;
int Test;
ll ql,qr;
namespace Subtask1
{
	const int MAXN=1e5+10,N=1e5;
	bool flag=1;
	int f[MAXN],Sum_f[MAXN],S[MAXN],Pw[MAXN];
	int Log10[MAXN],Dig[MAXN];
	inline int Ln(int x)
	{
		if(x<=N) return Log10[x];
		int res=0;
		while(x) x/=10,++res;
		return res;
	}
	inline void init()
	{
		Pw[0]=1;
		for(int i=1;i<=9;++i) Dig[i]=1,S[i]=i,f[i]=i;
		for(int i=1;i<=N;++i) Pw[i]=10ll*Pw[i-1]%Mod,Log10[i]=Log10[i/10]+1;
		for(int i=10;i<=N;++i) S[i]=S[i-(i/Pw[Ln(i)-1])*Pw[Ln(i)-1]]+(i/Pw[Ln(i)-1]);
		for(int i=10;i<=N;++i) Dig[i]=Ln(i)+Dig[i-S[i]];
		for(int i=10;i<=N;++i) f[i]=((ll)i*Pw[Dig[i-S[i]]]%Mod+f[i-S[i]]%Mod)%Mod;
		for(int i=1;i<=N;++i) Sum_f[i]=(Sum_f[i-1]+f[i])%Mod;
		flag=0;
	}
	inline void solve()
	{
		if(flag) init();
		write((Sum_f[qr]-Sum_f[ql-1]+Mod)%Mod,'\n');
		return ;
	}
};
namespace Subtask2
{
	#define sec second
	#define fir first
	const int MAXN=1e6+10,N=1e5,M=1e6;
	using Pir=std::pair<ll,ll>;
	ll Pw[MAXN],Pow[2][MAXN];
	int S[MAXN],Log10[MAXN];
	inline int Digit(ll x)
	{
		int l=0,r=18,res=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(Pw[mid]<=x) l=mid+1,res=mid;
			else r=mid-1;
		}
		return res+1;
	}
	inline int qPow(int b)
	{ return (ll)Pow[0][b%N]*Pow[1][b/N]%Mod; }
	inline Pir calc(int x)
	{
		if(x<10) return Pir{x,1};
		auto res=calc(x-S[x]);
		return {0,Digit(x)+res.sec};
	}
	inline int Sum(int x)
	{
		int res=S[x%N];
		x/=N;
		while(x) res+=x%10,x/=10;
		return res;
	}
	bool flag=0;
	inline void init()
	{
		Pw[0]=1,Pow[0][0]=Pow[1][1]=Pow[1][0]=1;
		for(int i=1;i<=9;++i) S[i]=i;
		for(int i=1;i<=18;++i) Pw[i]=Pw[i-1]*10;
		for(int i=1;i<=N;++i) Pw[i]=10ll*Pw[i-1]%Mod,Log10[i]=Log10[i/10]+1;
		for(int i=10;i<=N;++i) S[i]=S[i-(i/Pw[Digit(i)-1])*Pw[Digit(i)-1]]+(i/Pw[Digit(i)-1]);
		for(int i=1;i<=N;++i) Pow[0][i]=(ll)Pow[0][i-1]*10%Mod,Pow[1][1]=(ll)Pow[1][1]*10%Mod;
		for(int i=2;i<=N;++i) Pow[1][i]=(ll)Pow[1][i-1]*Pow[1][1]%Mod;
		flag=1;
		for(int i=11414;i<=11450;++i) write(S[i],' ');
	}
	inline void solve()
	{
		if(!flag) init();
		// write(calc(qr),'\n');
	}
	#undef fir
	#undef sec
};
const int MAXN=19,MAXM=11,MAXS=167;
struct Sth
{ int a,b,c; };
struct Stl
{ int a,b,c; };
Stl operator+(Stl a,Stl b){ return (Stl){(a.a+b.a)%Mod,(a.b+b.b)%Mod,(a.c+b.c)%Mod}; }
Stl operator*(Stl a,Sth b){ return (Stl){a.a,((ll)a.b*b.a+(ll)b.b*a.a)%Mod,((ll)a.c*b.a+(ll)b.c*a.a)%Mod}; }
Sth operator*(Sth a,Sth b){ return (Sth){(ll)a.a*b.a%Mod,((ll)a.b*b.a+b.b)%Mod,((ll)a.c*b.a+b.c)%Mod}; }
Sth vl[MAXN][MAXN][MAXS][MAXN],rv[MAXN][MAXN],Tr[MAXN][MAXN][MAXM][MAXS][MAXN];
Stl Dp[MAXN][MAXN][MAXS][MAXN],Su[MAXN][MAXN][MAXM][MAXS][MAXN],res[MAXN];
int Nt[MAXN][MAXN][MAXS][MAXN],St[MAXN][MAXN][MAXM][MAXS][MAXN],Pow[MAXN];
int Id[MAXS][MAXS],Rid[MAXS][MAXN];
inline void init_Dp()
{
	Pow[0]=1;
	for(int i=1;i<MAXN;++i) Pow[i]=10ll*Pow[i-1]%Mod;
	for(int r=0;r<=162;++r)
	{
		int ci=0;
		for(int j=1;j<=162;++j) if((j+162-r)%9==1) Id[r][j]=++ci,Rid[r][ci]=j;
	}
	rv[0][1]=(Sth){1,0,0};
	for(int i=1;i<MAXN;++i)
	{
		for(int r=1;r<=9*i;++r) for(int e=1;e<=i;++e)
			if(Rid[r][e]>1) vl[i][0][r][e]=(Sth){1,0,0},Nt[i][0][r][e]=Id[r-1][Rid[r][e]-1];
			else vl[i][0][r][e]=(Sth){Pow[i],0,1},Nt[i][0][r][e]=Id[r-1][r];
		for(int d=1;d<i;++d) for(int r=1;r<=9*(i-d);++r)
		{
			for(int e=1;e<=i;++e) Tr[i][d][0][r][e]=(Sth){1,0,0},St[i][d][0][r][e]=e;
			for(int u=0;u<=9;++u) for(int e=1;e<=i;++e)
			{
				Sth r1=vl[i][d-1][r+u][e];r1.b=(r1.b+1ll*u*Pow[d-1]*r1.c)%Mod;
				Tr[i][d][u+1][r][e]=r1*Tr[i][d][u][r][Nt[i][d-1][r+u][e]],
				St[i][d][u+1][r][e]=St[i][d][u][r][Nt[i][d-1][r+u][e]];
			}
			for(int e=1;e<=i;++e) vl[i][d][r][e]=Tr[i][d][10][r][e],Nt[i][d][r][e]=St[i][d][10][r][e];
		}
		for(int e=1;e<=i;++e)
		{
			int nw=e;
			Sth tp=(Sth){1,0,0};
			for(int u=9;u>0;--u)
			{
				Sth r1=vl[i][i-1][u][nw];r1.b=(r1.b+1ll*u*Pow[i-1]*r1.c)%Mod;
				tp=tp*r1;nw=Nt[i][i-1][u][nw];
			}
			rv[i][e]=tp*rv[i-1][nw];
		}
	}
	for(int i=1;i<MAXN;++i)
	{
		for(int r=1;r<=9*i;++r) Dp[i][0][r][Id[r-1][r]]=(Stl){1,0,1};
		for(int d=1;d<i;++d) for(int r=1;r<=9*(i-d);++r)
		{
			for(int u=0;u<=9;++u)
			{
				for(int e=1;e<=i;++e) Su[i][d][u+1][r][e]=Su[i][d][u][r][e];
				for(int e=1;e<=i;++e)
				{
					Stl si=Dp[i][d-1][r+u][e];si.b=(si.b+1ll*u*Pow[d-1]*si.c)%Mod;
					Su[i][d][u+1][r][St[i][d][u][r][e]]=Su[i][d][u+1][r][St[i][d][u][r][e]]+si*Tr[i][d][u][r][e];
				}
			}
			for(int e=1;e<=i;++e) Dp[i][d][r][e]=Su[i][d][10][r][e];
		}
		res[i]=res[i-1];
		for(int u=1;u<=9;++u) for(int e=1;e<=i;++e)
		{
			Stl si=Dp[i][i-1][u][e];si.b=(si.b+1ll*u*Pow[i-1]*si.c)%Mod;
			int nw=e;
			for(int y=u-1;y>0;--y)
			{
				Sth r1=vl[i][i-1][y][nw];r1.b=(r1.b+1ll*y*Pow[i-1]*r1.c)%Mod;
				si=si*r1;nw=Nt[i][i-1][y][nw];
			}
			res[i]=res[i]+si*rv[i-1][nw];
		}
	}
}
Stl s1[MAXN],s2[MAXN];
inline int solve(ll x)
{
	if(x<=9) return x*(x+1)/2;
	int ans=0,sr=0,le=0;
	if(x==1000000000000000000ll) --x,ans=753831110;
	ll tp=1,t1=x;
	while(tp<=x) tp*=10,++le;
	for(int i=1;i<=18;++i) s1[i]=s2[i]=(Stl){0,0,0};
	while(t1) sr+=t1%10,t1/=10;
	for(int d=1;d<le;++d)
	{
		int ri=x%10;x/=10;sr-=ri;
		for(int i=1;i<=18;++i)
		{
			Stl r1=s1[i];r1.b=(r1.b+1ll*ri*Pow[d-1]*r1.c)%Mod;
			s2[St[le][d][ri][sr][i]]=s2[St[le][d][ri][sr][i]]+r1*Tr[le][d][ri][sr][i];
		}
		for(int i=1;i<=18;++i) s2[i]=s2[i]+Su[le][d][ri+(d==1)][sr][i];
		for(int i=1;i<=18;++i) s1[i]=s2[i],s2[i]=(Stl){0,0,0};
	}
	for(int i=1;i<=18;++i) s1[i].b=(s1[i].b+1ll*x*Pow[le-1]*s1[i].c)%Mod;
	for(int u=x-1;u>=1;--u)
	{
		for(int i=1;i<=18;++i)
		{
			Sth r1=vl[le][le-1][u][i];r1.b=(r1.b+1ll*u*Pow[le-1]*r1.c)%Mod;
			s2[Nt[le][le-1][u][i]]=s2[Nt[le][le-1][u][i]]+s1[i]*r1;
		}
		for(int i=1;i<=18;++i)
		{
			Stl si=Dp[le][le-1][u][i];si.b=(si.b+1ll*u*Pow[le-1]*si.c)%Mod;
			s2[i]=s2[i]+si;
		}
		for(int i=1;i<=18;++i) s1[i]=s2[i],s2[i]=(Stl){0,0,0};
	}
	for(int i=1;i<=18;++i) ans=(ans+(s1[i]*rv[le-1][i]).b)%Mod;
	ans=(ans+res[le-1].b)%Mod;
	return ans;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	init_Dp();
	while(Test--)
	{
		read(ql,qr);
		// else if(ql==qr&&qr<=1000000000) Subtask2::solve();
		write(((solve(qr)-solve(ql-1))%Mod+Mod)%Mod,'\n');
	}
	return 0;
}
/*

*/