GGAutomaton's Blog
0%

数位dp模板

发表于 分类于 ，

通用模板： 

1
2
3
4
5
6
7
8
9
10
11
12
LL dfs(int p,/*其他状态*/,bool lead/*前导0*/,bool limit/*压上界*/) {
	if (p==-1) return 1;//条件和返回值依题目而定
	if (!limit && !lead && dp[p][stat]!=-1) return dp[p][stat];
	int up=limit?a[p]:9;
	LL ans=0;
	for (int i=0;i<=up;i++) {
		if (...) continue;
		ans+=dfs(p-1,/*新状态*/,lead && i==0,limit && i==a[p]);
	}
	if (!lead && !limit) dp[p][stat]=ans;
	return ans;
}

练手题：HDU4507 恨7不成妻
要求维护平方和 

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
#include<iostream>
#include<cstdio>
#include<cstring>
typedef long long LL;
const int P=1e9+7;
struct node {
	LL cnt,sum,sqr;
} dp[25][7][7];
LL pow10[25];
int a[25],nn;
int T;
node dfs(int p,int res1,int res2,bool limit) {
	if (p==-1) return (node){(res1 && res2),0,0};
	if (!limit && dp[p][res1][res2].cnt!=-1) return dp[p][res1][res2];
	int up=limit?a[p]:9;
	node ans=(node){0,0,0};
	node tmp;
	for (int i=0;i<=up;i++) {
		if (i==7) continue;
		tmp=dfs(p-1,(res1+i)%7,(res2*10+i)%7,limit && (i==a[p]));
		ans.cnt+=tmp.cnt;if (ans.cnt>=P) ans.cnt-=P;
		ans.sum=(ans.sum+tmp.sum+pow10[p]*i%P*tmp.cnt)%P;
		ans.sqr=(pow10[p]*pow10[p]%P*i*i%P*tmp.cnt+2*pow10[p]*i%P*tmp.sum+tmp.sqr+ans.sqr)%P;
	}
	if (!limit) dp[p][res1][res2]=ans;
	return ans;
}
inline LL solve(LL x) {
	nn=0;
	while (x) {
		a[nn++]=x%10;
		x/=10;
	}
	return dfs(nn-1,0,0,1).sqr;
}
int main() {
	for (int i=0;i<20;i++) {
		for (int j=0;j<7;j++) {
			for (int k=0;k<7;k++) dp[i][j][k].cnt=-1;
		}
	}
	pow10[0]=1;
	for (int i=1;i<20;i++) pow10[i]=(pow10[i-1]*10)%P;
	scanf("%d",&T);
	while (T--) {
		LL l,r;
		scanf("%lld %lld",&l,&r);
		printf("%lld\n",((solve(r)-solve(l-1))%P+P)%P);
	}
	return 0;
}