SGU 390 BZOJ 2063 我爸是李刚

Link

Solution

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

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利