HBC237553[SCOI2012]滑雪与时间胶囊,图论,生成树,排序Rabbit题解

水水月牙算法基础篇 2023-11-20 14:53:01 103 0

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

Mr.Gree has a lot of cute rabbits in the farm, and every rabbit has a number a1,a2,a3...ana_1, a_2, a_3...a_na1,a2,a3...an. Different rabbits may have same numbers. Mr.Gree thinks The Cute Value of these rabbits is a1a2a3...ana_1 * a_2 * a_3 * ... * a_na1a2a3...an. One day, he wants to make The Cute Value changed, so he takes away exactly one rabbit and The Cute Value is changed. Mr.Gree wants to know how many different numbers The Cute Value could be?For example, Mr.Gree has three rabbits numbered [3,4,5], now The Cute Value is 345=603*4*5 = 60345=60. If he takes away a rabbit numbered 3, The Cute Value will change to 45=204*5=2045=20. And if he takes away a rabbit numbered 4, now The Cute Value will change to 35=153*5=1535=15. And if he take away a rabbit numbered 5, now The Cute Value will change to 34=123*4=1234=12. So The Cute Value could change to 12, 15 or 20 three numbers after one rabbit is took away.

What a cute rabbit! Mr.Gree has a lot of cute rabbits in the farm, and every rabbit has a number a1,a2,a3...ana_1, a_2, a_3...a_na1,a2,a3...an. Different rabbits may have same numbers. Mr.Gree thinks The Cute Value of these rabbits is a1∗a2∗a3∗...∗ana_1 * a_2 * a_3 * ... * a_na1∗a2∗a3∗...∗an. One day, he wants to make The Cute Value changed, so he takes away exactly one rabbit and The Cute Value is changed. Mr.Gree wants to know how many different numbers The Cute Value could be? For example, Mr.Gree has three rabbits numbered [3,4,5], now The Cute Value is 3∗4∗5=603*4*5 = 603∗4∗5=60. If he takes away a rabbit numbered 3, The Cute Value will change to 4∗5=204*5=204∗5=20. And if he takes away a rabbit numbered 4, now The Cute Value will change to 3∗5=153*5=153∗5=15. And if he take away a rabbit numbered 5, now The Cute Value will change to 3∗4=123*4=123∗4=12. So The Cute Value could change to 12, 15 or 20 three numbers after one rabbit is took away.