更新时间:2023-02-19 22:53:32
好问题.我使用 BFS 通过中间相遇和其他一些修剪来解决这个问题.现在我的代码可以在合理的时间内解决 n9.
Nice question. I use BFS to solve this question with meet-in-the-middle and some other prunings. Now my code can solve n<109 in a reasonable time.
#include <cstdio>
#include <cstring>
class BIT {
private: int x[40000000];
public:
void clear() {memset(x, 0, sizeof(x));}
void setz(int p, int z) {x[p>>5]=z?(x[p>>5]|(1<<(p&31))):(x[p>>5]&~(1<<(p&31)));}
int bit(int p) {return x[p>>5]>>(p&31)&1;}
} bp, bq;
class UNIT {
private: int x[3];
public: int len, sum;
void setz(int z) {x[len>>5]=z?(x[len>>5]|(1<<(len&31))):(x[len>>5]&~(1<<(len&31)));}
int bit(int p) {return x[p>>5]>>(p&31)&1;}
} u;
class MYQUEUE {
private: UNIT x[5000000]; int h, t;
public:
void clear() {h = t = 0;}
bool empty() {return h == t;}
UNIT front() {return x[h];}
void pop() {h = (h + 1) % 5000000;}
void push(UNIT tp) {x[t] = tp; t = (t + 1) % 5000000;}
} p, q;
int n, md[100];
void bfs()
{
for (int i = 0, tp = 1; i < 200; i++) tp = 10LL * (md[i] = tp) % n;
u.len = -1; u.sum = 0; q.clear(); q.push(u); bq.clear();
while (1)
{
u = q.front(); if (u.len >= 40) break; q.pop();
u.len++; u.setz(0); q.push(u);
u.setz(1); u.sum = (u.sum + md[u.len]) % n;
if (!bq.bit(u.sum)) {bq.setz(u.sum, 1); q.push(u);}
if (!u.sum) {
for (int k = u.len; k >= 0; k--) printf("%d", u.bit(k));
puts(""); return;
}
}
u.len = 40; u.sum = 0; p.clear(); p.push(u); bp.clear();
while (1)
{
u = p.front(); p.pop();
u.len++; u.setz(0); p.push(u);
u.setz(1); u.sum = (u.sum + md[u.len]) % n;
if (!bp.bit(u.sum)) {bp.setz(u.sum, 1); p.push(u);}
int bf = (n - u.sum) % n;
if (bq.bit(bf)) {
for (int k = u.len; k > 40; k--) printf("%d", u.bit(k));
while (!q.empty())
{
u = q.front(); if (u.sum == bf) break; q.pop();
}
for (int k = 40; k >= 0; k--) printf("%d", u.bit(k));
puts(""); return;
}
}
}
int main(void)
{
// 0 < n < 10^9
while (~scanf("%d", &n)) bfs();
return 0;
}