题目


给定n个字符串，可以按任意顺序拼接，每个串可以使用无限次，使得拼接的的字符串长度最短且被P整除。


设在意义下 ,和拼接成的最小花费，建立有向图，跑最短路即可。
最后只要看有没有到的最短路径即可。

#include<bits/stdc++.h>
#include<sys/socket.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
int O(){putchar('\n');return 0;}template<typename T,typename... Ty>
int O(const T& a,const Ty&... b){cout<<a<<' ';return O(b...);}
void I(){}template<typename T,typename... Ty>void I(T& a,Ty&... b){cin>>a;I(b...);}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
int n,p;
char s[N];
int dp[303][303];
int main(){
    I(n,p);
    for(int i=0;i<p;i++)
    for(int j=0;j<p;j++)
    dp[i][j]=N*2;
    for(int i=0;i<n;i++){
        sc("%s",s+1);
        int len=strlen(s+1);
        int pw=1,val=0;
        for(int j=1;j<=len;j++){
            pw=pw*10;
            val=val*10+(s[j]-'0');
            pw%=p,val%=p;
        }
        for(int j=0;j<p;j++){
            dp[j][(j*pw%p+val)%p]=min(dp[j][(j*pw%p+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]);
            }
        }
    }
    O(dp[0][0]!=2*N?dp[0][0]:-1);
}