首页 > ACM题库 > HDU-杭电 > hdu 4073 Lights待解决[解题报告]C++
2015
04-16

hdu 4073 Lights待解决[解题报告]C++

Lights

问题描述 :

John has n light bulbs and a switchboard with n switches; each bulb can be either on or off, and pressing the i-th switch changes the state of bulb i from on to off, and viceversa. He is using them to play a game he has made up. In each move, John selects a (possibly empty) set of switches and presses them, thus inverting the states of the corresponding bulbs. After exactly m moves, John would like to have the first v bulbs on and the rest off; otherwise he loses the game. There is only one restriction: he is not allowed to press the same set of switches in two different moves.
This is quite an easy game, as there are lots of ways of winning. This has encouraged him to keep playing different winning games, and now he is intent on trying them all. Help him count how many ways of winning there are. Two games are considered the same if, after a reordering of the moves in one of them, at every step the same set of switches is pressed in both of them.
For example, if n = 4, m = 3, and v = 2, one possible winning game is obtained by pressing switches 1, 2 and 4 in the first move, 1 and 3 in the second one, and 1, 3 and 4 in the last one. This is considered equivalent to, say, first pressing 1 and 3; then 1, 2, 4; and then 1, 3, 4.

输入:

The input has at most 500 lines, one for each test case. Each line contains three integers n (1 <= n <= 1 000), m (1 <= m <= 1 000), and v (0 <=v <= n). The last line of input will hold the values 0 0 0 and must not be processed.

输出:

The input has at most 500 lines, one for each test case. Each line contains three integers n (1 <= n <= 1 000), m (1 <= m <= 1 000), and v (0 <=v <= n). The last line of input will hold the values 0 0 0 and must not be processed.

样例输入:

3 3 1
6 4 0
6 4 3
0 0 0

样例输出:

7
10416
9920


  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c