数位 dp

考虑比较难以记录某个状态下的最大值，可以直接枚举一个数 $d$ 计算强制它为最大值的方案和。

设 $c$ 为 $d$ 在某个长度为 $n$ 的数中的出现次数，要求满足 $c\geq \lceil\frac{n}{2}\rceil$。

设 $c’$ 为 $d$ 以外数码的出现次数，即需要满足 $c-c’\geq 0$。

所以设 $dp_{i,j}$ 表示前 $i$ 个数位，$c-c’=j$ 的方案数，再按照数位 dp 的套路记录上下界啥的就可以转移了。

但是很遗憾，算重了。

需要容斥掉那些存在两个数码都恰好占一半的情况。

同样是枚举这两个数，然后发现这一次合法的数中只包含这两个字符，所以可以记录 $g_{i,j}$ 表示考虑到前 $i$ 位，其中一个数码填了 $j$ 次的方案数，同样套路转移即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<cstdio>
#include<cstring>
#define rep(a,b,c) for(int c(a);c<=(b);++c)
typedef long long ll;
const int M=20;
int a[20],n;ll L,R;
ll dp[20][50][10][2],g[20][20][2][2];
inline ll G(int d1,int d2)
{
	int d[2]={d1,d2};
	memset(g,0,sizeof(g));
	rep(0,1,i)
	{
		g[1][i][i][0]=1;
		if(d[i]<=a[1])g[1][i][i][1]=1;
	}
	rep(1,n-1,i)
	{
		rep(0,i,j)
		{
			rep(0,1,k)
			{
				rep(0,1,c)
				{
					int nj=j+c;
					g[i+1][nj][c][0]+=g[i][j][k][0];
					if(d[c]<=a[i+1])
					{
						if(d[c]==a[i+1]){g[i+1][nj][c][1]+=g[i][j][k][1];}
						else{g[i+1][nj][c][1]+=g[i][j][k][0];}
					}
				}
			}
		}
	}
	ll ans=0;
	if(!(n&1))
	{
		rep(0,1,i)if(d[i]&&d[i]<=a[n])
		{
			ans+=g[n][n>>1][i][d[i]==a[n]];
		}
	}
	for(int i=2;i<n;i+=2)
	{
		rep(0,1,j)if(d[j])
		{
			ans+=g[i][i>>1][j][0];
		}
	}
	return ans;
}
inline ll DP(int d)
{
	memset(dp,0,sizeof(dp));
	rep(0,9,i)
	{
		dp[1][(i==d?1:-1)+M][i][0]=1;
		if(i<=a[1])dp[1][(i==d?1:-1)+M][i][1]=1;
	}
	rep(1,n-1,i)
	{
		rep(-i,i,j)
		{
			rep(0,9,k)
			{
				rep(0,9,c)
				{
					int nj=j+(c==d?1:-1);
					dp[i+1][nj+M][c][0]+=dp[i][j+M][k][0];
					if(c<=a[i+1])
					{
						if(c==a[i+1])dp[i+1][nj+M][c][1]+=dp[i][j+M][k][1];
						else dp[i+1][nj+M][c][1]+=dp[i][j+M][k][0];
					}
				}
			}
		}
	}
	ll ans=0;rep(0,n,j)
	{
		rep(1,a[n]-1,c)ans+=dp[n][j+M][c][0];
		ans+=dp[n][j+M][a[n]][1];
	}
	rep(1,n-1,i)rep(0,i,j)rep(1,9,c)ans+=dp[i][j+M][c][0];
	return ans;
}
inline ll S(ll x)
{
	n=0;while(x)a[++n]=x%10,x/=10;ll ans=0;
	rep(0,9,i)ans+=DP(i);rep(0,9,i)rep(i+1,9,j)ans-=G(i,j);
	return ans;
}
int main()
{
	scanf("%lld%lld",&L,&R);
	printf("%lld\n",S(R)-S(L-1));
}