|
||||||||||
Problem B. BeadsTime Limit: 8000/4000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 277 Accepted Submission(s): 98 Problem Description There are m different colors of beads. Define a necklace of length n is a cyclic string that successively connects n beads, taking all rotations and overturnings as equivalent. For example, [1, 2, 3, 4] is equivalent to [2, 3, 4, 1], [3, 4, 1, 2] and [4, 1, 2, 3] (by ro-tation); and [1, 2, 3, 4] is equivalent to [1, 4, 3, 2], [3, 2, 1, 4], [2, 1, 4, 3] and [4, 3, 2, 1] (by overturning). Moreover, each time you could transpose the beads of color i to color (i mod m) + 1 for all i at the same time. After some operations, if a necklace A becomes B, then B is equivalent to A. Count the number of necklaces modulo 998244353. Input The first line of the input contains an integer T , denoting the number of test cases. In each test case, there are two integers n, m in one line, denoting the length of necklaces, and the number of colors. 1 ¡Ü T ¡Ü 20, 3 ¡Ü n ¡Ü 10^18, 2 ¡Ü m ¡Ü 10^18, 998244353 ²»Õû³ý n, m Output For each test case, output one line contains a single integer, denoting the number of necklaces modulo 998244353. Sample Input
Sample Output
Hint For n = 3, m = 2: - [1, 1, 1], [2, 2, 2] are equivalent - [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], [1, 2, 2] are equivalent Source | ||||||||||
|