eolymp
bolt
Try our new interface for solving problems
Məsələlər

Binary Polynomials

Binary Polynomials

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Each mapping f of the set {0,1}^n of n-dimensional binary vectors to {0,1} is called Boolean function of n variables and denoted by f(x_n,x_{n-1},...,x_1). For cryptography some properties of the Boolean functions are interesting. Let denote by B(n,k) the set of n-dimensional binary vectors that have k1's. The task is for given Boolean function f to find the number of vectors (b_n,b_{n-1},...,b_1) from B(n,k) such that f(b_n,b_{n-1},...,b_1)=1.

The Boolean function will be given by its (unique) polynomial modulo 2. In these polynomials the operations addition and multiplication modulo 2 are used, defined as shown in the tables of Fig. 1. In the polynomial of a function any product of m variables x_i1 x_i2 ... x_im could participate or not participate. So the general form of the polynomial for n variables is:

a_0+a_1x_1+a_2x_2+a_3x_2x_1+a_4x_3+a_5x_3x_1+a_6x_3x_2+a_7x_3x_2x_1+. . .+a_nx_nx_{n-1...}x_1

where all coefficients a_j, j=0,1,...,N=2^n-1, are 0's or 1's and if the coefficient is equal to 0 we will omit the corresponding product and if it is equal to 1 we just will omit the coefficient. For example, the polynomial of the Boolean function disjunction of 2 variables given on Fig. 2 is 0+1.x_1+1.x_2+1.x_2x_1=x_1+x_2+x_2x_1.

Giriş verilənləri

Your program has to be ready to solve more than one test case. The first line of the input file will contains only the number T of the test cases. Each of the following T lines will describe one function - first the numbers n and k separated by single space (1n18, 0kn) and then, separated by one more space a string of 2^n0's and 1's that are the coefficients of the corresponding polynomial, ordered as in the general form of the polynomial given above.

Çıxış verilənləri

The output file have to contain T lines with a single number each - the number of vectors found by your program.

Nümunə

Giriş verilənləri #1
3
2 1 0111
4 2 1000000000000000
5 3 00000000000000000000000000000001
Çıxış verilənləri #1
2
6
0
Mənbə ACM ICPC Southeastern European Regional Programming Contest, Bucharest, Romania, October 18, 2003