B-number
Problem Description
A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string "13" and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.
Input
Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).
Output
Print each answer in a single line.
Sample Input
13
100
200
1000
Sample Output
1
1
2
2
Author
wqb0039
Source
2010 Asia Regional Chengdu Site —— Online Contest
题目类型：数位DP
算法分析：dp[i][j][k]表示满足状态为k，且模上13后值为j的i位数个数，类似于HDU3555，只不过是在递归边界上还要额外满足j == 0，在每次向低位搜索时都要计算模值：mod = (mod * 10 + i) % 13
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
/************************************************* Author :supermaker Created Time :2015/12/4 23:03:38 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; LL dp[166][16][3], bit[166]; LL SS (int pos, int mod, int st, bool flag) { if (pos == 0) return (st == 2 && mod == 0); if (flag && dp[pos][mod][st] != -1) return dp[pos][mod][st]; LL res = 0; int x = flag ? 9 : bit[pos]; for (int i = 0; i <= x; i++) { int tt = (mod * 10 + i) % 13; if ((st == 2) || (st == 1 && i == 3)) res += SS (pos - 1, tt, 2, flag || i < x); else if (i == 1) res += SS (pos - 1, tt, 1, flag || i < x); else res += SS (pos - 1, tt, 0, flag || i < x); } return flag ? dp[pos][mod][st] = res : res; } LL Calc (LL val) { memset (dp, -1, sizeof (dp)); int len = 0; while (val) { bit[++len] = val % 10; val /= 10; } return SS (len, 0, 0, 0); } int main() { //CFF; //CPPFF; LL n; while (scanf ("%I64d", &n) != EOF) { printf ("%I64d\n", Calc (n)); } return 0; } |
- « 上一篇：hdu2639
- hdu4389：下一篇 »