SGU 390 BZOJ 2063 我爸是李刚

发表于 | 更新于

Link

Solution

不能用区间减法做了。。因为最后总能剩下那么一点，就不满足区间减法了。。 没办法，只好在计算的时候同时卡上界和下界了。 先不考虑卡上界和下界，现在找一下独立的子问题：通用的f[len][i]f[len][i]表示有lenlen位，最高位为ii的方案数还可行吗？似乎不行了，原因还是一样：最后剩下的那么一点点，导致子问题不是独立的了。 那就加一维f[len][i][rem]f[len][i][rem]表示统计完了前两维<len,<i< len,< i的情况，剩下了一些数字数位和为remrem，能分的组数。然后似乎还不行：这个状态没有记录已经有的数位和，所以没法转移。那好说，注意到第二维表示成最高位的数字是意义不明(也许也可以做，但做法确实不显然)的，那就把第二维改成已经有的数位和。这样f[len][sum][rem]f[len][sum][rem]表示前lenlen位的数位和为sumsum，之前剩下的数位和为remrem能分出的组数，就可以计算了。 注意要记录是否需要卡上下界，而且需要卡上下界的每种状态都是至多计算一次，不需要记忆化，如果记忆化了在BZOJ上就MLE了。 因为两个界都卡的只会有第一层DFS计算，剩下的都是卡一边的。而卡一边的只能从len+1len+1的卡一边的转移过来。 附l=1,r=1018l=1,r=10^{18}的需要卡上下界的状态计数 

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
c[1][0][0]<1,0>=1
c[2][0][0]<1,0>=1
c[3][0][0]<1,0>=1
c[4][0][0]<1,0>=1
c[5][0][0]<1,0>=1
c[6][0][0]<1,0>=1
c[7][0][0]<1,0>=1
c[8][0][0]<1,0>=1
c[9][0][0]<1,0>=1
c[10][0][0]<1,0>=1
c[11][0][0]<1,0>=1
c[12][0][0]<1,0>=1
c[13][0][0]<1,0>=1
c[14][0][0]<1,0>=1
c[15][0][0]<1,0>=1
c[16][0][0]<1,0>=1
c[17][0][0]<1,0>=1
c[18][0][0]<1,0>=1
c[1][1][483]<0,1>=1
c[2][1][483]<0,1>=1
c[3][1][483]<0,1>=1
c[4][1][483]<0,1>=1
c[5][1][483]<0,1>=1
c[6][1][483]<0,1>=1
c[7][1][483]<0,1>=1
c[8][1][483]<0,1>=1
c[9][1][483]<0,1>=1
c[10][1][483]<0,1>=1
c[11][1][483]<0,1>=1
c[12][1][483]<0,1>=1
c[13][1][483]<0,1>=1
c[14][1][483]<0,1>=1
c[15][1][483]<0,1>=1
c[16][1][483]<0,1>=1
c[17][1][483]<0,1>=1
c[18][1][483]<0,1>=1
c[19][0][0]<1,1>=1
126628280529273434

Tips

数位DP不只有区间减法，有可能需要一次算两边。

Code

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
#include "lucida"
int lbit[20],rbit[20];
int Convert(int64 x,int bit[]) {
	int len=0;
	for(;x;x/=10)
		bit[++len]=x%10;
	return len;
}
struct Node {
	int64 cnt,rem;
	Node():cnt(-1),rem(0){}
	Node(int64 cnt,int rem):cnt(cnt),rem(rem){}
	Node &operator +=(const Node &a) {
		cnt+=a.cnt;
		rem=a.rem;
		return *this;
	}
}f[21][171][1011];
int64 l,r,M;
Node DFS(int len,int sum,int rem,bool lm,bool rm) {
	//sum是数位之和9*18=162
	if(len==0)
		return (sum+rem>=M)?Node(1,0):Node(0,sum+rem);
	if(!lm && !rm && f[len][sum][rem].cnt!=-1)
		return f[len][sum][rem];
	Node res(0,rem);
	for(int i=(lm?lbit[len]:0),ei=(rm?rbit[len]:9);i<=ei;++i) 
		res+=DFS(len-1,sum+i,res.rem,lm && i==lbit[len],rm && i==rbit[len]);
	if(!lm && !rm) f[len][sum][rem]=res;
	return res;
}
int main() {
	freopen("input","r",stdin);
	is>>l>>r>>M;
	Convert(l,lbit);
	int len=Convert(r,rbit);
	int64 Ans=DFS(len,0,0,1,1).cnt;
	os<<Ans<<'\n';
	return 0;
}