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 a i(1 ≤ a i ≤ 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#include #include #include 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; }