首页 > ACM题库 > HDU-杭电 > hdu 2465 Binary Integer待解决[解题报告]C++
2014
01-26

hdu 2465 Binary Integer待解决[解题报告]C++

Binary Integer

问题描述 :

An antique machine with C(n , 3) switches capable of processing integers in the range 0…2N-1 has just been discovered. Each switch is associated to a distinct integer in 0…2N-1 with exactly three ones in its binary representation. By setting switches associated with number X0,X1…XM-1 to on, any integer Y passing through the machine will render a result of Y�X0�X1�…�XM-1(here “�” stands for bitwise-XOR).
We are interested in the number of configurations capable of transforming integer S into T with exactly K switches set to on. Could you write a program to help us?

输入:

There are multiple test cases in the input file.
Each test case starts with two integers, N and K (1 ≤ N ≤ 40 , 0 ≤ K ≤ min{20 , C(N,3)} ), followed by two binary integers, S and T, each containing exactly N bits.
Two successive test cases are separated by a blank line. A case with N = 0 and K = 0 indicates the end of the input file, and should not be processed by your program.

输出:

There are multiple test cases in the input file.
Each test case starts with two integers, N and K (1 ≤ N ≤ 40 , 0 ≤ K ≤ min{20 , C(N,3)} ), followed by two binary integers, S and T, each containing exactly N bits.
Two successive test cases are separated by a blank line. A case with N = 0 and K = 0 indicates the end of the input file, and should not be processed by your program.

样例输入:

4 3
1101
1001
3 1
101
010
5 3
11010
10111
0 0

样例输出:

Case #1: 1
Case #2: 1
Case #3: 6


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?