2015
09-17

Mutiples on a circle

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.

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.

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.

5 7
9 6 4 2 8

5

dp递推，通过一个状态往后加数不断递推出所有状态，并且不断取余

#include <cstdio>
#include <cstring>
#include <cmath>
#define M 50005
#define K 205
int mod[M], sum[M], dp[M][K], p[200005];
int n, k;
void POW()
{
p[0] = 1;
for(int i = 1; i <= 4*n; ++i) p[i] = (p[i-1]*10)%k;
}
int main ()
{
//freopen("in.txt","r",stdin);
//freopen("ou.txt","w",stdout);
while(scanf("%d%d",&n, &k)!=EOF)
{
POW();
for(int i=0; i<=n; ++i)
for(int j=0; j<=k; ++j) dp[i][j]=0;
for(int i = 1; i <= n; ++i)
{
scanf("%d",&sum[i]);
mod[i] =1+ log10(sum[i]*1.0);
}
int cnt=mod[1],s=sum[1]%k;
++dp[1][s];
for(int i = 2; i <= n; ++i)
{
s = (sum[n-i+2]*p[cnt]+s)%k;
++dp[1][s];
cnt+=mod[n-i+2];
}
int ans = dp[1][0];
for(int i = 2; i <= n; ++i)
{
++dp[i][sum[i]%k];
for(int j = 0; j < k; ++j)
if(dp[i-1][j])
{
int t = (j*p[mod[i]]+sum[i])%k;
dp[i][t] += dp[i-1][j];
}
s=(s*p[mod[i]]+sum[i])%k;
dp[i][s]-=1;
ans+=dp[i][0];
s=(s-(sum[i]*p[cnt])%k+k)%k;
}
printf("%d\n",ans);
}
return 0;
}