思路:主要就是一个动态方程dp[now][(j*Exp[len[num[i]]]+num[i])%k]+=dp[pre][j];我用的是滚动数组。其实也就是dp[i][(j*Exp[len[num[i]]]+num[i])%k]+=dp[i-1][j];
唯一需要注意的就是存在长度长于n的串,要减掉。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define Maxn 100010
using namespace std;
int len[Maxn],Exp[Maxn*],n,k,num[Maxn];
int dp[][];
void init()
{
int i;
for(i=;i<;i++) len[i]=;
for(i=;i<;i++) len[i]=;
for(i=;i<;i++) len[i]=;
for(i=;i<=;i++) len[i]=;
}
int main()
{
int i,j;
init();
//freopen("ans.txt","r",stdin);
//freopen("ABCd.txt","w",stdout);
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(dp,,sizeof(dp));
Exp[]=;
for(i=;i<=*n;i++)
Exp[i]=(Exp[i-]*)%k;
for(i=;i<=n;i++)
scanf("%d",num+i);
int sum=,s=;
int ans=;
int pre=,now=;
for(i=;i<=n;i++)
{
now=!now;
pre=!pre;
memset(dp[now],,sizeof(dp[now]));
for(j=;j<k;j++)
dp[now][(j*Exp[len[num[i]]]+num[i])%k]+=dp[pre][j];
dp[now][num[i]%k]++;
sum=(sum*Exp[len[num[i]]]+num[i])%k;
s+=len[num[i]];
ans+=dp[now][];
}
for(i=;i<n;i++)
{
now=!now;
pre=!pre;
memset(dp[now],,sizeof(dp[now]));
for(j=;j<k;j++)
dp[now][(j*Exp[len[num[i]]]+num[i])%k]+=dp[pre][j];
sum=(sum*Exp[len[num[i]]]+num[i])%k;
dp[now][sum]--;
sum=((sum-num[i]*Exp[s])%k+k)%k;
ans+=dp[now][];
}
printf("%d\n",ans);
}
return ;
}