首页 > 代码库 > HDU 4669 Mutiples on a circle（DP）

HDU 4669 Mutiples on a circle（DP）

2024-07-08 23:54:17   217人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4669

题意：给出一个长度为n的数字环A和数字m。问有多少子串（连续）使得这些子串的数字拼在一起是m的倍数？

思路：首先计算A[1]和A[n]不在一起的。这个简单，只要记录f[i][j]表示到第i个数字余数为j的个数即可，然后：


接着计算a[1]和a[n]在一起的情况。我们首先预处理end[i]表示数字子串A[i,n]连在一起对m的余数。然后枚举i从[1,n-1]，那么数字设数字串[1,i]的长度为L、对m的余数为k，同时在i从1循环到i的时候f[n]将end[i]减去，那么f[n]中剩下的就是[i+1,n]这个串的所有子串[j,n]对m的余数（i+1<=j<=n）。此时枚举[i+1,n]对m的余数j：

int a[N],b[N],p[6],n,m;int f[2][205],end[N];int get(int x){    if(x>=1&&x<=9) return 1;    if(x>=10&&x<=99) return 2;    if(x>=100&&x<=999) return 3;    return 4;}int pre,cur;i64 cal1(){    pre=0,cur=1;    int i,j,k;    FOR0(i,m) f[pre][i]=0;    f[pre][a[1]]=1;    i64 ans=0;    ans+=f[pre][0];    for(i=2;i<=n;i++)    {        FOR0(j,m) f[cur][j]=0;        f[cur][a[i]]=1;        FOR0(j,m)         {            k=(j*p[b[i]]+a[i])%m;            f[cur][k]+=f[pre][j];        }        swap(pre,cur);        ans+=f[pre][0];    }    return ans;}i64 cal2(){    int i,j,k,t,temp;    i64 ans=0;    end[n]=a[n];    t=p[b[n]];    for(i=n-1;i>=1;i--)    {        end[i]=(a[i]*t+end[i+1])%m;        t=t*p[b[i]]%m;    }    t=a[1]; k=p[b[1]];    for(i=1;i<n;i++)    {        f[pre][end[i]]--;        FOR0(j,m)        {            temp=(j*k+t)%m;            if(temp==0) ans+=f[pre][j];        }        k=k*p[b[i+1]]%m;        t=(t*p[b[i+1]]+a[i+1])%m;    }    return ans;}int main(){    Rush(n)    {        RD(m);        int i;        p[0]=1;        FOR1(i,4) p[i]=p[i-1]*10%m;        FOR1(i,n) RD(a[i]),b[i]=get(a[i]),a[i]%=m;        i64 ans=cal1();        ans+=cal2();        PR(ans);    }}

 


联系
我们