问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1426思路:
典型的BFS，每次扩展都在末尾加上0或者1，例如从1开始，1->10、1->11，10->100，10->101...
根据这点，就可以写出AC的代码，不过这样所需内存会比较高昂，因为保存的每个状态都是long long，并且状态数目非常多
参考网上代码，发现这里可以应用鸽巢原理
对于m取模，其结果只有0, 1, ..., m-1这几种可能，因此很可能出现重复
另外，如果扩展前remainder是k, 那么扩展之后的remainder可以通过((k*10)+0/1)%num计算得到
如何记录结果也是比较tricky的，这里在每个状态中只保留一位以及指向扩展前状态的指针，输出的时候只要递归即可
代码:
1 struct EACH {
2 int remainder;
3 int digit;
4 struct EACH *pre;
5 }queue[QUEUE_MAX];
6 int hash[REMAINDER_MAX];
7 int head, tail;
8 int num;
9
10 void
11 output(struct EACH *end)
12 {
13 if(end==NULL)
14 return;
15 output(end->pre);
16 printf("%d", end->digit);
17 }
18
19 void
20 bfs()
21 {
22 int cur_rem, next_rem;
23 queue[tail].remainder = 1%num;
24 queue[tail].digit = 1;
25 queue[tail].pre = NULL;
26 hash[queue[tail].remainder] = 1;
27 while(head <= tail) {
28 ++head;
29 cur_rem = queue[head].remainder;
30 if(cur_rem == 0) {
31 output(queue+head);
32 printf("\n");
33 return;
34 }
35 next_rem = (cur_rem*10+0)%num;
36 if(!hash[next_rem]) {
37 ++tail;
38 queue[tail].remainder = next_rem;
39 queue[tail].digit = 0;
40 queue[tail].pre = queue+head;
41 hash[next_rem] = 1;
42 }
43 next_rem = (cur_rem*10+1)%num;
44 if(!hash[next_rem]) {
45 ++tail;
46 queue[tail].remainder = next_rem;
47 queue[tail].digit = 1;
48 queue[tail].pre = queue+head;
49 hash[next_rem] = 1;
50 }
51 }
52 }