题目描述

给出 个数和一个模数

问选若干个数(可以重复选择)拼在一起,并且整除 时,最短的长度。

正解

显然这 个数有用的信息只有长度 和模 意义下的值 ,那就先预处理这些东西。

考虑每次把新加进来的数放在已有的数的左边。

加入后的值是原来的值 加上新增的值

表示当前的数模 意义下的值为 ,下一个数加进来,还要乘上 的最短串。

在模 意义下至多只有 个不同的取值,那么状态其实只有 种。

暴力枚举每一种转移就行了,本质上就是跑一遍最短路,用 Dijkstra 实现。

时间复杂度

代码

#include <bits/stdc++.h>
#define N 205
#define MAX 1000005

using namespace std;

int n, p;
int f[N][N];
int d[N], len[N], pw[MAX];

struct node {
    int x, y, d;
    bool operator > (const node &t) const {
        return d > t.d;
    }
};

int main() {
    scanf("%d %d", &n, &p);
    pw[0] = 1;
    for(int i = 1; i < MAX; ++i) pw[i] = 10 * pw[i - 1] % p;
    for(int i = 1; i <= n; ++i) {
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) {
            ++len[i];
            d[i] = (d[i] * 10 + ch - '0') % p;
            ch = getchar();
        }
    }

    memset(f, 32, sizeof f);
    int ans = f[0][0];
    f[0][1] = 0;
    priority_queue<node, vector<node>, greater<node> > H;
    H.push((node){0, 1, 0});
    while(!H.empty()) {
        node cur = H.top(); H.pop();
        if(cur.d != f[cur.x][cur.y]) continue;
        for(int i = 1; i <= n; ++i) {
            node nex;
            nex.x = (cur.x + d[i] * cur.y) % p;
            nex.y = cur.y * pw[len[i]] % p;
            nex.d = cur.d + len[i];
            if(nex.x == 0) ans = min(ans, nex.d);
            if(f[nex.x][nex.y] > nex.d) {
                f[nex.x][nex.y] = nex.d;
                H.push(nex);
            }
        }
    }

    if(ans > 500000000) ans = -1;
    printf("%d\n", ans);
    return 0;
}