数位dp学习笔记

wzb13958817049 · 2026-07-28 08:40:08 · 算法·理论

Part1

一种最基础的数位dp，例如 windy数 此类的数位dp入门题，一般我写的都是记忆化搜索，没怎么写过递推。

将 P2602 [ZJOI2010] 数字计数 作为例题来讲解，从高位往低位 dp，我们分开来求每个数出现的次数，首先设计状态 f[N][N] 表示还剩下 i 位前面已经有了 j 个 now。

• 什么时候需要将状态压进dp状态中：如果前面所有数的选值对于后面的数有影响，比如 \% k 为零的数的个数或 last 会对这一位的选数有影响，不同的状态会对答案产生影响例如这题的记录 i 出现的个数。亦或者说你要求什么就把什么存到状态里即可。

放个模板： ::::info[code]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll T,n,l,r,c[20],f[20][20],ans,now;
ll dp(int dep,int sta,int lim,int qd0){
    if(qd0==0) sta=0;
    if(dep==0) return sta;
    if(!lim && qd0 && f[dep][sta]!=-1) return f[dep][sta];
    int up=lim?c[dep]:9;
    ll res=0;
    for(int i=0;i<=up;++i){
        res+=dp(dep-1,sta+(i==now),lim&&(i==up),qd0||(i!=0));
    }
    if(!lim && qd0) f[dep][sta]=res;
    return res;
}
ll calc(ll x){
    int cnt=0;
    while(x){c[++cnt]=x%10;x/=10;}
    return dp(cnt,0,1,0);
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>l>>r;
    for(int i=0;i<=9;i++){
        now=i;memset(f,-1,sizeof f);
        cout<<calc(r)-calc(l-1)<<" ";
    }
    return 0;
}

::::

Part 2

例如 P2106 Sam 数 当数位达到 10^{18} 的时候就很自然的想到用矩阵快速幂来优化数位dp。 ::::info[code]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
ll k,cnt;
struct matrix{
    ll a[15][15],nn,mm;
    matrix(ll nn=0,ll mm=0):nn{nn},mm{mm}{memset(a,0,sizeof a);}
    matrix friend operator*(const matrix &x,const matrix &y){
        matrix z(x.nn,y.mm);
        for(int i=1;i<=x.nn;i++)
            for(int j=1;j<=y.mm;j++)
                for(int k=1;k<=x.mm;k++)
                    z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
        return z;
    }
    matrix friend operator^(matrix &x,const long long&y){
        matrix z(x.nn,x.mm),tmp=x;
        for(int i=1;i<=x.nn;i++) z.a[i][i]=1;
        for(ll i=y;i;i>>=1){
            if(i&1) z=z*tmp;
            tmp=tmp*tmp;
        }
        return z;
    }
}x(10,10),ans(1,10);
int main(){
    ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
    cin>>k;
    for(int i=1;i<=10;i++){
        for(int j=max(1,i-2);j<=min(10,i+2);j++){
            x.a[i][j]=1;
        }
    }
    if(k==1){cout<<10;return 0;}
    for(int i=2;i<=10;i++) ans.a[1][i]=1;
    x=x^(k-1);
    ans=ans*x;
    for(int i=1;i<=10;i++) cnt=(cnt+ans.a[1][i])%mod;
    cout<<cnt;
    return 0;
}

::::

Part 3

当我们需要求的值并不是个数，而是满足条件的数的平方和或 \sum if(i) 这种类型时，我们需要记录多个变量来维护。

例题

link，我们不管题目中所需要的条件，因为这是 Part 1 的事情，那么我们考虑如何维护平方和那么我们就要维护三个值，个数，总和，平方和。

前两个值好维护，令 node tmp=dp(dep-1,lim&&(i==up)) 那么根据 (a+b)^2=a^2+b^2+2ab 可知

res.cnt+=tmp.cnt;
res.sum+=tmp.cnt*i*ten[dep-1]+tmp.sum;
res.ans+=tmp.ans+i*i*ten[dep-1]*ten[dep-1]*tmp.cnt+2*i*ten[dep-1]*tmp.sum;

::::info[code]

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,a,b,ans,c[22],ten[18];
struct node{
    long long f,g,h;
    node(){
        f=0,g=0,h=0;
    }
    node(long long _f,long long _g,long long _h):f(_f),g(_g),h(_h){}
}f[22][8][8];
node dp(int dep,int sta1,int sta2,int lim){
    if(dep==0) return {sta1!=0 && sta2!=0,0,0};
    if(lim==0 && f[dep][sta1][sta2].f!=-1) return f[dep][sta1][sta2];
    int up=lim?c[dep]:9;
    node ret{0,0,0};
    for(int i=0;i<=up;i++){
        if(i!=7){
            node tmp=dp(dep-1,(sta1+i)%7,(sta2*10+i)%7,lim&&(i==up));
            ret.f+=tmp.f;ret.f=ret.f%mod;
            ret.g+=((tmp.f*i)%mod*ten[dep-1]%mod+tmp.g)%mod;ret.g=ret.g%mod;
            ret.h+=(i*i%mod*ten[dep-1]%mod*ten[dep-1]%mod*tmp.f%mod+2*i*ten[dep-1]%mod*tmp.g%mod+tmp.h)%mod;ret.h=ret.h%mod;
        }
    }
    if(lim==0) f[dep][sta1][sta2]=ret;
    return ret;
}
long long calc(long long x){
    int cnt=0;
    while(x){c[++cnt]=x%10;x/=10;}
    return (dp(cnt,0,0,1).h)%mod;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ten[0]=1;
    for(int i=1;i<=17;i++) ten[i]=(ten[i-1]*10)%mod;
    cin>>n;memset(f,-1,sizeof f);
    for(int i=1;i<=n;i++){
        cin>>a>>b;
        cout<<(calc(b)-calc(a-1)+mod)%mod<<"\n";
    }
    return 0;
}

::::

Part 4

如何优化掉一个 B？例如 P3281 [SCOI2013] 数数。

我们先正常思考我们发现其实在我们枚举的时候有很大一部分情况的后记状态的答案是相同的，那么只需要用同一个 node tmp 来转移即可。 ::::info[code]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+5,mod=20130427;
struct node{
    ll ans,sum,cnt;
    //ans为答案
    //sum为以第i位开头的
}f[N][2];
ll B,n,m,a[N],s[N];
node dp(int dep,bool lim,bool qd0){
    if(dep==0) return {0,0,1};
    if(lim==0 && f[dep][qd0].cnt!=-1) return f[dep][qd0];
    ll up=lim?a[dep]:B-1;
    node res={0,0,0};
    for(int i=0;i<=up;i+=max(1ll,up)){
        node tmp=dp(dep-1,lim&&(i==up),qd0||(i!=0));
        if(!qd0&&!i){res.ans+=tmp.ans;res.ans%=mod;continue;}
        res.ans+=tmp.ans;res.ans%=mod;
        res.cnt+=tmp.cnt;res.cnt%=mod;
        res.sum+=tmp.sum+tmp.cnt*s[dep]%mod*i;res.sum%=mod;
    }
    node tmp=dp(dep-1,0,1);
    if(up>1){
        res.sum+=(up-1)*tmp.sum+tmp.cnt*s[dep]%mod*(up*(up-1)/2)%mod;res.sum%=mod;
        res.ans+=tmp.ans*(up-1);res.ans%=mod;
        res.cnt+=tmp.cnt*(up-1);res.cnt%=mod;
    }
    res.ans+=res.sum;res.ans%=mod;
    if(lim==0) f[dep][qd0]=res;
    return res;
}
ll calc(){
    memset(f,-1,sizeof f);
    return dp(n,1,0).ans;
}
signed main(){
    ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
    cin>>B;for(int i=1,pw=1;i<N;pw=pw*B%mod,i++) s[i]=(s[i-1]+pw)%mod;
    cin>>n;for(int i=n;i>=1;i--) cin>>a[i];
    a[1]--;
    for(int i=1;i<=n;i++){
        if(a[i]<0){
            a[i]+=B;
            a[i+1]--;
        }
    }
    ll ans=mod-calc();
    if(a[2]==-1) ans=0;
    cin>>n;for(int i=n;i>=1;i--) cin>>a[i];
    ans=ans+calc();
    cout<<ans%mod;
    return 0;
}

::::

Part 5

有限状态下的数位 dp。例如淘金对于一个位置 (i,j) 会变为 (f(i),f(j))，其中 f(i) 表示 i 数位上各位数的乘积，只能分解成 2^a \times 3^b \times 5^c \times 7^d 爆搜后发现有用的状态只有 14672 个，然后数位 dp 即可，最后用堆来维护 cnt(i) \times cnt(j) 的前 k 大值。 ::::info[code]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll n,k,c[15],f[15][40][25][15][15],prime[6]={0,2,3,5,7},cc,cnt,a[15000],b[15000];
//2 3 5 7
ll num[10][6]={
    {0,0,0,0,0},//0
    {0,0,0,0,0},//1
    {0,1,0,0,0},//2
    {0,0,1,0,0},//3
    {0,2,0,0,0},//4
    {0,0,0,1,0},//5
    {0,1,1,0,0},//6
    {0,0,0,0,1},//7
    {0,3,0,0,0},//8
    {0,0,2,0,0},//9
};
ll dp(int dep,int cnt2,int cnt3,int cnt5,int cnt7,bool lim,bool qd0){
    if(dep==0) return cnt2==0 && cnt3==0 && cnt5==0 && cnt7==0;
    if(lim==0 && qd0 && f[dep][cnt2][cnt3][cnt5][cnt7]!=-1) return f[dep][cnt2][cnt3][cnt5][cnt7];
    ll up=lim?c[dep]:9;
    ll res=0;
    for(int i=0;i<=up;i++){
        if(i==0 && qd0) continue;
        res+=dp(dep-1,cnt2-num[i][1],cnt3-num[i][2],cnt5-num[i][3],cnt7-num[i][4],lim&&(i==up),qd0||(i!=0));
    }
    if(lim==0 && qd0) f[dep][cnt2][cnt3][cnt5][cnt7]=res;
    return res;
}
void init(int pos,ll x){
    if(x>n) return ;
    a[++cc]=x;
    for(int i=pos;i<=4;i++){
        init(i,x*prime[i]);
    }
}
ll calc(ll x){
    ll cnt2=0,cnt3=0,cnt5=0,cnt7=0;
    while(x%2==0) cnt2++,x/=2;
    while(x%3==0) cnt3++,x/=3;
    while(x%5==0) cnt5++,x/=5;
    while(x%7==0) cnt7++,x/=7;
    return dp(cnt,cnt2,cnt3,cnt5,cnt7,1,0);
}
struct node{
    ll i,j;
    bool operator<(const node &o)const{
        return b[i]*b[j]<b[o.i]*b[o.j];
    }
};
int main(){
    ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
    cin>>n>>k;cnt=0;
    init(1,1);memset(f,-1,sizeof f);
    while(n){c[++cnt]=n%10;n/=10;}
    for(int i=1;i<=cc;i++) b[i]=calc(a[i]);b[1]--;
    sort(b+1,b+1+cc,greater<ll>());
    priority_queue<node> q;
    for(int i=1;i<=cc;i++) q.push({i,1});
    ll ans=0;
    while(k){
        node u=q.top();
        q.pop();
        ans=(ans+b[u.i]*b[u.j])%mod;
        k--;
        if(u.j!=cc) q.push({u.i,u.j+1});
    }
    cout<<ans;
    return 0;
}

::::

Part 6

不能直接数位 dp 的题目，需要算贡献或需要枚举一些值来帮助 dp。

例题 CF908G

且因为 a_i,b_i < k 所以 \binom{a_i}{b_i} \equiv 0 \mod k 当且仅当 a_i < b_i。

稍微容斥一下就是总方案数减去不为 0 的方案数也就是所有的 a_i \ge b_i 的方案数，那么就变为了 k 进制 dp，1 \leq a \leq n,0 \leq b \leq m 有多少对这样的数对就可以写出一个暴力的版本，时间复杂度 O(\log_k n \times k^2) 代码如下，可以通过弱化版 P6669。 ::::info[暴力]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr ll N=65,mod=1e9+7;
ll T,k,n,m,f[N][2][2],c1[N],c2[N];
ll dp(int dep,int lim1,int lim2){
    if(dep==0) return 1;
    if(f[dep][lim1][lim2]!=-1) return f[dep][lim1][lim2];
    int up1=lim1?c1[dep]:k-1,up2=lim2?c2[dep]:k-1;
    ll res=0;
    for(int a=0;a<=up1;a++){
        for(int b=0;b<=min(up2,a);b++){
            res+=dp(dep-1,lim1&&(a==up1),lim2&&(b==up2));
            res%=mod;
        }
    }
    f[dep][lim1][lim2]=res;
    return res;
}
signed main(){
    ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
    cin>>T>>k;
    while(T--){
        cin>>n>>m;
        m=min(n,m);
        ll ans=(n%mod*((m+1)%mod)%mod-(m%mod)*((m-1)%mod)%mod*500000004ll%mod+mod)%mod;
        ll cnt1=0,cnt2=0;
        while(n){
            c1[++cnt1]=n%k;
            n/=k;
        }
        while(m){
            c2[++cnt2]=m%k;
            m/=k;
        }
        memset(f,-1,sizeof f);
        for(int i=cnt2+1;i<=cnt1;i++) c2[i]=0;
        cout<<(ans-dp(cnt1,1,1)+mod+1)%mod<<"\n";
    }
    return 0;
}

:::: 写起来细节还是比较多的，需要加一是因为会把 (0,0) 多减了，再考虑如何使用 Part 4 来优化，那么我们就记录一个状态他的后继状态如 dp(dep-1,1,1) 出现了几次，然后分类讨论即可，该取模时就取模。 ::::info[code]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr ll N=65,mod=1e9+7,inv2=500000004;
ll T,k,n,m,f[N][2][2],c1[N],c2[N];
ll dp(int dep,int lim1,int lim2){
    if(dep==0) return 1;
    if(f[dep][lim1][lim2]!=-1) return f[dep][lim1][lim2];
    ll up1=lim1?c1[dep]:k-1,up2=lim2?c2[dep]:k-1;
    // ll res=0;
    // for(int a=0;a<=up1;a++){
    //  for(int b=0;b<=min(up2,a);b++){
    //      res+=dp(dep-1,lim1&&(a==up1),lim2&&(b==up2));
    //      res%=mod;
    //  }
    // }
    ll t11=dp(dep-1,1,1),t10=dp(dep-1,1,0),t01=dp(dep-1,0,1),t00=dp(dep-1,0,0);
    ll tot=(up2>=up1?(2+up1)*(1+up1)%mod*inv2%mod:((2+up2)*(1+up2)%mod*inv2%mod+(up2+1)*(up1-up2)%mod)%mod);
    ll c11=0,c10=0,c01=0,c00=0;
    if(lim1 && lim2){
        c11=up1>=up2?1:0;
        c10=min(up1+1,up2);
        c01=up1>=up2?up1-up2:0;
        c00=tot-c11-c10-c01;
    }else if(lim1){
        c10=min(up1,up2)+1;
        c00=tot-c10;
    }else if(lim2){
        c01=up1>=up2?up1-up2+1:0;
        c00=tot-c01;
    }else c00=tot;
    c11=(c11%mod+mod)%mod;c10=(c10%mod+mod)%mod;
    c01=(c01%mod+mod)%mod;c00=(c00%mod+mod)%mod;
    f[dep][lim1][lim2]=(t11*c11+t10*c10+t01*c01+t00*c00)%mod;
    return f[dep][lim1][lim2];
}
signed main(){
    ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
    cin>>T>>k;
    while(T--){
        cin>>n>>m;
        m=min(n,m);
        ll ans=(n%mod*((m+1)%mod)%mod-(m%mod)*((m-1)%mod)%mod*inv2%mod+mod)%mod;
        ll cnt1=0,cnt2=0;
        while(n){
            c1[++cnt1]=n%k;
            n/=k;
        }
        while(m){
            c2[++cnt2]=m%k;
            m/=k;
        }
        for(int i=0;i<=cnt1;i++) f[i][1][1]=f[i][0][1]=f[i][1][0]=f[i][0][0]=-1;
        for(int i=cnt2+1;i<=cnt1;i++) c2[i]=0;
        cout<<(ans-dp(cnt1,1,1)+mod+1)%mod<<"\n";
    }
    return 0;
}

::::

P13125 [GCJ 2019 Finals] Won't sum? Must now

根据附件给的题解模拟的，但是时间复杂度也是错的，剪枝草过去的（也有可能是我时间复杂度分析错了），需要写出一种能高效判断是否存在 S=A+B，A 与 B 均为回文数，那么不妨设 A \ge B，那么 A 的位数只能是 |S| 或 |S|-1，再枚举 B 的位数，时间复杂度为 O(n)。

然后最麻烦的是考虑进位，我们搜索时需要记录 (l,lc,rc) 分别表示正在处理的低位 l，(下表从 0 开始)，r=la-1-l 表示高位的下表，lc 表示从 l 向 l+1 位的进位，rc 表示 r 向 r+1 位的进位。

结束条件：如果 l>r 那么判断 lc 是否等于 rc 即可也就是最后一次的进位是否相同，如果 l==r 那么 a_l=a_r 枚举 da 表示这一位的数值为多少根据等式：

对于一般的，枚举 nlc 与 nrc 表示下一个 lc 与 rc 只需要满足，低位：(nlc 从 l 位向 l+1 位)

高位：(nrc 从 r-1 位向 r 位)

然后通过枚举 da 来推算出 db 再判断是否合法即可，时间复杂度为 O(2^n n^2)，你发现 dfs 的次数只跟进位有关系所以只有 O(4^{n/2})=O(2^n)。再根据附件所说的最小的回文数不会超过 10801 所以最多会算 207 次。 ::::info[code]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr ll N=1e6+5,inf=1e18;
inline bool check(string s){
    if(s.empty()) return 0;
    int l=0,r=s.size()-1;
    while(l<r) if(s[l++]!=s[r--]) return 0;
    return 1;
}
string sub(string a,string b){
    string res;
    ll n=a.size(),m=b.size();
    ll jw=0;
    for(int i=0;i<n;i++){
        int da=a[n-1-i]-'0';
        int db=(i<m?b[m-1-i]-'0':0);
        int s=da-db-jw;
        if(s<0) s+=10,jw=1;
        else jw=0;
        res.push_back(s+'0');
    }
    while(res.size()>1 && res.back()=='0') res.pop_back();
    reverse(res.begin(),res.end());
    return res;
}
namespace two{
    int ls,la,lb;
    vector<ll> s,a,b;
    //lc 从 l-1 位向 l 的进位
    //rc 从 r 位向 r+1 位的进位
    bool dfs(int l,int lc,int rc){
        int r=la-l-1;
        if(l>r) return lc==rc;
        if(l==r){
            for(int da=(l==la-1?1:0);da<=9;da++){
                if(a[l]!=-1 && a[l]!=da) continue;
                for(int db=(l<lb?(l==lb-1?1:0):0);db<=(l<lb?9:0);db++){
                    if(l<lb && b[l]!=-1 && b[l]!=db) continue;
                    int sum=da+db+lc;
                    if(sum%10==s[l] && sum/10==rc){
                        a[l]=da;
                        if(l<lb) b[l]=db;
                        return 1;
                    }
                }
            }
            return 0;
        }
        //nlc 从 l 位向 l+1 位
        //nrc 从 r-1 位向 r 位
        for(int nlc=0;nlc<=1;nlc++){
            for(int nrc=0;nrc<=1;nrc++){
                //da+db+lc=s[l]+10*nlc
                int tl=s[l]+10*nlc-lc;//da+db
                if(tl<0 || tl>18) continue;
                //ad+db+nrc=s[r]+10*rc
                int tr=s[r]+10*rc-nrc;
                if(tr<0 || tr>18) continue;
                for(int da=(l==0?1:0);da<=9;da++){
                    if(a[l]!=-1 && a[l]!=da) continue;
                    if(a[r]!=-1 && a[r]!=da) continue;
                    int bl=tl-da;
                    if(l>=lb){
                        if(bl) continue;
                    }else{
                        int mnb=(l==lb-1?1:0);
                        if(bl<mnb || bl>9) continue;
                        if(b[l]!=-1 && b[l]!=bl) continue;
                        if(b[lb-1-l]!=-1 && b[lb-1-l]!=bl) continue;
                    }
                    int br=tr-da;
                    if(r>=lb){
                        if(br) continue;
                    }else{
                        int mnb=(r==lb-1?1:0);
                        if(br<mnb || br>9) continue;
                        if(b[r]!=-1 && b[r]!=br) continue;
                        if(b[lb-1-r]!=-1 && b[lb-1-r]!=br) continue;
                    }
                    if(l<lb && r<lb && lb-1-l==r && bl!=br) continue;
                    int old_al=a[l],old_ar=a[r];
                    int old_bl=(l<lb?b[l]:0),old_bll=(l<lb?b[lb-1-l]:0);
                    int old_br=(r<lb?b[r]:0),old_brr=(r<lb?b[lb-1-r]:0);
                    a[l]=a[r]=da;
                    if(l<lb) b[l]=b[lb-1-l]=bl;
                    if(r<lb) b[r]=b[lb-1-r]=br;
                    if(dfs(l+1,nlc,nrc)) return 1;
                    a[l]=old_al;a[r]=old_ar;
                    if(l<lb){b[l]=old_bl;b[lb-1-l]=old_bll;}
                    if(r<lb){b[r]=old_br;b[lb-1-r]=old_brr;}
                }
            }
        }
        return 0;
    }
    inline bool solve(string S,string& A,string& B){
        ls=S.size();s.resize(ls);
        for(int i=0;i<ls;i++) s[i]=S[ls-1-i]-'0';
        for(la=ls;la>=max(1,ls-1);la--){
            for(lb=la;lb>=1;lb--){
                a.assign(la,-1);
                b.assign(lb,-1);
                if(dfs(0,0,(la<ls?s[ls-1]:0))){
                    A.resize(la);
                    for(int i=0;i<la;i++) A[i]=a[la-1-i]+'0';
                    B.resize(lb);
                    for(int i=0;i<lb;i++) B[i]=b[lb-1-i]+'0';
                    return 1;
                }
            }
        }
        return 0;
    }
}
vector<string> zw;
inline void solve(){
    string s;cin>>s;
    if(check(s)){
        cout<<s<<"\n";
        return ;
    }
    string a,b;
    if(two::solve(s,a,b)){
        cout<<a<<" "<<b<<"\n";
        return ;
    }
    for(auto k:zw){
        string tmp=sub(s,k);
        if(check(tmp)){
            cout<<k<<" "<<tmp<<"\n";
            return ;
        }
        if(two::solve(tmp,a,b)){
            cout<<k<<" "<<a<<" "<<b<<"\n";
            return ;
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll T;cin>>T;
    for(int i=1;i<=10801;i++){
        string t=to_string(i);
        if(check(t)) zw.push_back(t);
    }
    for(int _=1;_<=T;_++){
        cout<<"Case #"<<_<<": ";
        solve();
    }
    return 0;
}

::::