- hdu3652 B-number http://acm.hdu.edu.cn/showproblem.php?pid=3652
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 15;
- int dp[maxn][maxn][maxn][maxn];
- // dp[i][j][state][r] i 表示位数, j 表示开头, state 是 0 或 1 表示是否已经出现了 "13" 这个子串
- int base[maxn];
- void init() {
- base[0] = 1;
- for (int i = 1; i <= 10; i++) {
- base[i] = base[i-1]*10;
- }
- for (int i = 0; i <= 9; i++) {
- dp[1][i][0][i] = 1;
- }
- for (int i = 2; i <= 10; i++) {
- for (int j = 0; j <= 9; j++) {
- for (int x = 0; x <= 9; x++) {
- int t = base[i-1]*j % 13;
- for (int r = 0; r <= 12; r++) {
- dp[i][j][1][(r+t)%13] += dp[i-1][x][1][r];
- if (j == 1 && x == 3) { // 出现了 13 这个子串
- dp[i][j][1][(r+t)%13] += dp[i-1][x][0][r];
- }
- else {
- dp[i][j][0][(r+t)%13] += dp[i-1][x][0][r];
- }
- }
- }
- }
- }
- }
- int calc(int n) {
- n++;
- int digit[15] = {0};
- int lenstr = 0;
- while (n/10> 0) {
- digit[++lenstr] = n%10;
- n /= 10;
- }
- digit[++lenstr] = n%10;
- int ans = 0;
- int mod = 0;
- bool flag = false;
- for (int i = lenstr; i>= 1; i--) {
- for (int j = 0; j <= digit[i]-1; j++) {
- ans += dp[i][j][1][(13-mod)%13];
- if (flag || j == 3 && digit[i+1] == 1) {
- ans += dp[i][j][0][(13-mod)%13];
- }
- }
- if (digit[i] == 3 && digit[i+1] == 1) {
- flag = true;
- }
- mod = (mod+digit[i]*base[i-1])%13;
- }
- return ans;
- }
- int main() {
- int n;
- init();
- while (~scanf("%d",&n)) {
- printf("%d\n",calc(n));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3264403.html