#include <bits/stdc++.h> using namespace std; int digit[12]; int dp[12][13][3]; int DFS(int pos, int pre, int have, int flag) { if(pos == -1) return have == 2 && pre == 0; if(!flag && dp[pos][pre][have] != -1) return dp[pos][pre][have]; int end = flag ? digit[pos] : 9; int ans = 0; int tmp; for(int i=0; i<=end; i++) { int nhave = have; if(have == 1) { if(i == 3) nhave = 2; else if( i != 1) nhave = 0; } if(have != 2 && i == 1) nhave = 1; tmp = (pre * 10 + i) % 13; ans += DFS(pos-1, tmp, nhave, i==end && flag); } if(!flag) dp[pos][pre][have] = ans; return ans; } int Cal(int n) { int pos = 0; while(n) { digit[pos++] = n % 10; n /= 10; } return DFS(pos - 1, 0, 0, 1); } int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int n; while(~scanf("%d", &n)) { memset(dp, -1, sizeof(dp)); cout<<Cal(n)<<endl; } return 0; }
原文:http://blog.csdn.net/dojintian/article/details/44652395