概述
一般是求小于等于数字N的某些特征数字个数，或者是区间[L,R]的之间的某些特征数字个数，后者一般可以转换成求差的方式来做。
模板
数字处理函数：
int f(int num){
int ans;
int pos = 0;
while(num){
digit[++pos]=num%10;
num=num/10;
}
return dfs( pos, s , true );
}
其中：
digit为处理串的每个数位的数值。
s为初始的状态。
如果有其他限定条件，dfs中可以增加参数。
DFS函数：
int dfs(int l, int s, bool jud) {
if ( l==-1 ) return s == target_s;
if ( !e && ~f[l][s] ) return f[l][s];
int ans = 0;
int nex = e ? digit[i] : 9;
for (int d = 0; d <= nex; ++d)
ans += dfs( l-1 , new_s( s,d ) , e && d==nex );
return jud ? ans : f[l][s] = ans;
}
其中：
f为记忆化数组；
l为当前处理串的第l位（权重表示法，也即后面剩下l+1位待填数）；
s为之前数字的状态（如果要求后面的数满足什么状态，也可以再记一个目标状态t之类，for的时候枚举下t）；
jud表示之前的数是否是上界的前缀（即后面的数能否任意填）。
for循环枚举数字时，要注意是否能枚举0，以及0对于状态的影响，有的题目前导0和中间的0是等价的，但有的不是，对于后者可以在dfs时再加一个状态变量z，表示前面是否全部是前导0，也可以看是否是首位，然后外面统计时候枚举一下位数。It depends.
于是关键就在怎么设计状态。当然做多了之后状态一眼就可以瞄出来。
前导零的判断：
int dfs(bool zero)
......
ans+=dfs(zero&&i==0)//不区分前导零与零
ans+=dfs(zero&&i==0&&l>1)//区分前导零与零
题目：
A. 【CF55D】
题意：
给定区间[L,R]，求区间完美数字的个数。（一个数字是完美数字当且仅当该数字可整除其所有数位上的非零数）
思路：
位数上的数字只需要考虑2~9，因此用一个数字1<<8来表示有哪些数字出现过。
如果一个数是所有位数的倍数，那么一定是其最小公倍数的倍数，其所有的最小公倍数是2520，所以求和的时候直接对2520取余。
dp[l][cnt][sum]，l为数字长度，cnt为位数上有哪些数，sum为数字和。
dfs(int l,int cnt,int sum,bool jud)，jud为是否为边界。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
int digit[20];
LL dp[20][(1<<8)][2520];
LL dfs(int l,int cnt,int sum,bool jud){
if(l==0){
for(int i=2;i<=9;i++)
if( (cnt&(1<<(i-2))) && (sum%i) ){
return 0;
}
return 1;
}
if(!jud && dp[l][cnt][sum] != -1) return dp[l][cnt][sum];
int nes = jud ? digit[l] : 9;
LL pos = 0 ;
for(int i=0;i<=nes;i++){
pos += dfs(l-1 , i<2 ? cnt : (cnt|(1<<(i-2))) , ((sum*10)+i)%2520 , jud&&(i==digit[l]));
}
if(!jud)
dp[l][cnt][sum]=pos;
return pos;
}
LL f(LL k){
LL ans;
int pos = 0;
while(k){
digit[++pos]=k%10;
k=k/10;
}
ans = dfs(pos,0,0,true);
return ans;
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
memset(dp,-1,sizeof(dp));
int t;
LL m,n;
cin>>t;
while(t--){
cin>>m>>n;
cout<<f(n)-f(m-1)<<endl;
}
return 0;
}
B. 【HDU4352】
题意：
寻找[L,R]中间所有数字串中LIS（最长上升子序列）为K的数字和。
思路：
LIS运用动态规划可以在O(nlogn)的时间复杂度解决，此略。
因为最多只有0～9十个数字，因此可以预处理。
sta为LIS的状态，siz[sta]中保存LIS的长度（即二进制中1的个数），nex[sta][l]为在sta中插入数字l之后的LIS状态。
dp[l][sta][k]：l为数字长度，sta为当前LIS的状态，k为所要求的LIS长度。
dfs(int l,int sta,bool zero,bool jud)：zero判断是否为前导零，jud为是否为边界。
注意：dp[l][sta][k]中，k并不是必须的，然而因为本题样例组数过多且k很小，所以选择增加一维表状态而不是每次都初始化以节约时间。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
int digit[20],siz[1<<10],nex[1<<10][10];
LL dp[66][(1<<10)][11];
int Cas,k;
LL dfs(int l,int sta,bool zero,bool jud){
if(l==0) return siz[sta]==k;
if(!jud&&dp[l][sta][k]!=-1)return dp[l][sta][k];
int nes = jud ? digit[l] : 9;
LL ans = 0;
for(int i=0;i<=nes;i++)
ans+= dfs(l-1, (zero&&i==0) ? 0 : nex[sta][i] , zero&&i==0 , jud&&i==nes);
if(!jud)dp[l][sta][k]=ans;
return ans;
}
LL f(LL num){
int pos = 0;
while(num){
digit[++pos]=num%10;
num/=10;
}
return dfs(pos,0,true,true);
}
int find_nex(int status,int num){
for(int i=num;i<10;i++)
if (status&(1<<i)) return (status^(1<<i)|(1<<num));
return status|(1<<num);
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
memset(dp,-1,sizeof(dp));
for(int i=0;i<(1<<10);i++){
siz[i]=0;
for(int j=0;j<10;j++){
if(i&(1<<j))siz[i]++;
nex[i][j]=find_nex(i,j);
}
}
int t;
LL m,n;
cin>>t;
while(t--){
cin>>m>>n>>k;
cout<<"Case #"<<++Cas<<": ";
cout<<f(n)-f(m-1)<<endl;
}
return 0;
}
C. 【HDU2089】
题意：
[L,R]中，不含4或62的数字个数。
思路：
dp[l][six]：l为数字长度，six为最后一位数字是否为6。
dfs(int l,bool six,bool jud)，jud判断是否为边界。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int digit[10],dp[10][2],vis[10][2];
int dfs(int l,bool six,bool jud){
if(l==0) return 1;
if(!jud&&vis[l][six])return dp[l][six];
int len = jud ? digit[l] : 9;
int nes = 0;
for(int i=0;i<=len;i++){
if((i==4)||(six&&i==2)) continue;
nes += dfs(l-1 , i==6 , jud&&(i==len));
}
if(!jud){
vis[l][six]=true;
dp[l][six]=nes;
}
return nes;
}
int f(int k){
memset(dp,0,sizeof(dp));
memset(vis,0,sizeof(vis));
int pos = 0;
while(k){
digit[++pos]=k%10;
k=k/10;
}
int ans = dfs(pos,false,true);
return ans;
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int m,n;
while(scanf("%d%d",&m,&n)&&(m+n)){
cout<<f(n)-f(m-1)<<endl;
}
return 0;
}
D. 【HDU3555】
题意：
数字中含有49的数字个数。
思路：
偷了下懒，用C题的代码求不含49的个数，然后做差，居然过了= =b。其实这道题打表都行= =b。
代码：
#include <cstring>
#include <cstdio>
#include <iostream>
#define LL long long
using namespace std;
int digit[25];
LL dp[25][2];
LL dfs(int l,bool num,bool jud){
if(l==0) return 1;
if(!jud && dp[l][num]!=-1) return dp[l][num];
LL ans=0;
int nex = jud ? digit[l] : 9;
for(int i=0;i<=nex;i++){
if(num&&i==9)continue;
ans += dfs(l-1,i==4,jud&&i==nex);
}
if(!jud) dp[l][num]=ans;
return ans;
}
LL f(LL num){
int pos = 0;
while(num){
digit[++pos]=num%10;
num/=10;
}
return dfs(pos,false,true);
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int T;
LL n;
memset(dp,-1,sizeof(dp));
scanf("%d",&T);
while(T--){
cin>>n;
cout<<n-f(n)+1<<endl;
}
return 0;
}
E. 【HDU3252】
题意：
数字[L,R]中，round number数字的个数。round number即数字转换成二进制后0的个数大于等于1的个数。
思路：
digit数组中直接保存该数字的二进制形式。
dp[l][cnt1][cnt2][zero]：l为数字长度，cnt1为数字0的数字个数，cnt2为数字1的数字个数，zero判断是否为前导零。
dfs(int l,int cnt1,int cnt2,bool zero,bool jud)：jud判断是否为边界。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int digit[35],dp[35][35][35][2],pos;
int dfs(int l,int cnt1,int cnt2,bool zero,bool jud){
if(l==0) return cnt1>=cnt2;
if(!jud&&dp[l][cnt1][cnt2][zero]!=-1) return dp[l][cnt1][cnt2][zero];
int nex = jud ? digit[l] : 1;
int ans = 0;
for(int i=0;i <= nex;i++){
ans += dfs( l-1 , zero ? 0 : cnt1+(i==0) ,cnt2+(i==1) , zero&&(i==0) , jud&&i==nex );
}
if(!jud)dp[l][cnt1][cnt2][zero]=ans;
return ans;
}
int f(int num){
pos = 0;
while(num){
digit[++pos]=num%2;
num>>=1;
}
return dfs(pos,0,0,true,true);
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
memset(dp,-1,sizeof(dp));
int m,n;
cin>>m>>n;
cout<<f(n)-f(m-1)<<endl;
return 0;
}
F. 【HDU3709】
题意：
统计区间[L,R]中，balanced number的数字个数。balanced number即对于任意一个数字串，假设其有一个数字位，它左边的数字乘距离的和等于它右边的数字乘距离的和，则其为balanced number。
思路：
枚举作为平衡点的数字位数，最后要减掉（pos-1）因为对于0,计算了0,00,000...重复计算了pos次，只需要保留一次。
dp[l][o][pos]：长度为l，平衡点位置为o时的当前状态（pos为0时表示平衡，pos>0则为左边的沉，pos<0则为右边的沉）
dfs(int l,int o,int pos,bool jud)：jud判断是否为边界。
注意只要pos<0就可以返回false。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long
int digit[20];
LL dp[20][20][2000];
LL dfs(int l,int o,int pos,bool jud){
if( l==0 ) return pos == 0;
if( pos<0 ) return 0;
if(!jud && dp[l][o][pos] >= 0)return dp[l][o][pos];
int nex = jud ? digit[l] : 9;
LL ans = 0;
for(int i=0;i<=nex;i++)
ans += dfs( l-1 , o , pos+i*(l-o) , jud && i==nex );
return jud ? ans : dp[l][o][pos] = ans;
}
LL f(LL num){
int pos = 0;
while(num){
digit[++pos]=num%10;
num/=10;
}
LL ans = 0;
for(int i=1;i<=pos;i++)
ans += dfs(pos,i,0,true);
ans = ans - pos + 1;
return ans;
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
memset(dp,-1,sizeof(dp));
int T;
LL m,n;
cin>>T;
while(T--){
cin>>m>>n;
cout<<f(n)-f(m-1)<<endl;
}
return 0;
}
G. 【HDU3652】
题意：
[1,n]的含数字13且为13的倍数的数字个数。
思路：
dp[l][mod][iso][has]：l为数字长度，mod为当前数字对13的取余值，iso为是否存在，has为最后一位是否为数字1。
int dfs(int l,int mod,bool iso,bool has,bool jud)：jud判断是否为边界值。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int digit[11];
int dp[11][13][2][2];
int dfs(int l,int mod,bool iso,bool has,bool jud){
if(l==0)return (has && !mod);
if(!jud && dp[l][mod][iso][has])return dp[l][mod][iso][has];
int nex = jud ? digit[l] : 9;
int ans = 0;
for(int i=0;i<=nex;i++){
ans += dfs( l-1 , (mod*10+i)%13 , i==1 , has||(iso&&i==3) , jud && i==nex );
}
return jud ? ans : dp[l][mod][iso][has]=ans;
}
int f(int num){
int pos = 0;
while(num){
digit[++pos]=num%10;
num/=10;
}
return dfs(pos,0,false,false,true);
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int n;
while(~scanf("%d",&n)){
printf("%d\n",f(n));
}
return 0;
}
H. 【HDU4734】
题意：
对于每个数字x，都有一个F（x）值，让你求[0,B]中，函数值小于等于F（A）的数字个数。
思路：
首先计算出F（a）。
dp[l][sum]：l为当前数字长度，sum为F（A）减去之前枚举的数字的数字差（如果差为正则代表F（A）大）。
dfs(int l,int sum,bool jud)：jud判断是否为边界。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int digit[10],dp[10][100005],CASE;
int dfs(int l,int sum,bool jud){
if( l==0 ) return sum >= 0;
if( sum<0 )return 0;
if( !jud && dp[l][sum]>=0 ) return dp[l][sum];
int nex = jud ? digit[l] : 9;
int ans = 0;
for(int i=0 ; i<=nex ; i++)
ans += dfs( l-1 , sum-i*(1<<(l-1)) , jud&&i==nex );
return jud ? ans : dp[l][sum] = ans;
}
inline int f(int num,int cas){
int pos = 0;
while(num){
digit[++pos]=num%10;
num/=10;
}
return dfs(pos,cas,true);
}
inline int count(int a){
int pos = 0,ans = 0;
while(a){
ans+=(a%10)*(1<<pos++);
a/=10;
}
return ans;
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
memset(dp,-1,sizeof(dp));
int T,a,b,cas;
scanf("%d",&T);
while(T--){
scanf("%d%d",&a,&b);
cas = count(a);
//cout<<">"<<cas<<endl;
printf("Case #%d: ",++CASE);
printf("%d\n",f(b,cas));
}
return 0;
}
I. 【ZOJ3494】
题意：
区间[L，R]的数字转换成BCD之后，不含有forbidden code（即长度不超过20的01组成的数字串）的数字个数。
思路：
forbidden code可以用trie树储存。
dp[l][pos]：l为数字长度，pos为树上的位置。
dfs(int l,int pos,bool zero,bool jud)：zero判断是否为前导零（注意和数字0区分），jud判断是否为边界。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int M = 10005,MOD=1000000009;
#define LL long long
int idx;
char str[25];
int bcd[2005][10];
LL dp[205][2005];
int digit[205],len,n;
struct Trie{
Trie *next[2];
Trie *fail;
int isword,kind;
};
Trie *que[M],s[M];
Trie *NewNode(){
Trie *tmp=&s[idx];
tmp->next[0]=tmp->next[1]=NULL;
tmp->isword=0;
tmp->fail=NULL;
tmp->kind=idx++;
return tmp;
}
void Insert(Trie *root,char *s,int l){
Trie *p=root;
for(int i=0; i<l; i++){
if(p->next[s[i]-'0']==NULL) p->next[s[i]-'0']=NewNode();
p=p->next[s[i]-'0'];
}
p->isword=1;
}
void Bulid_fail(Trie *root){
int head=0,tail=0;
que[tail++]=root;
root->fail=NULL;
while(head<tail){
Trie *tmp=que[head++];
for(int i=0; i<2; i++){
if(tmp->next[i]){
if(tmp==root) tmp->next[i]->fail=root;
else{
Trie *p=tmp->fail;
while(p!=NULL){
if(p->next[i]){
tmp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL) tmp->next[i]->fail=root;
}
if(tmp->next[i]->fail->isword)
tmp->next[i]->isword=tmp->next[i]->fail->isword;
que[tail++]=tmp->next[i];
}
else if(tmp==root) tmp->next[i]=root;
else tmp->next[i]=tmp->fail->next[i];
}
}
}
//状态当前在状态pre,经过一个数字num之后到达哪个状态
//如果不合法，返回-1
int BCD(int pre,int num){
if(s[pre].isword) return -1;
int cur=pre;
for(int i=3;i>=0;i--){
int k=(num>>i)&1;
if(s[cur].next[k]->isword) return -1;
else cur=s[cur].next[k]->kind;
}
return cur;
}
void Get_next(){
for(int i=0;i<idx;i++){
for(int j=0;j<10;j++){
bcd[i][j]=BCD(i,j);
}
}
}
LL dfs(int l,int pos,bool zero,bool jud){
if(pos<0) return 0;
if(l==0)return 1;
if(!jud&&dp[l][pos]>=0)return dp[l][pos];
LL ans = 0;
int nex = jud ? digit[l] : 9;
for(int i=0;i<=nex;i++)
ans += dfs( l-1 , zero&&i==0&&l>1 ? pos : bcd[pos][i] , zero&&i==0 , jud&&i==nex );
ans%=MOD;
return jud ? ans : dp[l][pos]=ans;
}
LL cal(char *s,int l){
memset(dp,-1,sizeof(dp));
for(int i=1;i<=l;i++) digit[l-i+1]=s[i-1]-'0';
dfs(l,0,true,true);
}
char A[205],B[205];
void sub(char *s,int len){
for(int i=len-1;i>=0;i--){
if(s[i]=='0') s[i]='9';
else{
s[i]--;
break;
}
}
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t;
scanf("%d",&t);
while(t--){
idx=0;
Trie *root=NewNode();
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%s",str);
Insert(root,str,strlen(str));
}
Bulid_fail(root);
Get_next();
scanf("%s",A);
sub(A,strlen(A));
scanf("%s",B);
cout<<((cal(B,strlen(B))-cal(A,strlen(A)))%MOD+MOD)%MOD<<endl;
}
return 0;
}
J. 【HDU4507】
题意：
区间[L,R]中，和7无关的数字的平方和是多少？含7的数、数位和为7的倍数、数为7的倍数都是和7有关的数字。
思路：
dp[len][sum][remain]：len为长度，sum为数位和，remain为前缀和。
dfs(int len,int sum,int remain,bool jud)jud判断是否为边界。
维护三个数字：个数，和，平方和。
a[1]^2 + a[2]^2 + … + a[n]^2，新式是 (a[1]+b)^2 + (a[2]+b)^2 + … + (a[n]+b)^2，按照这样的原理求前缀的平方和。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
typedef pair< int,pair<LL,LL> > PILL;//< count , < sum，square sum> >
#define F first
#define S second
#define MP make_pair
const int mod = 1e9+7, mx = 20;
int digit[mx];
LL pow10[20];
PILL dp[20][7][7];
bool vis[20][7][7];
//边界的答案不同
PILL dfs(int len,int sum,int remain,bool jud){
if(!len)
if(sum&&remain)
return MP(1,MP(0LL,0LL));
else
return MP(0,MP(0LL,0LL));
if(!jud&&vis[len][sum][remain])
return dp[len][sum][remain];
PILL res = MP(0,MP(0LL,0LL));
int nex = jud ? digit[len] : 9;
for(int i=0;i<=nex;i++){
if(i==7) continue;
PILL ans = dfs(len-1,(sum+i)%7,(remain*10+i)%7,jud&&i==nex);
LL pref = i * pow10[len-1] % mod;
res.F += ans.F;
res.F %= mod;
res.S.F += ans.S.F + pref * ans.F;
res.S.F %= mod;
res.S.S += ans.S.S + pref * pref % mod * ans.F + 2 * pref * ans.S.F;
res.S.S %= mod;
}
if(!jud){
vis[len][sum][remain]=true;
dp[len][sum][remain]=res;
}
return res;
}
LL f(LL a){
memset(vis,0,sizeof(vis));
int len=0;
while(a){
digit[++len]=a%10;
a=a/10;
}
return dfs(len,0,0,true).S.S;
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
pow10[0]=1;
for(int i=1;i<20;i++)
pow10[i]=pow10[i-1]*10%mod;
int t;
scanf("%d",&t);
while(t--){
LL a,b,ans;
scanf("%lld%lld",&a,&b);
ans = (f(b)-f(a-1)+mod)%mod;
printf("%lld\n",ans);
}
return 0;
}
K. 【SPOJ10606】
题意：
求[L,R]中positive integer的数字个数。positive integer就是对于一个数字串，偶数数字各有奇数个，奇数数字各有偶数个。
思路：
用一个三进制数字表示每个数字的状态，0为未出现过，1为出现过奇数次，2为出现过偶数次。
dp[l][s]：l为数字长度，s为当前所有数字出现的状态。
dfs(int l,int s,bool zero,bool jud)：zero判断是否为前导零，jud判断是否为边界。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long
int dp[20][60000];
int digit[20];
LL pos[11];
void init(){
pos[0]=1;
for(int i=1;i<=10;i++)
pos[i]=pos[i-1]*3;
}
bool judge(int s){
for(int i=9;i>=0;i--){
if(i%2==0 && s/pos[i]==2) return false;
if(i%2==1 && s/pos[i]==1) return false;
s%=pos[i];
}
return true;
}
LL dfs(int l,int s,bool zero,bool jud){
if(l==0){
if(judge(s))
return 1;
return 0;
}
if(!jud && dp[l][s]>=0)return dp[l][s];
int nes = jud ? digit[l] : 9;
LL ans = 0;
for(int i=0;i<=nes;i++)
ans += dfs(l-1 , zero&&i==0 ? 0 : ((s%pos[i+1])/pos[i]==2 ? s-pos[i] : s+pos[i]), zero&&i==0 , jud&&i==nes);
return jud ? ans : dp[l][s] = ans;
}
LL f(LL num){
int pos=0;
while(num){
digit[++pos]=num%10;
num/=10;
}
return dfs(pos,0,true,true);
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
init();
int T;
LL a,b;
cin>>T;
memset(dp,-1,sizeof(dp));
while(T--){
cin>>a>>b;
cout<<f(b)-f(a-1)<<endl;
}
return 0;
}
参考资料
刘聪《浅谈数位类统计问题》
高逸涵《数位计数问题解法研究》
http://www.cnblogs.com/jffifa/archive/2012/08/17/2644847.html