学步园

#include<stdio.h>
#include<string.h>
#define maxn 50005
#define maxm 205
#define INF 0xfffffff
int number[maxn],digits[maxn];
int count[maxn][maxm],e[3*maxn];
int n,mod;
void init()
{
    memset(count,0,sizeof(int)*n*maxm);//这里是maxm,如果直接把所有的都置0，会tle
//    memset(count,0,sizeof(count));//这里会tle
    for(int i=1;i<=3*n;i++)
    {
        e[i]=(e[i-1]*10)%mod;
    }
}
inline int getdigits(int x)
{
    if(x==0) return 1;
    int ret=0;
    while(x)
    {
        ret++;
        x/=10;
    }
    return ret;
}
int main()
{
    e[0]=1;
    while(scanf("%d%d",&n,&mod)!=EOF)
    {
        init();
        for(int i=0;i<n;i++)
        {
            scanf("%d",&number[i]);
            digits[i]=getdigits(number[i]);
        }
        number[n]=number[0];
        digits[n]=digits[0];
        //count[i][s]表示以i结尾，余数为s的子串数
        //先计算出count[0][s]
        int s=0,ans=0,l=0;
        for(int i=n;i;i--)
        {
            s=(s+e[l]*number[i])%mod;//从后向前一个一个增加
            //余数是number[i]*前面数的长度加上原余数
            l+=digits[i];
            count[0][s]++;
        }
        ans+=count[0][0];//s是从1到0的子串的余数
        for(int i=1;i<n;i++)
        {
            for(int r=0;r<mod;r++)
            {
                count[i][(r*e[digits[i]]+number[i])%mod]+=count[i-1][r];//从数的后面添加数
            }
            s=(s*e[digits[i]]+number[i])%mod;
            //s最开始是从1-2-3-。。。-0 这以0结尾的子串取模的余数，然后在求以1结尾的余数
            //count[i-1][r]表示的是前一个数字所有的子串，
            //当然也包括从i-(i+1)-(i+1)-...-(n-1)-0-1-(i-1)这个子串，
            //不过这个以(i-1)结尾的子串在尾部增加i的时候是不行的，因为已经在前面出现了i，
            //所以得把这种情况减掉。
            count[i][s]--;
            //以number[i]单独为一个串
            count[i][number[i]%mod]++;
            //最低位插入i之后，更改s的值，即减掉最高位的i
            s=((s-number[i]*e[l])%mod+mod)%mod;
            ans+=count[i][0];//l的长度始终为总长度
        }
        printf("%d\n",ans);
    }
    return 0;
}