首页 > 代码库 > 【dp】B-number
【dp】B-number
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3652
题解：先预处理([0,0][1,1],[2,2]....[0,9],[10, 19],[20,29]......[900000000, 1000000000] 区域中 有子串13 （用1表示）余数为0,1,2.。。12的个数。以及 无子串13（用0表示）余数为0,1,2,3.。。12 的个数。
四维数组dp【一共多少位数】【最高位的数】【是否含有子串13】【余数】 例如 dp[4][1][1][0] 表示 （【1000,2000)）（四位， 最高位数为1）， 子串中含有13， 且余数为0的个数。
dp[a][b][c][d]
当求a = 2时必须 a=1的元素都已知，例如 求[20, 29）中含有13， 余数为3的个数。 即 dp【2】【2】【0】【3】 ，由于 [20, 29）可看做 20 + x（0—9）。而20 % 13 = 7， 只需找余数为9. 则 sum（ dp【1】【j】【0】【9】）（j= 0,1,2.。。。9）。
需注意的是 当b = 1 时， 由于在低一位上有3， 所以这种情况要分开求。
/***Good Luck***/#define _CRT_SECURE_NO_WARNINGS#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <algorithm>#include <stack>#include <map>#include <queue>#include <vector>#include <set>#include <functional>#include <cmath>#include <numeric>#define Zero(a) memset(a, 0, sizeof(a))#define Neg(a) memset(a, -1, sizeof(a))#define All(a) a.begin(), a.end()#define PB push_back#define inf 0x3f3f3f3f#define inf2 0x7fffffffffffffff#define ll long longusing namespace std;//#pragma comment(linker, "/STACK:102400000,102400000")void get_val(int &a) { int value = http://www.mamicode.com/0, s = 1; char c; while ((c = getchar()) == ‘ ‘ || c == ‘\n‘); if (c == ‘-‘) s = -s; else value = http://www.mamicode.com/c - 48; while ((c = getchar()) >= ‘0‘ && c <= ‘9‘) value = value * 10 + c - 48; a = s * value;}const int maxn = 20;int dp[maxn][maxn][2][maxn];int n;void change1(int i, int j, int m) { for (int k = 0; k <= 1; ++k) for (int kk = 0; kk <= 12; ++kk) { dp[i][j][1][(kk - m + 13) % 13] += dp[i - 1][3][k][kk]; }}void change2(int i, int m,int j, int jj) { for (int k = 0; k <= 1; ++k) for (int kk = 0; kk <= 12; ++kk) { dp[i][j][k][(kk + m) % 13] += dp[i - 1][jj][k][kk]; }}void init() { Zero(dp); int w = 10, m; dp[0][0][0][0] = 1; for (int i = 0; i <= 10; ++i) dp[1][i][0][i] = 1; for (int i = 2; i <= 9; ++i) { for (int j = 0; j <= 9; ++j) { for (int jj = 0; jj <= 9; ++jj) { m = (j * w) % 13; if (j == 1 && jj == 3) { m = (jj * w / 10 )% 13; change1(i, j, m); } else change2(i, m, j, jj); } } w *= 10; }}int cal(int n1) { if (n1 == 1000000000) return 5993844; char ch[15]; Zero(ch); int i = 1; int flag = -1; int ret = 0; while (n1) { ch[i++] = n1 % 10 + ‘0‘; n1 /= 10; } for (int j = i - 1; j > 0; --j) { if (ch[j] == ‘1‘ && ch[j - 1] == ‘3‘) { flag = j - 1; break; } } n1 = n / 10; int w = 1; for (int j = 1; j <= i; ++j) { for (int jj = 0; jj < ch[j] - ‘0‘; ++jj) { int t = (n1 * 10 ) * w % 13; if (jj == 3 && ch[j + 1] == ‘1‘) { t = (n1 / 10 * 100) * w % 13; ret += dp[j][0][0][(13 - t) % 13] + dp[j ][0][1][(13 - t) % 13]; continue; } if (flag > j) { ret += dp[j][jj][0][(13 - t) % 13] + dp[j][jj][1][(13 - t) % 13]; } else { ret += dp[j][jj][1][(13 - t) % 13]; } } w *= 10; n1 /= 10; } if (n % 13 == 0 && flag != -1) ret++; return ret;}int main() { //freopen("data.out", "w", stdout); //freopen("data.in", "r", stdin); //cin.sync_with_stdio(false); init(); while (cin >> n) { cout << cal(n) << endl; } return 0;}
【dp】B-number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。