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

https://ac.nowcoder.com/acm/contest/5205/D

### 代码

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

Java

3 收藏 评论