hdu 4669 动态规划

时间：2021-11-23 14:46:37

思路：主要就是一个动态方程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 ;

}

相关文章