|
|
参考 百度知道 给定L,M,K,N,求序列A的数量。满足: 1. A的长度为L 2. A中元素均在 [1,M] 间的正整数 3. A的元素之和为K的倍数 求字典序第N小的序列A,排名从0开始标号 (即,称最小为“第0小”) L<=100,M<=50,K<=50 N范围题目没有给 Edited by author 26.12.2021 13:22 Edited by author 26.12.2021 13:22 "choosing" -> "chosen" "divided" -> "divisible" "satisfied" -> "satisfying the" "is really completely defines" -> "completely defines" These aren't just typos, they impede the understanding. Test#11 4 10 4 2497 Out - 10 10 10 2 What's wrong? Help!!! I think the res is : 10 10 10 10 DP on Amount x Remainder (100x50), then continusously subtract calculated amounts with 1... 2... 3... from given index. Once it becomes strictly less than current number - proceed deeper for the next value. What is wrong with this test ? I had WA17, but that was too few reserved digits. - N is much smaller than 50^100. 50^100 - is the number of all possible states, but N is the order of all ALLOWABLE states (whose sum mod K = 0 )and that's quite less, but still does not fit even in int64 :(. Wherefore, you have to use long arifmetics. If K=1, you'll get your 50^100 :) My program get AC, but works incorrectly on this test. Please add it: 100 100 1 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 This test is incorrect, because M must be <= 50. If you have got WA on Test #5, just pay attention to the statement of the problem. It is said that N is "an arbitrary vector of length L" in the problem, but actually N is just an INTEGER. So, read an integer instead of reading a string with length L. I've used BigInteger solving this problem, am I supposed to use this class on timus and acm contest? Does anybody know may I also use on contests HashMap and another such powerfull classes. You can use it. And also everything from STL. Am I right? 1. there are 200 chains with first digit from 1 to 8 2. 201: 9-1-2 202: 9-1-6 203: 9-1-10 204: 9-2-1 205: 9-2-5 206: 9-2-9 207: 9-3-4 208: 9-3-8 209: 9-4-3 210: 9-4-7 211: 9-5-2 212: 9-5-6 213: 9-5-10 !! 214: 9-6-1... Then, is sample correct? First chain has index 0. So test is correct. |
|
|