FastPrep

Description

Solutions

Count Integer Sequences

🤘 INTERN📚RELATED PROBLEMS

Print the number of integer sequences of length N, A = {A1, A2, A3...., AN} possible where the Sequence A should follow the conditions below:

All elements in A should be between 0 and M (inclusive)
XOR of all the elements in A is equal to X

Print the number of integer sequence satisfying these conditions modulo 998244353.

Input Format:

N, M , X

Function Description

Complete the function countIntegerSequences in the editor.

countIntegerSequences has the following parameters:

N: the length of the sequence
M: the maximum value of the elements in the sequence
X: the XOR value to be achieved

Returns

int: the number of integer sequences modulo 998244353

Example 1:

Input:  N = 200, M = 9000606388L, X = 317329110
Output: 788002104 
Explanation:
The output is the number of integer sequences of length N that satisfy the given conditions modulo 998244353.

Example 2:

Input:  N = 3, M = 3, X = 2
Output: 5 
Explanation:
The 5 sequences of length N(3) that satisfy both the conditions are:
(0, 0, 2), (0, 1, 3), (1, 1 ,2), (2, 2, 2), (2, 3, 3).

All the sequences are of length N(3), all the elements in the sequence are between 0 and M(3) inclusive and xor of all the elements in the individual sequence is equal to X(2).

Constraints:

N/A