首页 > 代码库 > HDU - 4669 Mutiples on a circle
HDU - 4669 Mutiples on a circle
Problem Description
Tom has a necklace with n jewels. There is a number on each jewel. Now Tom wants to select a wonderful chain from the necklace. A chain will be regarded wonderful if the wonderful value of the chain is a multiple of a key number K. Tom gets the wonderful value using this way:He writes down the number on the chain in clockwise order and concatenates them together. In this way, he gets a decimal number which is defined as the wonderful value.
For example, consider a necklace with 5 jewels and corresponding numbers on the jewels are 9 6 4 2 8 (9 and 8 are in neighborhood). Assume we take K=7, then we can find that only five chains can be multiples of K. They are 42, 28, 896, 42896 and 89642.
Now Tom wants to know that how many ways he can follow to select a wonderful chain from his necklace.
For example, consider a necklace with 5 jewels and corresponding numbers on the jewels are 9 6 4 2 8 (9 and 8 are in neighborhood). Assume we take K=7, then we can find that only five chains can be multiples of K. They are 42, 28, 896, 42896 and 89642.
Now Tom wants to know that how many ways he can follow to select a wonderful chain from his necklace.
Input
The input contains several test cases, terminated by EOF.
Each case begins with two integers n( 1 ≤ n ≤ 50000), K(1 ≤ K ≤ 200),the length of the necklace and the key number.
The second line consists of n integer numbers, the i-th number ai(1 ≤ ai ≤ 1000) indicating the number on the ith jewel. It’s given in clockwise order.
Each case begins with two integers n( 1 ≤ n ≤ 50000), K(1 ≤ K ≤ 200),the length of the necklace and the key number.
The second line consists of n integer numbers, the i-th number ai(1 ≤ ai ≤ 1000) indicating the number on the ith jewel. It’s given in clockwise order.
Output
For each test case, print a number indicating how many ways Tom can follow to select a wonderful chain.
Sample Input
5 7 9 6 4 2 8
Sample Output
5
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> typedef long long ll; using namespace std; const int maxn = 50010; const int mod = 210; int n, k; int dp[maxn][305], num[maxn<<1]; int len[maxn<<1], doMod[maxn<<2]; int digit(int a) { int len = 0; while (a) { a /= 10; len++; } return len; } void getMod(int k, int n) { doMod[0] = 1; for (int i = 1; i <= n<<2; i++) doMod[i] = (doMod[i-1] * 10) % k; } int main() { int n, k; while (scanf("%d%d", &n, &k) != EOF) { for (int i = 1; i <= n; i++) { scanf("%d", &num[i]); num[i+n] = num[i]; } getMod(k, n); for (int i = 0; i <= n; i++) for (int j = 0; j <= k; j++) dp[i][j] = 0; int r; for (int i = 1; i <= n; i++) { len[i+n] = len[i] = digit(num[i]); r = num[i] = num[i+n] = num[i] % k; dp[i][r]++; } r = num[1]; int sunlen = 0; for (int i = n; i > 1; i--) { sunlen += len[i+1]; r = (num[i] * doMod[sunlen] + r) % k; dp[1][r]++; } sunlen = 0; for (int i = 1; i <= n; i++) sunlen += len[i]; int last = r; ll ans = dp[1][0]; for (int i = 2; i <= n; i++) { for (int j = 0; j < k; j++) { r = (j * doMod[len[i]] + num[i]) % k; dp[i][r] += dp[i-1][j]; } last = (last * doMod[len[i]] + num[i]) % k; dp[i][last]--; last = (last - (num[i] * doMod[sunlen]) % k + k) % k; ans += dp[i][0]; } printf("%lld\n", ans); } return 0; }
HDU - 4669 Mutiples on a circle
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。