题意求能够整除和包含13的数字。
这个比较简单，保留余数及1，然后标记前面是否出现过13就行。
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set> 10 using namespace std; 11 #define N 100000 12 #define LL long long 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 LL n,dp[22][15][2][2]; 18 int d[22]; 19 LL dfs(int i,bool e,int r,bool o,bool p) 20 { 21 if(i==-1) 22 { 23 return r==0&&p; 24 } 25 if(!e&&dp[i][r][o][p]!=-1) 26 return dp[i][r][o][p]; 27 int j; 28 int mk = e?d[i]:9; 29 LL ans = 0; 30 for(j = 0; j <= mk ; j++) 31 { 32 if(p) 33 ans+=dfs(i-1,e&&j==mk,(r*10+j)%13,0,1); 34 else 35 { 36 if(o&&j==3) 37 ans+=dfs(i-1,e&&j==mk,(r*10+j)%13,0,1); 38 else if(j==1) 39 ans+=dfs(i-1,e&&j==mk,(r*10+j)%13,1,0); 40 else 41 ans+=dfs(i-1,e&&j==mk,(r*10+j)%13,0,0); 42 } 43 } 44 return e?ans:dp[i][r][o][p]=ans; 45 } 46 LL cal(LL x) 47 { 48 int g=0; 49 while(x) 50 { 51 d[g++] = x%10; 52 x/=10; 53 } 54 return dfs(g-1,1,0,0,0); 55 } 56 int main() 57 { 58 memset(dp,-1,sizeof(dp)); 59 while(cin>>n) 60 { 61 cout<<cal(n)<<endl; 62 } 63 return 0; 64 }