İkili Polinomlar#5758
Hər bir f təsviri n ölçülü ikili vektorlar dəstəsi {0,1}^n üzərində {0,1}-ə olan təsviri n dəyişənli Boole funksiyası adlanır və f(x_n,x_{n-1},...,x_1) ilə işarə olunur. Kriptoqrafiyada Boole funksiyalarının bəzi xüsusiyyətləri maraq doğurur. B(n,k) ilə k ədəd 1 olan n ölçülü ikili vektorlar dəstəsini işarə edək. Verilmiş Boole funksiyası f üçün B(n,k) dəstəsində olan və f(b_n,b_{n-1},...,b_1)=1 olan vektorların sayını tapmaq tələb olunur.
Boole funksiyası onun (unikal) polinomu ilə modulo 2 veriləcək. Bu polinomlarda toplama və vurma əməliyyatları modulo 2 ilə istifadə olunur, Şəkil 1-də göstərilən cədvəllərdə müəyyən edildiyi kimi. Funksiyanın polinomunda hər hansı m dəyişənli x_i1 x_i2 ... x_im məhsulu iştirak edə bilər və ya iştirak etməyə bilər. Beləliklə, n dəyişənli polinomun ümumi forması belədir:
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
burada bütün əmsallar a_j, j=0,1,...,N=2^n-1, 0 və ya 1 olur və əgər əmsal 0-a bərabərdirsə, müvafiq məhsulu buraxacağıq və əgər 1-ə bərabərdirsə, sadəcə əmsalı buraxacağıq. Məsələn, Şəkil 2-də verilmiş 2 dəyişənli Boole funksiyasının disjunktsiyası polinomu 0+1.x_1+1.x_2+1.x_2x_1=x_1+x_2+x_2x_1 şəklindədir.
Proqramınız bir neçə test halını həll etməyə hazır olmalıdır. Giriş faylının ilk sətri yalnız test halların sayı T olacaq. Sonrakı T sətirdən hər biri bir funksiyanı təsvir edəcək - əvvəlcə n və k rəqəmləri tək boşluqla ayrılmış şəkildə (1 ≤ n ≤ 18, 0 ≤ k ≤ n) və sonra bir daha boşluqla ayrılmış şəkildə müvafiq polinomun əmsalları olan 2^n ədəd 0 və 1 simvolu olacaq, yuxarıda verilmiş polinomun ümumi formasında olduğu kimi sıralanmışdır.
Çıxış faylı T sətirdən ibarət olmalıdır və hər biri proqramınız tərəfindən tapılmış vektorların sayını göstərən tək bir rəqəm olmalıdır.
Nümunə 1