xorequation(DFS完全枚举)

题目

有一个含有N个未知数的方程如下：

x1^x2^...^xn= V，给定N,V，再给定正整数a1,a2,...an满足1≤ai≤9且∏^N_i=1(ai+1) ≤ 32768，请输出所有满足0≤xi≤ai的解。

思路

枚举每个xi的取值，显然，写成N个循环肯定可以，但不如递归简洁。

复杂度

递归的写法复杂度不那么明显，其实和多重循环的复杂度一样，共有∏^N_i=1(ai+1)种状态，每种状态输出结果，所以为O(N x ∏^N_i=1(ai+1))。

代码实现

 1 #include<stdio.h>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 
 6 const int maxn = 36 + 10;
 7 int N, V,a[maxn];
 8 char s[maxn];
 9 char ans[32768][maxn];
10 int ans_cnt = 0;
11 
12 void dfs(int cur,int v)
13 {
14     if (cur == N)
15     {
16         if (v == V)
17             strcpy(ans[ans_cnt++], s);   //把答案存起来
18         return;
19     }
20     for (int i = 0; i <= a[cur]; i++)
21     {
22         s[2 * cur] = i + '0';
23         if (cur != 0)  s[2 * cur - 1] = '^';
24         dfs(cur + 1, v ^ i);
25     }
26 }
27 
28 int main()
29 {
30     scanf("%d%d", &N, &V);
31     for (int i = 0; i < N; i++)
32         scanf("%d", &a[i]);
33     dfs(0, 0);
34     printf("%d
", ans_cnt);
35     for (int i = 0; i < ans_cnt; i++)
36         printf("%s=%d
", ans[i], V);
37 }