编程介的小学生 2017-09-01 17:15 采纳率: 20.5%
浏览 704
已采纳

Binary Polynomials

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(xn,xn-1,��,x1). 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 k 1's. The task is for given Boolean function f to find the number of vectors (bn,bn-1,��,b1) from B(n,k) such that f(bn,bn-1,��,b1)=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 could participate or not participate. So the general form of the polynomial for n variables is:

a0+a1x1+a2x2+a3x2x1+a4x3+a5x3x1+a6x3x2+a7x3x2x1+. . .+aNxnxn-1��x1

where all coefficients aj, 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.x1+1.x2+1.x2x1=x1+x2+x2x1.

+
0
1
0
0
1
1
1
0

*
0
1
0
0
0
1
0
1

x2
x1
f
0
0
0
0
1
1
1
0
1
1
1
1
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 (1 <= n <= 18,0 <= k <= n) and then, separated by one more space a string of 2^n 0's and 1's that are the coefficients of the corresponding polynomial, ordered as in the general form of the polynomial given above.

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

Sample Input

3
2 1 0111
4 2 1000000000000000
5 3 00000000000000000000000000000001

Sample Output

2
6
0

  • 写回答

1条回答 默认 最新

报告相同问题?

悬赏问题

  • ¥15 为什么使用javacv转封装rtsp为rtmp时出现如下问题:[h264 @ 000000004faf7500]no frame?
  • ¥15 乘性高斯噪声在深度学习网络中的应用
  • ¥15 运筹学排序问题中的在线排序
  • ¥15 关于docker部署flink集成hadoop的yarn,请教个问题 flink启动yarn-session.sh连不上hadoop,这个整了好几天一直不行,求帮忙看一下怎么解决
  • ¥30 求一段fortran代码用IVF编译运行的结果
  • ¥15 深度学习根据CNN网络模型,搭建BP模型并训练MNIST数据集
  • ¥15 C++ 头文件/宏冲突问题解决
  • ¥15 用comsol模拟大气湍流通过底部加热(温度不同)的腔体
  • ¥50 安卓adb backup备份子用户应用数据失败
  • ¥20 有人能用聚类分析帮我分析一下文本内容嘛