|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초 (추가 시간 없음)||512 MB||9||7||7||77.778%|
You have some bags of coins. Each bag contains exactly k coins. Exactly one bag contains only counterfeit coins (we’ll call this the fake bag), while all other bags contain only real coins. All real coins weigh exactly the same number of grams. All counterfeit coins weigh exactly the same number of grams. You don’t know the exact weights of a real or counterfeit coin. You do know a counterfeit coin is strictly heavier than a real coin, but you do not know exactly how much heavier it is. The weights of the coins are positive real numbers.
You have a scale which you can use at most m times. The scale has a left and right side. To use the scale, you can place any number of coins, taken from any of the bags, on each side of the scale, as long as the total number of coins on the left and right sides are exactly equal. The scale will return a single real number s. If s is zero, both sides of the scale weigh exactly the same. If s is negative, the left side is |s| grams heavier than the right side. If s is positive, the right side is s grams heavier than the left side. Coins can be reused multiple times for different weighings, and you are able to keep track of which bag each coin came from. You must specify beforehand all weighings you want to perform (so you cannot adjust what gets weighed in future trials based on the results of previous trials). After using the scale m times, you would like to be able to determine which bag is the fake bag.
You are now wondering: given m and k, what is the maximum number of bags for which you can always determine the fake bag? This number can get large, so output it modulo the large prime 998,244,353.
The single line of input contains two space-separated integers m and k (1 ≤ m, k ≤ 106), where m is the number of weighings available to you and k is the number of coins in each bag.
Output a single integer, which is the maximum number of bags for which you can determine the fake bag in m weighings, modulo the large prime 998,244,353.
One way we can use 2 weighings to determine the fake bag among 9 bags, each containing 1 coin, is as follows:
We can determine the fake bag as follows: