※ 引述《HiltonCool (野兽疯)》之铭言：
: ※ 引述《qoojordon (颖川琦)》之铭言：
: : 102 DS 9
: : 看不太懂题目再问什么 , 是考回文吗 ?
: : 010010 长度k的回文可能个数有几种 ?
: 应该就是考回文的个数没错
: 因为第 k 个 bit 一定要跟第 1 个 bit 一样
: 所以前面 k/2 个 bits 一定要跟后面 k/2 个 bits 一样
: 令 T(k) 表示长度为 k 的回文个数
: ┌ ┐
: => T(k) = 2^│k/2│，T(1) = 2
我不太懂为什么这个跟回文有关系..
因为symmetric function只跟 x_i 的总和有关
http://ppt.cc/lcGT
所以一个symmetric function就等同于{0, 1, ..., k} -> {0, 1}的mapping
因此symmetric funtion的个数是2^(k+1)

他定义的函数为f(x1,x2,...,xk,xk,...,x2,x1)所以我才会觉得题目的symmetric不是离散的symmetric但数学应该不会用f：{0,1}^k → {0,1}定义一个函数吧这样不就等于是f:{0,1} → {0,1}吗？

{0,1}^k 代表是k个bits..

我知道，但以数学的角度来看，重复k次跟原来是一样的

好吧 我没看清楚题目 但是我觉得他打错字了..因为按照你的解释 这样输入会有2k个 但是题目说有k个变量.

= =...F大有睡觉吗?我手边没有答案只能提出来大家讨论 =口=最大的问题应该是x1,x2...xk第定义是什么? 依照f定义,输入是字串,输出是boolean,可是题目把x1放在输入,代表x1是字串? 后面定义的symmetric又对x1~xk做sigma,定义是总合?boalean的OR?还是??

我也搞不懂他最后sigma是什么意思

我也是在猜测题目要考的是什么，因为考在DS又给这样的函数，所以我才把他解读成是回文，单就input数量来看的话，input总共会有2k个应该是没错的，只是symmetric的函数是什么我就不清楚了

我会这样回 是因为symmetric function在计算理论上是有明确定义的.. 看wiki的Symmetric Boolean function

有点理解你要说的意思了 , 前半段怎么mapping方式出来后半段就是一样的输出 , f其实就是 B^k→B

哇...那我完全理解错误，所以F大说题目打错的地方应该是f(x1,x2,...,xk)对吧？

http://ppt.cc/lcGT 应该就是你说的那样 , 刚刚估到的照上面的说明,sigma的定义是相加不是OR,symmetricboolean function在意的是input中有几个1,这样修改后的答案应该修正为2^(k+1)比较好,因为k个bits的输入,1的个数可能是0~k共k+1种可能你也可以试试看看这题 http://ppt.cc/t4o2ANS: 2^(2^n) , 4