Idea

数位DP. 注意加一点记录. 第一次写的时候把\(i\)写成了1, 调整了好久, 第二个错误是没注意到13是要连续的. 因此Code可以再简化.

Code

#include <bits/stdc++.h>
using namespace std;
#define MAXN 16
#define F(i, a, b) for(int i=(a); i<=(b);i++)
#define Fd(i, a, b) for(int i=(a);i>=(b);i--)
#define int long long
int f[15][15][15][15][3][3];
int num[13];
int rom[6]={1,10, 9, 12, 3, 4}; // remainder
int dfs(int pos, int rem, int now, int sta, int lim, int zero){
   #define REM f[pos][rem][now][sta][lim][zero]
   if(pos == 0){
   	if(rem==0 && sta==1) return 1; 
   	else return 0;
   }
   if(REM != -1) return REM;
   int sum = 0; int up = lim ? num[pos] : 9;
   F(i,0,up){
   	int nsta = (sta || (i==3 && now==1))?1:0;
   	int nmod = (rem+rom[(pos-1)%6]*i)%13;
   	sum += dfs(pos-1, nmod, i, nsta, (lim && (up==i)), (i==0&&zero));
   	
   }
   REM = sum;
   return sum;
}
int sol(int x) {
   memset(f, -1, sizeof f);
   int tot=0;
   while(x){ num[++tot]=x%10,x/=10;}
   // printf("%d\n",tot);
   return dfs(tot,0,-1,0,1,1);
}
signed main(){
   int n ; 
   while(cin>>n){
   	cout<<sol(n)<<endl; 
   	
   }
   return 0;
}

原文地址：http://www.cnblogs.com/augpath/p/16922308.html