/*题意：给出一个环，每个点是一个数字，取一个子串，使得拼接起来的数字是K的倍数。 由于K不大，暂且不考虑环的话，那么dp[i][j]表示以i结尾的，模K为j的有多少个子串。 那么sigma (dp[i][0])便是不考虑环的答案。 考虑环的话，不知道别人怎么写的，我感觉我的写法不是很复杂。 环和情况1 和n肯定是必选的，那么便是一个前缀为后缀，一个后缀为前缀拼接而成。 所以枚举某个前缀，求出前缀模K，那么枚举后缀模K的值，通过之前已经预处理过的dp值，便可以求出有多少个后缀满足为K的倍数。 但是这样可能后缀和前缀重叠了，所以我们枚举前缀的同时，依次记录后缀不同模值的个数。 随着前缀的增长，这些后缀都是和前缀重叠的。 */
Mutiples on a circle
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 1424 Accepted Submission(s): 362
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.
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.
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
Source
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long int LL;
const int maxn=50005;
int dp[2][205];
int fac[maxn*4],l[maxn];
int cnt[205];
int pref[maxn],suff[maxn];
int a[maxn],N,K;
int WE(int x)
{
if(x==0) return 1;
int ret=0;
while(x) { x/=10; ret++; }
return ret;
}
int main()
{
while(scanf("%d%d",&N,&K)!=EOF)
{
/*******init***********/
memset(dp,0,sizeof(dp));
memset(cnt,0,sizeof(cnt));
fac[0]=1;
for(int i=1;i<=(N<<2);i++)
fac[i]=fac[i-1]*10%K;
/**********************/
for(int i=1;i<=N;i++)
{
scanf("%d",a+i); l[i]=WE(a[i]);
}
dp[1][a[1]%K]=1;
LL ans=dp[1][0];
for(int i=2;i<=N;i++)
{
for(int j=0;j<K;j++)
dp[i&1][j]=0;
dp[i&1][a[i]%K]++;
for(int j=0;j<K;j++)
{
int r=(j*fac[l[i]]+a[i])%K;
dp[i&1][r]+=dp[(i-1)&1][j];
}
ans+=dp[i&1][0];
}
/************环型DP**************/
pref[0]=0;
for(int i=1;i<=N;i++)
pref[i]=(pref[i-1]*fac[l[i]]+a[i])%K;
int len=0;
suff[N+1]=0;
for(int i=N;i>=1;i--)
{
suff[i]=(a[i]*fac[len]+suff[i+1])%K;
len+=l[i];
}
len=0;
for(int i=1;i<=N;i++)
{
cnt[suff[i]]++;
len+=l[i];
for(int j=0;j<K;j++)
{
if((j*fac[len]+pref[i])%K) continue;
ans+=dp[N&1][j]-cnt[j];
}
}
printf("%I64d\n",ans);
}
return 0;
}