题目的意思是给你一些数字a[i](首位相连),现在要你选出一些连续的数字连续的每一位单独地作为一个数位。现在问你有多少种选择的方式使得选出的数字为k的一个倍数。
其实题目是很简单的。由于k不大(200),总共的数字个数为50000,所以我们对于当前走到的每一个数字最多的状态数目也只有50000*200个。
同时由于是循环的,我们可以使长度增倍,这样就可以保证序列是循环的了。
不过注意,增倍后空间是开不下的,所以需要使用循环的滚动数组。
同时注意递推的细节,还有有的a[i]不止一位数,不能直接取模。
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 50050
typedef long long ll;
using namespace std;int a[*maxn],f[*maxn],n,m,k,tep,cur,w[*maxn];
int s[maxn][];
ll ans;void init_(int x)
{
for (int i=; i<k; i++) s[x][i]=;
}int count(int x)
{
if (x<) return ;
if (x<) return ;
if (x<) return ;
return ;
}int get(int x)
{
if (x==) return ;
if (x==) return %k;
if (x==) return %k;
return %k;
}int power(int x,int y)
{
int tot=;
while (y)
{
if (y&) tot=(tot*x)%k;
y>>=;
x=(x*x)%k;
}
return tot;
}int main()
{
while (scanf("%d%d",&n,&k)!=EOF)
{
ans=;
w[]=,f[]=;
for (int i=; i<=n; i++)
{
scanf("%d",&a[i]);
a[i+n]=a[i];
w[i]=count(a[i]);
w[i+n]=count(a[i+n]);
}
for (int i=; i<=*n; i++) f[i]=(f[i-]*get(w[i])+a[i])%k;
for (int i=; i<=*n; i++) w[i]+=w[i-];
for (int i=; i<=n; i++)
{
init_(i);
s[i][a[i]%k]++;
for (int j=; j<k; j++) s[i][(get(w[i]-w[i-])*j+a[i])%k]+=s[i-][j];
}
for (int i=n+; i<=*n; i++)
{
int qq=i-n-;
if (qq==) qq=n;
init_(i-n);
s[i-n][a[i]%k]++;
for (int j=; j<k; j++) s[i-n][(get(w[i]-w[i-])*j+a[i])%k]+=s[qq][j];
cur=(f[i-n-]*power(,w[i]-w[i-n-]))%k;
cur=((f[i]-cur)%k+k)%k;
s[i-n][cur]--;
ans+=s[i-n][];
}
printf("%I64d\n",ans);
}
return ;
}