牛客练习赛62 D.牛牛的呱数

大致题意:给定n个数字和p，选择一些将数字拼接成一个新的数字ans(可以重复选择)，ans可被p整除.(n个数字长度总和<=1e6,p<=200 )
分析：参考jls代码..%%%九峰大佬..

• 考虑p的范围不大，可以写动态规划并且对于每一个数而言模p下的贡献方案最多只有p次,那么我们只需要外层循环更新p次即可.
  ,dp[i]表示选择一些数字拼接后模p下余数为i的最小长度.那么我们枚举n个数进行更新dp[j]数组,对于当前第i个数而言更新dp[j]， 表示第i个数字的长度,我们简化= ,x表示第i个数字模p下的答案，我们考虑将数字拼接到右边，那么新的数字模p下就是
  ,那么我们可列出转移方程: ,now和pre我们可以用滚动数组维护.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e6+10;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,p;
int dp[2][205];
int d[maxn],len[maxn],pw[maxn];



int main()
{
    scanf("%d%d",&n,&p);
    pw[0]=1;
    for( int i=1;i<maxn;i++ ) pw[i]=10*pw[i-1]%p;
    getchar();
    for( int i=1;i<=n;i++ )
    {
        char s=getchar();
        int cnt=0;
        for( ;isdigit(s);d[i]=(d[i]*10+s-48)%p,cnt++,s=getchar());
        len[i]=cnt;
    } 
    int now=1;
    for( int i=1;i<p;i++ ) dp[0][i]=inf;
    for( int i=1;i<=p;i++ )
    {
        for( int j=0;j<p;j++ ) dp[now][j]=dp[now^1][j];
        if( dp[now][0]==0 ) dp[now][0]=inf;
        for( int j=1;j<=n;j++ )
        {
            for( int k=0;k<p;k++ )
            {
                dp[now][ (k*pw[len[j]]+d[j])%p ]=min( dp[now][ (k*pw[len[j]]+d[j])%p ],dp[now^1][k]+len[j] );
            }
        }
    //    for(int j=0;j<p;j++)cout<<dp[now][j]<<' ';cout<<endl;
        now^=1; 
    }
    if( dp[now^1][0]>=inf ) printf("-1");
    else printf("%d\n",dp[now^1][0]);
    return 0;
}