2010年02月08日星期一.sgu159 && pku2205 dfs
/*
* SOUR:sgu159 && pku2205
* ALGO:dfs... ...
* DATE: 2010年 02月 07日 星期日 23:16:59 CST
* COMM:4 dfs
* 如果P[n]是符合條件的那么必須有P[n-1]是符合條件的。所以可以從0位開始按位在數(shù)的前段
* 添加數(shù)，而在搜索的過(guò)程中由于P[n-1]是符合條件的所以只需要判斷最高位是否符合條件即可。
* 不好想啊，我想到了這個(gè)符合條件，但是卻還是沒想到還能這么搜
* */
本題我的思路就是按位擴(kuò)展+高精，以下精妙算法完全來(lái)自
http://162.105.81.212/JudgeOnline/showmessage?message_id=93126
1
2 const int N = 2048;
3 int n,bas,top;
4 int g[N][N];
5 int a[N];
6
7 void dfs(int idx,int sum)
8 {
9 if (idx == n) {
10 if (a[idx-1] || n == 1) {
11 for (int i = 0;i < n;i++) {
12 g[top][i] = a[i];
13 }
14 top++;
15 }
16 return ;
17 }
18 for (int i = 0;i < bas;i++) {
19 a[idx] = i;
20 int tmp = 0;
21 for (int j = 0;j <= idx;j++) {
22 tmp += a[j] * a[idx-j];
23 }
24 if ((sum + tmp) % bas == i) {
25 dfs(idx + 1,(sum + tmp) / bas);
26 }
27 }
28 }
29
30 int main()
31 {
32 int i,j,k;
33 scanf("%d%d",&bas,&n);
34 dfs(0,0);
35 printf("%d\n",top);
36 for (i = 0;i < top;i++) {
37 for (j = n - 1;j >= 0;j--) {
38 if (g[i][j] >= 10) {
39 printf("%c",g[i][j] - 10 + 'A');
40 }else {
41 printf("%d",g[i][j]);
42 }
43 }
44 printf("\n");
45 }
46 return 0;
47 }
48