这个题目Yveh送给xyx做胡策题的, 但是我这种只做过二进制数位dp裸题的丝薄选手, 直接懵逼了好不好。。

实际上是数位dp的例题, 好几年前的论文里就有了。

话说这个题目真是非常的魔性。

题目链接

题目大意

区间\([l,r]\), 每个数的价值是各个数位的数字之和, 如果相邻的\(x\)个数价值和大于等于\(m\), 则这\(x\)个数可以分为一组, 求\([l,r]\)最多分为几组。

解题报告

因为数的价值是各个数位的数字之和, 所以考虑进行数位dp.

具体的,考虑“数位树”, 在十进制下也就是一个十叉树, 那么对于一个\([l,r]\)的询问,可以转换成\((l',r')\), 在十叉树上, 这个开区间中的数可以看作若干满二叉子树。

因为树高是\(\text{log }n\)级别的,所以这些满十叉树的个数是\(\text{log }n\) 级别的。

考虑预处理每棵满十叉树对答案可能产生的贡献, 因为一颗满十叉树可能分成若干组后, 贡献一个\(\leqslant m\)的一个余数, 不妨设计这样的状态:

\(f[i][j][k]\) 表示满十叉树根节点的深度是\(i\), 子树根节点到根的路径和为\(j\), 在前方提供\(k\)的余数, 可以贡献的分组数。

\(g[i][j][k]\) 表示满十叉树根节点的深度是\(i\), 子树根节点到根的路径和为\(j\), 在前方提供\(k\)的余数, 贡献若干组后剩余的余数。

现在就得到了每棵满十叉树在不同情况下对答案的贡献、对后方子树的影响, 消耗的时间复杂度是\(O(\log^2n * 10^2 * m)\)

查询的时候,在十叉树上查询\((l',r')\)两个区间端点的\(\text{lca}\), 分别从左侧向上爬,在从\(\text{lca}\)向右端点爬 。

统计答案, 复杂度是\(O(\log n * 10)\)的。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
typedef long long ll;
ll f[20][180][1010],l,r;
int g[20][180][1010],m,a[25],b[25],sa[25],sb[25],la,lb,ln,tst;
inline void solve() {
la=lb=ln=0;
rep(i,0,9*18) rep(j,0,m-1) f[1][i][j]=(i+j>=m),g[1][i][j]=(i+j>=m?0:i+j);
rep(i,2,18) rep(j,0,9*(18-i+1)) rep(k,0,m-1) {
int tmp=k; f[i][j][k]=0;
rep(x,0,9) f[i][j][k]+=f[i-1][j+x][tmp],tmp=g[i-1][j+x][tmp];
g[i][j][k]=tmp;
}
--l, ++r;
while (l) a[++la]=l%10, l/=10;
while (r) b[++lb]=r%10, r/=10;
sa[lb+1]=0,sb[lb+1]=0; vep(i,lb,1)
sa[i]=sa[i+1]+a[i],sb[i]=sb[i+1]+b[i];
ln=lb; while (a[ln]==b[ln]) --ln; int tmp=0; ll as=0;
rep(i,1,ln-1) rep(j,a[i]+1,9)
as+=f[i][sa[i+1]+j][tmp],tmp=g[i][sa[i+1]+j][tmp];
rep(i,a[ln]+1,b[ln]-1) as+=f[ln][sa[ln+1]+i][tmp],tmp=g[ln][sa[ln+1]+i][tmp];
vep(i,ln-1,1) rep(j,0,b[i]-1)
as+=f[i][sb[i+1]+j][tmp],tmp=g[i][sb[i+1]+j][tmp];
printf("%lld\n",as);
}
int main() {
scanf("%lld%lld%d",&l,&r,&m);
solve();
return 0;
}

留言