数位DP练习

故事起源于10.25日某比赛，一道数位DP题目被我们做傻了，回来复习一下。

好朋友

问题链接：https://ac.nowcoder.com/acm/problem/19327

题意：求l-r中包含子序列‘007’的数字个数

解：详见注释

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int t;
ll l,r;
ll a[20];
ll f[20][20][2][2];

ll dp(int pos,int s0,bool h,bool have,bool lim)
{  ///pos代表从高到低枚举位数 s0代表前面有多少个0(前导0不算）
   ///h代表前面是否出现过子序列‘007’，lim表示是否达到了最大值
   ///have表示是否出现过非0的数字，只有出现过非0数字才能开始统计s0
    if(!pos) return h;
    if(lim && f[pos][s0][h][have]) return f[pos][s0][h][have];
    int x = lim ? 9 : a[pos];
    ll ans = 0;
    for(int i = 0;i <= x; ++i)
        ans += dp(pos - 1, s0 + (have && i == 0), 
				  h || (s0 >= 2 && i == 7), i || have,lim || i < x);
    if(lim) f[pos][s0][h][have] = ans;
    return ans;
}

ll solve(ll x)
{
	int pos = 0;
	while(x) a[++pos] = x % 10,x /= 10;
	return dp(pos,0,0,0,0);
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>t;
	ll ans = 0;
	while(t--)
	{
		cin>>l>>r;
		ans ^= solve(r) - solve(l - 1);
	}	
	cout<<ans<<'\n';
	return 0;
}

同类分布

题目链接：https://ac.nowcoder.com/acm/problem/19888

题意：给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。

解：详见注释

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll l,r;
int a[20],tot,x;
int ma[2][200][20][200];
ll f[2][200][20][200];

ll dp(int lim,int s,int pos,int v)
{   ///s代表位数和，pos代表枚举的位数，v代表当前数字%x之后的余数，判断是否能整除
	if(!pos) return  !s && !v;
	if(ma[lim][s][pos][v] == tot) return f[lim][s][pos][v];
	ma[lim][s][pos][v] = tot;
	int l = max(0,s - (pos - 1) * 9);
	int r = min(lim ? 9 : a[pos],s);
	ll t = 0;
	for(int i = l;i <= r; ++i)
		t += dp(lim | (i < a[pos]),s - i,pos - 1,(v * 10 + i) % x);
	return f[lim][s][pos][v] = t;
}

ll solve(ll k)
{
	int pos = 0;
	while(k) a[++pos] = k % 10,k /= 10;
	ll ans = 0;
	for(x = 1;x <= pos * 9; ++x)
		tot++,ans += dp(0,x,pos,0);
	return ans;
}

int main()
{
	ll l,r;
	cin>>l>>r;
	cout<<solve(r) - solve(l - 1)<<'\n';
	return 0;
}