2016陕西省省赛-magicnum-数位dp

题目链接

题意：
网易在线笔试出了这么一道题：
Celin一直认为万物皆数，他总会花上很多的时间去研究和数相关的一些问题。最近他在研究一种神奇的数，这种数包含以下3个特征：
(1) 这个数至少包含(‘2’,’3’, ‘5’)中的任意一个数字;
(2) 这个数不能出现’18’；
(3) 这个数能被7整除。
如217，280，1393，9520均为同时满足三个条件的神奇的数。
而140，798不符合条件(1)，518，1183不符合条件(2)，12，1727不符合条件(3)，这些数均不是Celin要找的神奇的数。
给出一个范围[N,M]，Celin想知道在范围内(包括N和M两个边界在内)一共有多少个符合条件的神奇的数。
出题人认为这个题目的数据范围太友好了，于是决定加大一点数据范围，卡掉部分不是特别好的做法。
1 <= N <= M <= 10^210

思路：数位dp模板题，dp[i][j][pre][k],表示在第i位，有无出现2,3,5，前一位是pre，膜7是k的数有多少个。这题去年比赛时的标程写炸了……简直可怕……

注意，这份代码并不能在上面的链接里ac,西交的oj只给了32M……一记忆化就会boom，想要ac应该是跟标程一样用递推的写法（好吧我也没有试过）……只是我拿改过的标程比对了一下，这份代码的答案是正确的。

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
99
100
101
102
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
long long mod=1e9+7;
long long dp[220][3][10][10];        // 位，出现2,3,5，前一位， 模7 
int dig[220];
long long fac[220];
string n,m;
long long dfs(int pos,int pre,int er,int k,int inf)
{
	if(pos<1)
	{
		if(er==1  && k==0 && !inf)return dp[pos][er][pre][k]=1;
		 else if(er==1  && k==0)return 1;
		return 0;
	}
	if(dp[pos][er][pre][k]!=-1 && !inf)return dp[pos][er][pre][k];
	long long rt=0;
	int endd=inf?dig[pos]:9;
	for(int i=0;i<=endd;i++)
	{
		if(i==8 && pre==1)continue;
		if(i==2 || i==3 || i==5)
		 rt=(rt+dfs(pos-1,i,1,(k+i*fac[pos-1])%7,inf && i==endd))%mod;
		else
		 rt=(rt+dfs(pos-1,i,er,(k+i*fac[pos-1])%7,inf && i==endd))%mod;	
	}
	if(!inf)
	return dp[pos][er][pre][k]=rt;
 	else return rt;
}
long long solve(string s)
{
	int l=s.size();
	for(int i=0;i<l;i++)dig[i+1]=s[l-i-1]-'0';
	return dfs(l,0,0,0,1); 
}
string sub(string str1,string str2)
{
    string str;
    int tmp=str1.length()-str2.length();
    int cf=0;
    for(int i=str2.length()-1;i>=0;i--)
    {
        if(str1[tmp+i]<str2[i]+cf)
        {
            str=char(str1[tmp+i]-str2[i]-cf+'0'+10)+str;
            cf=1;
        }
        else
        {
            str=char(str1[tmp+i]-str2[i]-cf+'0')+str;
            cf=0;
        }
    }
    for(int i=tmp-1;i>=0;i--)
    {
        if(str1[i]-cf>='0')
        {
            str=char(str1[i]-cf)+str;
            cf=0;
        }
        else
        {
            str=char(str1[i]-cf+10)+str;
            cf=1;
        }
    }
    str.erase(0,str.find_first_not_of('0'));
    return str;
}
int main()
{
	freopen("data.in","r",stdin);
	fac[1]=10;
	fac[0]=1;
	for(int i=1;i<=219;i++)fac[i]=(fac[i-1]*10)%7;
	int T;
   	scanf("%d",&T);
   	memset(dp,-1,sizeof(dp));
   	while(T--)
   	{
   		cin>>n;
   		n=sub(n,"1");
   		if(n=="")n="0";
		long long ans1=solve(n);
		cin>>m;
		long long ans2=solve(m);
		printf("%lld\n",(ans2-ans1+mod)%mod);
	}
	return 0;
 }