C++14(g++5.4) 解法, 执行用时: 22ms, 内存消耗: 1492K, 提交时间: 2020-04-26 18:43:59

#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int n, p;
char s[1000010];
int dp[210][210];
int main(){
	scanf("%d%d", &n, &p);
	memset(dp, 0x3f, sizeof(dp));
	for(int i = 1; i <= n; i++){
		scanf("%s", s+1);
		int len = strlen(s+1), val = 0, tmp = 1;
		for(int j = 1; j <= len; j++){
			val = (val*10+s[j]-'0')%p;
			tmp = (10*tmp)%p;
		}
		for(int j = 0; j < p; j++)
			dp[j][(j*tmp+val)%p] = min(dp[j][(j*tmp+val)%p], len);
	}
	for(int k = 0; k < p; k++)
		for(int i = 0; i < p; i++)
			for(int j = 0; j < p; j++)
				dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
	
	if(dp[0][0]==inf) printf("-1");
	else printf("%d", dp[0][0]);		
}

C++11(clang++ 3.9) 解法, 执行用时: 51ms, 内存消耗: 1628K, 提交时间: 2020-04-24 19:58:20

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

int n,p,len=0;
char s[1000010];
long long dis[210][210],t[210][210];

void Pow(){
	for(int k=0;k<p;k++)
		for(int i=0;i<p;i++)
			for(int j=0;j<p;j++)
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}

int main(){
	scanf("%d %d",&n,&p);
	for(int i=0;i<p;i++) for(int j=0;j<p;j++) dis[i][j]=1e18;
	for(int i=1;i<=n;i++){
		scanf("%s",s+1);len=strlen(s+1);
		long long t=1,tot=0;
		for(int j=len;j>=1;j--) (tot+=(s[j]-'0')*t%p)%=p,(t*=10)%=p;
		for(int j=0;j<p;j++) dis[j][(j*t+tot)%p]=min(dis[j][(j*t+tot)%p],1ll*len);
	}
	Pow();
	if(dis[0][0]==1e18) printf("-1");
	else printf("%lld\n",dis[0][0]);
}