数位dp的一般套路
问题形式
给你一个条件 \(A\) ,然后询问值大小在 \([L,R]\) 中有多少满足条件的数
这个问题暴力去做一般是 \(\mathcal{O}(R)\) 的时间复杂度,但是通过数位dp我们可以把这个东西优化到 \(\mathcal{O}(\log_{10}R)\)
求解过程
首先我们将区间 \([L,R]\) 的限制利用前缀和拆开,这样我们的问题就变成了求 \([1,R]\) 中满足要求的数的个数
每一位作为dp的阶段,设计状态,一般采用记忆化搜索的方法
我们要从高位向低位枚举,因为如果我们确定的高位之后才可以确定低位的范围
比如说一个数 \(1230\)
如果我们前两位分别选的是 \(1,2\) ,那么第三位的取值范围就是 \([0,3]\)
如果我们前两位分别选的是 \(1,1\) ,那么第三位的取值范围就是 \([0,9]\)
也就是我们在记忆化搜索的过程中记一个变量 \(lim\) 表示前几位是否和最大数一样
具体的代码实现看下面的这一道题目
P4127 [AHOI2009]同类分布（经典数位dp）
题目
给出两个数\(a,b\)，求出\([a,b]\)中各位数字之和能整除原数的数的个数。
\(1 \le a \le b\le 10^{18}\)
代码实现如下,细节都在注释里
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
const int N=25,M=210;
int n,a[N],f[N][M][M],mod;
inline int F(int u,int sum,int st,bool lim)
{
if(u>n&&sum==0) return 0;//模数为0是无意义的
if(u>n) return st==0&&sum==mod?1:0;//如果模数恰好为1,那么就是一个合法的解
if(!lim&&f[u][sum][st]!=-1) return f[u][sum][st];//记忆化搜索
int ret=0,res=lim?a[u]:9;//lim判断当前位是否能随便取
for(int i=0;i<=res;++i)
ret+=F(u+1,sum+i,(10*st+i)%mod,i==res&&lim);
return f[u][sum][st]=ret;
}
inline int solve(int x)
{
n=0;
while(x) a[++n]=x%10,x/=10;
reverse(a+1,a+1+n);//从高位到低位枚举
int ret=0;
for(mod=1;mod<=9*n;++mod)//枚举当前模数
{
memset(f,-1,sizeof(f));
ret+=F(1,0,0,1);
}
return ret;
}
int l,r;
signed main()
{
l=read();r=read();
printf("%lld\n",solve(r)-solve(l-1));
return 0;
}
HDU 3709 Balanced Number（普通数位dp）
题目
求区间 \([L,R]\) 里面满足平衡数的数的个数,\(1 \le L\le R\le 1\times 10^{18}\)
平衡数定义：可以通过找一个平衡数位，该数位左边的数位乘以偏移距离的和等于右边的数位乘以偏移距离的和。
比如 \(4139\) ，平衡数位为 \(3\) ,\(4\times 2+1=9\),因此该数是平衡数
题解
显然的是,每个数最多只能有一个平衡数位(毕竟没有物体是有两个重心的)
那么我们仿照上一题枚举模数的做法,这一题我们枚举平衡数位
假设我们将一个数的各位存到 \(a\) 数组中,枚举到的平衡数位是 \(k\) ,那么一个有 \(\text{len}\) 位的数答案可以按照如下的方式统计
\[\text{nw}=\sum_{i=1}^{\text{len}} (i-k)\times a[i] \]当 \(i=\text{len}\) 且 \(\text{nw}=0\) 的时候,就意味着当前数是平衡数位为 \(k\) 的平衡数
通过上面的方式统计出答案即可
HDU 4507 吉哥系列故事——恨7不成妻（平方和的处理）
题目
如果一个数跟 \(7\) 有关,那么我们就说它满足以下三条性质
- 整数中的某一位是 \(7\)
- 整数的每一位上的数加起来是 \(7\) 的倍数
- 整数是 \(7\) 的倍数
询问 \([L,R]\) 当中与 \(7\) 无关的数的平方和 \(1\le L\le R\le 1\times 10^{18}\)
题解
首先可以通过所有的数的平方和减去与 \(7\) 有关的数的平方和来得到答案
我们的状态按照下面的思路定义
- 整数中的某一位是 \(7\) \(\Rightarrow\) 一维状态 \(a\) 表示是否有 \(7\) 出现
- 整数的每一位上的数加起来是 \(7\) 的倍数 \(\Rightarrow\) 一维状态 \(b\) 表示各数位的和模 \(7\) 的值
- 整数是 \(7\) 的倍数 \(\Rightarrow\) 一维状态 \(c\) 表示当前这个数模 \(7\) 的值
于是我们就设出了状态 \(f[u][a][b][c]\)
如果是要求个数,那么这个问题与上面两个问题是没有区别的,可是这里是要我们求平方和
所以考虑一个我们在期望dp那里也用过的套路,为了转移,我们需要维护 \(3\) 个值:
- \(\text{cnt}\) 表示与 \(7\) 有关的数的个数
- \(\text{sum}\) 表示与 \(7\) 有关的数的和
- \(\text{sqr}\) 表示与 \(7\) 有关的数的平方和
考虑转移,假设我们记忆化搜索回溯上来的数为 \(x\) ,当前是第 \(u\) 位,上面的数为 \(k\) 。那么我们知道,算上这一位后再回溯这个数就会变为 \(x+k\times 10^{u-1}\),为了方便表示,我们设 \(d=k\times 10^{u-1}\) ,考虑我们形成的新数 \(x+d\) 与 \(7\) 有关的数的平方和应该怎么计算
它的平方对答案的贡献为 \((x+d)^2=x^2+2dx+d^2\) ,考虑如何计算这个贡献和,假设有 \(n\) 个合法的数分别为 \(x_1,x_2,\cdots ,x_n\) ,那么对答案的贡献如下
\[\sum_{i=1}^n (x_i+d)^2=n\times d^2+2d\times (x_1+x_2+\cdots+x_n)+(x_1^2+x_2^2+\cdots+x_n^2) \]假设我们当前状态是 \(f\) ,回溯过来的状态是 \(g\) ,那么转移方程如下
\[f.\text{cnt}\leftarrow g.\text{cnt} f.\text{sum}\leftarrow g.\text{sum}+d\times g.text{cnt} f.\text{sqr}\leftarrow g.\text{cnt}\times d^2+2d\times g.\text{sum}+g.\text{sqr} \]这样就做完了
CF55D Beautiful numbers （数位dp的状态剪枝）
题目
Volodya 认为一个数字 \(x\) 是美丽的，当且仅当 \(x\in\mathbb{Z^+}\) 并且对于 \(x\) 的每一个非零位上的数 \(y\)，都有 \(y|x\)。
你需要帮助他算出在区间 \([l,r]\) 中有多少个数是美丽的。
\(t\) 组数据。
\(1\le t\le 10,1\le l\le r\le 9\times 10^{18}\)
保证 \(l,r\) 都是整数
题解
首先,一个数能够被它的各个数位同时整除,等价于它能被各个数位的 \(\text{lcm}\) 整除
而 \(1\sim 9\) 的 \(\text{lcm}\) 是 \(2520\)
因此各个数位的 \(\text{lcm}\) 一定是 \(2520\) 的因子
于是我们设 \(f[u][\text{lcm}][\text{nw}]\) 表示枚举到第 \(u\) 位,当前所有非零数位的 \(\text{lcm}\) 为 \(\text{lcm}\),当前这个数模 \(2520\) 的结果为 \(\text{nw}\) ,假设当前数位的值为 \(k\) ,所以有转移
\[f[u][\text{lcm}][\text{nw}] \leftarrow f[u+1][\text{lcm}(\text{lcm},k)][(\text{nw}+k)\% 2520] \]由于中途的 \(\text{lcm}\) 是会发生变化的,所以我们模 \(2520\)
最后检查 \(\text{nw}\% \text{lcm}\) 是否为零就行
了吗？
我们注意到 \(\text{lcm}\) 和 \(\text{nw}\) 都是 \(2520\) 的大小,所以你要是这么写了,那么恭喜 \(\text{MLE}\)
注意到 \(2520\) 只有 \(48\) 个 因子,因此状压一下 \(\text{lcm}\) 那一维就可以了
CF908G New Year and Original Order （经典数位dp）
题目
给 $ n\le 10^{700} $ ，问 \(1\) 到 \(n\) 中每个数在各数位排序后得到的数的和。
题解
首先直接做肯定是没有前途的,冷静一下,我们发现一个性质,这里以 \(2457\) 举例
\[2457=1111\times 2+111\times 2|11\times 1+1\times 2+0\times 2 \]于是我们发现,一个数各数位排序之后会形成一个单调不降的序列,可以将其拆分为 \(9\) 个形如 \(1\cdots 11\) 的数。换句话说,如果这个数中有 \(i\) 个数位是大于等于 \(d~(d\in [1,9])\) 的,那么其对答案的贡献就有 \(\underbrace{11\cdots 1}_{i}\)
所以我们可以对于每个 \(d\) 都去算一下贡献,设 \(f[i][j][lim]\) 表示选了 \(i\) 个数,恰好有 \(j\) 位 \(\ge d\) ,是否压上界,时间复杂度 \(\mathcal O(n^2\times 10)\)
ZR2023 NOIP赛前20连测 Day6 T3 （反套路数位dp）
题意
你当前想要做一个有关概率的问题。
具体的，有 \(n\) 个随机变量，每个随机变量以相同的概率分布在 \([0,9]\) 。
当前你需要计算有多少概率使得变量的和小于等于为 \(k\)。
当然你并不满足于此，你尝试将这 \(n\) 个变量顺序排成一个十进制数（第 \(1\) 个变量是最高位，第 \(n\) 个变量是个位）。
要求这个十进制数大小 \(\mod p =0\)。
你需要对 \(k=0\sim m\) 都求出来结果。
为了方便，你只需要输出满足条件的概率乘上 \(10^n\)。
由于答案可能很大，你只需要输出答案在 \(\mod 998244353\) 意义下的结果。
对于所有测试点满足 \(1\leq n\leq 10^9,1\leq p\leq 50,1\le m \le 1000\)
题解
首先，你仔细想一下我们上面提到的常规数位dp做法，会发现它很困难，出题人的意思是可以用多项式做，挺抽象的
所以我们考虑另一种做法，我们将所有的 \(k\) ，按照 \(10^k\bmod p\) 的值分成若干剩余类，然后考虑 dp，设 \(f_{i,j,k}\) 表示考虑到第 \(i\) 个剩余类，当前数位和为 \(j\) ，当前数模 \(p\) 的结果是 \(k\) 时的方案数。我们记 \(g_{i,j}\) 表示第 \(i\) 个剩余类对数位和产生 \(j\) 的贡献的方案数。设当前我们要给数位和加 \(d\) ，那么转移方程即为
\[f_{i+1,j+d,(k+i\times d)\bmod p}\leftarrow f_{i,j,k}\times g_{i,d} \]考虑如何求出 \(g_{i,j}\) ，首先通过找 \(10^k\) 模 \(p\) 的循环节，我们很容易算出来每个剩余类的大小为多少，记作 \(\text{cnt}_i\) ，考虑我们现在的贡献 \(j\) 都是由剩余类 \(i\) 的哪些位置组成的，这里可以插板法算，也就是把 \(\text{cnt}_i\) 个板插到 \(j\) 个位置上，板 \(k\) 和板 \(k+1\) 之间的数的个数就是第 \(k\) 个位置所产生的贡献大小，这里的方案数即为。
\[\binom{\text{cnt}_i+j-1}{j} \]注意到一个位置的贡献最高是 \(9\) ，所以我们考虑容斥，钦定一些位置的贡献至少是 \(10\) ，钦定了 \(k\) 个位置，系数就是 \((-1)^k\binom{\text{cnt}_i}{k}\) ，然后还要把 \(j\) 减去 \(10k\)
然后由于 \(\text{cnt}_i\) 和 \(n\) 同阶，所以我们算上面的组合数需要用到下降幂，即
\[\binom{n}{m}=\frac{n^{\underline m}}{m!} \]总时间复杂度即为 \(\mathcal O(m^2p^2)\)
带注释代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
const int mod=998244353,M=1010,P=51;
int up[M],dw[M],fac[M],ifac[M];
int n,p,m,N;
inline int ksm(int a,int b)
{
int val=1;
while(b)
{
if(b&1) val=val*a%mod;
a=a*a%mod;
b>>=1;
}
return val;
}
inline void init(int n)
{
N=n;
dw[0]=1;
for(int i=1;i<M;++i) dw[i]=dw[i-1]*(n-i+1)%mod;
up[0]=1;
for(int i=1;i<M;++i) up[i]=up[i-1]*(n+i-1)%mod;
}
inline int Cd(int x)
{
if(x>N) return 0;
return dw[x]*ifac[x]%mod;
}
inline int Cu(int x)
{
return up[x]*ifac[x]%mod;
}
int ok[M],id[M],val[M],cnt[M];
int g[P][M];
int f[P][M][P];
signed main()
{
n=read();p=read();m=read();
fac[0]=1;
for(int i=1;i<M;++i) fac[i]=fac[i-1]*i%mod;
ifac[M-1]=ksm(fac[M-1],mod-2);
for(int i=M-2;i>=0;--i) ifac[i]=ifac[i+1]*(i+1)%mod;
int u=1,tot=0,L=0,R=-1;
for(int i=1;i<=n;++i)//找模p意义下的循环节,用来计算各个剩余类的大小
{
u%=p;
if(ok[u])
{
L=id[u];R=i-1;
break;
}
++cnt[u];
id[u]=++tot;
val[tot]=u;
ok[u]=1;
u*=10;u%=p;
}
if(R!=-1)
{
int k=(n-R)/(R-L+1);
for(int i=L;i<=R;++i) cnt[val[i]]+=k;
u=val[R]*10%p;
for(int i=R+k*(R-L+1)+1;i<=n;++i)
{
u%=p;
++cnt[u];
id[u]=++tot;
val[tot]=u;
ok[u]=1;
u*=10;u%=p;
}
}
for(int i=0;i<p;++i)
{
init(cnt[i]);
for(int j=0;j<=m;++j)
{
int res=0;
for(int k=0;;++k)
{
if(j<10*k) break;
if(k&1) res+=(mod-1)*Cd(k)%mod*Cu(j-10*k)%mod;
else res+=Cd(k)*Cu(j-10*k)%mod;
}
g[i][j]=res%mod;//第 i 个剩余类，给数位和贡献 j 的方案数
}
}
f[0][0][0]=1;//考虑到第 i 个剩余类 ，数位和为 j ，取模结果为 k 时的方案数
for(int i=0;i<p;++i)
for(int j=0;j<=m;++j)
for(int k=0;k<p;++k)
{
if(!f[i][j][k]) continue;
for(int d=0;d<=min(m-j,cnt[i]*9);++d)// 当前考虑贡献 d 到数位和
(f[i+1][j+d][(k+d*i)%p]+=f[i][j][k]*g[i][d])%=mod;
}
for(int i=1;i<=m;++i) (f[p][i][0]+=f[p][i-1][0])%=mod;
for(int i=0;i<=m;++i) cout<<f[p][i][0]<<' ';
return 0;
}