模板有2：
版1：：
void init() { dp[0][0] = 1; for (int i = 1; i <=14 ; ++i)//第i位 for (int j = 0; j <= 9; ++j)//第i-1位的可能值 for (int k = 0; k <= 9; ++k)//第i位的可能值 if (j != 3 && j!=8) dp[i][j] += dp[i - 1][k]; }同如上的三层循环，把每一位的所需情况遍历出来，直接满足条件时求和即可，适用于状态转移方程简单的情况 板2：:
static int dfs(int s,int m,int f,boolean u) {//s是当前位数，m，f或更多变量表示约束条件，u表示是否到达边界 if(s==0){ return m==0&&f==2?1:0; } if(!u&&dp[s][m][f]!=-1) { return dp[s][m][f]; } int len=u?dig[s]:9;//所取进位制（k进制），9处应该为k-1 int ans=0; for(int i=0;i<=len;i++) { int t=(m*10+i)%13; int tf=f; if(f==1&&i==3) { tf=2; } else if(f==0&&i==1) { tf=1; } else if(f==1&&i!=1) { tf=0; } ans+=dfs(s-1,t,tf,u&&(i==len));//状态转移方程 } if(!u) { dp[s][m][f] = ans; } return ans; } static int cal(int n) {讲每一位储存到dig（位数）数组里面，根据进制选择不同，除数应发生变化 int k=0; for(int i=0;i<15;i++)dig[i]=0; while(n!=0) { dig[++k]=n%10; n/=10; } for(int i=0;i<15;i++) { for(int j=0;j<15;j++) { for(int r=0;r<15;r++) { dp[i][j][r]=-1; } } } return dfs(k,0,0,true); } 这个板子的好处是灵活，可以应对基本所有的数位dp，只要设计好状态转移方程，选择合适的记录值创建dp数组，即可。
要理解的话，把上面那几个题搞出来就基本完事了
标题所示题目解答，按顺序如下
1009
import java.util.*;public class Main{ static Scanner in=new Scanner(System.in); public static void main(String[] args) { // TODO Auto-generated method stub while(in.hasNext()) { long x=in.nextInt(); long a[]=new long[20]; long res=0; int len=0; long dig=0; long rad=1; long tail=0; long t=1; a[0]=0; for (int i = 1; i <= 19; i++){ a[i]=a[i-1]*10+t; t*=10; } while(x!=0) { dig=x%10; x/=10; ++len; if(dig > 1) { res+=rad+dig*a[len-1]; } else if(dig==1) { res+=tail+a[len-1]+1; } tail = tail + dig*rad; rad*=10; } System.out.println(res); } } } 4278
import java.util.*;public class Main { //变量声明 static Scanner in=new Scanner(System.in); static long dp[][]=new long[15][10]; static long d[]=new long [15]; static long x; //初始化 static void init() { dp[0][0] = 1; for (int i = 1; i <=14 ; ++i) for (int j = 0; j <= 9; ++j) for (int k = 0; k <= 9; ++k) if (j != 3 && j!=8) dp[i][j] += dp[i - 1][k]; } //数位dp static long dp(long n) { long ans = 0; int len = 0; while (n!=0) { ++len; d[len] = n % 10; n /= 10; } d[len + 1] = 0; for (int i = len; i >= 1; --i) { for (int j = 0; j < d[i]; ++j) { ans += dp[i][j]; } if (d[i]==3 || d[i]==8) return ans; } return ans; } public static void main(String[] args) { // TODO Auto-generated method stub init(); while(in.hasNext()) { long x=in.nextLong(); if(0==x) { break; } System.out.println(x+": "+dp(x)); } }} 2089
import java.util.*;public class Main { //变量声明 static Scanner in=new Scanner(System.in); static long dp[][]=new long[10][10]; static long d[]=new long [10]; static long x; //初始化 static void init() { dp[0][0] = 1; for (int i = 1; i <= 7; ++i) for (int j = 0; j <= 9; ++j) for (int k = 0; k <= 9; ++k) if (j != 4 && !(j == 6 && k == 2)) dp[i][j] += dp[i - 1][k]; } //数位dp static long dp(long n) { int ans = 0; int len = 0; while (n!=0) { ++len; d[len] = n % 10; n /= 10; } d[len + 1] = 0; for (int i = len; i >= 1; --i) { for (int j = 0; j < d[i]; ++j) { if (d[i + 1] != 6 || j != 2) ans += dp[i][j]; } if (d[i] == 4 || (d[i + 1] == 6 && d[i] == 2)) return ans; } return ans; } public static void main(String[] args) { // TODO Auto-generated method stub init(); while(in.hasNext()) { long x=in.nextLong(),y=in.nextLong(); if(0==x&&0==y) { break; } System.out.println(dp(y+1)-dp(x)); } }} 3652
import java.util.*;public class Main { static Scanner in=new Scanner(System.in); static int dp[][][]=new int[15][15][15]; static int dig[]=new int[15]; static int dfs(int s,int m,int f,boolean u) { if(s==0){ return m==0&&f==2?1:0; } if(!u&&dp[s][m][f]!=-1) { return dp[s][m][f]; } int len=u?dig[s]:9; int ans=0; for(int i=0;i<=len;i++) { int t=(m*10+i)%13; int tf=f; if(f==1&&i==3) { tf=2; } else if(f==0&&i==1) { tf=1; } else if(f==1&&i!=1) { tf=0; } ans+=dfs(s-1,t,tf,u&&(i==len)); } if(!u) { dp[s][m][f] = ans; } return ans; } static int cal(int n) { int k=0; for(int i=0;i<15;i++)dig[i]=0; while(n!=0) { dig[++k]=n%10; n/=10; } for(int i=0;i<15;i++) { for(int j=0;j<15;j++) { for(int r=0;r<15;r++) { dp[i][j][r]=-1; } } } return dfs(k,0,0,true); } public static void main(String[] args) { // TODO Auto-generated method stub int n; while(in.hasNext()) { n=in.nextInt(); int x=cal(n); System.out.println(x); } }} 3555
#include#include #include using namespace std;__int64 dp[25][3];void Init(){ memset(dp,0,sizeof(dp)); dp[0][0] = 1; int i; for(i = 1;i<=22;i++) { dp[i][0] = dp[i-1][0]*10-dp[i-1][1]; dp[i][1] = dp[i-1][0]; dp[i][2] = dp[i-1][2]*10+dp[i-1][1]; }}__int64 solve(__int64 n){ __int64 i,tem = n,len = 0,a[25],flag = 0,ans = 0; while(n) { a[++len] = n%10; n/=10; } a[len+1] = 0; for(i = len;i;i--) { ans+=dp[i-1][2]*a[i]; if(flag) ans+=dp[i-1][0]*a[i]; if(!flag && a[i]>4) ans+=dp[i-1][1]; if(a[i+1] == 4 && a[i] == 9) flag = 1; } return ans;}int main(){ int t; __int64 n; scanf("%d",&t); Init(); while(t--) { scanf("%I64d",&n); printf("%I64d\n",solve(n+1)); } return 0;}
4507
#include "cstdio"#include "math.h"#include "cstring"#define mod 1000000007LL#define LL long longstruct status{ LL cnt,sum,sqsum; status() {cnt=-1;sum=sqsum=0;} status(LL cnt,LL sum,LL sqsum):cnt(cnt),sum(sum),sqsum(sqsum) {}}dp[20][10][10];LL digit[20],p[25];status dfs(int len,int re1,int re2,bool fp){ if(!len) return re1!=0&&re2!=0?status(1,0,0):status(0,0,0); if(!fp&&dp[len][re1][re2].cnt!=-1) return dp[len][re1][re2]; int fpmax=fp?digit[len]:9; status ans;ans.cnt=0; for(int i=0;i<=fpmax;i++) { if(i==7) continue; status next=dfs(len-1,(re1+i)%7,(re2*10+i)%7,fp&&i==fpmax); ans.cnt+=next.cnt; ans.cnt%=mod; ans.sum+=(next.sum+((p[len]*i)%mod)*next.cnt%mod)%mod; ans.sum%=mod; ans.sqsum+=(next.sqsum+((2*p[len]*i)%mod)*next.sum)%mod; ans.sqsum%=mod; ans.sqsum+=((next.cnt*p[len])%mod*p[len]%mod*i*i%mod); ans.sqsum%=mod; } if(!fp) dp[len][re1][re2]=ans; return ans;}LL f(LL x){ int len=0; while(x) { digit[++len]=x%10; x/=10; } status tt=dfs(len,0,0,true); return tt.sqsum;}int main(){ int T; LL l,r; scanf("%d",&T); p[1]=1; for(int i=2;i<=20;i++) p[i]=(p[i-1]*10)%mod; while(T--) { scanf("%I64d%I64d",&l,&r); LL ans=f(r); ans-=f(l-1); printf("%I64d\n",(ans%mod+mod)%mod); }} 3252
#include#include #include #include using namespace std;int val[] = { 1,-1 };int dig[40];int dp[40][2][2][2][40];//位数，前面是否全是0，这一位是是谁，more 的正负，more 的绝对值int a, b;int sw(int site, bool r, int more, bool f) { if (site == 0) { //cout <<"ans:"<< more << endl; return more >= 0?1:0; } if (!f&&dp[site][r][dig[site]][more>=0][abs(more)] != -1) { return dp[site][r][dig[site]][more >= 0][abs(more)]; } int len = f ? dig[site] : 1; int ans = 0; for (int i = 0; i <= len; i++) { bool rr = r || i == 1; int tem = rr?val[i]:0; ans += sw(site - 1, rr,(more + tem), f && (i == len)); } if (!f) { dp[site][r][dig[site]][more >= 0][abs(more)] = ans; } return ans;}void deal() { for (int i = 0; i < 40; i++) { dig[i] = 0; for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { for (int v = 0; v < 2; v++) { for (int o = 0; o < 40; o++) { dp[i][j][k][v][o] = -1; } } } } } int site = 0; while (b != 0) { dig[++site] = b % 2; b /= 2; } int ans = sw(site, false,0, true); --a; site = 0; for (int i = 0; i < 40; i++) { dig[i] = 0; } while (a != 0) { dig[++site] = a % 2; a /= 2; } cout << ans - sw(site,false, 0, true);}int main(int argc, char *argv) { ios::sync_with_stdio(false); cin >> a >> b; deal(); //cin >> a; return 0;}