题解 [牛客练习赛62 D] 牛牛的呱数

牛牛的呱数

题目描述

给出 $n$ 个数和一个模数 $p$ 。

问选若干个数（可以重复选择）拼在一起，并且整除 $p$ 时，最短的长度。

正解

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

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

加入后的值是原来的值 $x_i$ 加上新增的值 $x_j \times 10^{len_i}$ 。

设 $f_{x,10^{len}}$ 表示当前的数模 $p$ 意义下的值为 $x$ ，下一个数加进来，还要乘上 $10^{len}$ 的最短串。

$10^{len_i}$ 在模 $p$ 意义下至多只有 $p$ 个不同的取值，那么状态其实只有 $O(p^2)$ 种。

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

时间复杂度 $O(p^3 \log n)$ 。

代码

#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;
}