随笔-21  评论-10  文章-21  trackbacks-0
pku 2461 Magic Bitstrings


Start by proving that in the square matrix (like the one, shown in the table in the problem statement),
the diagonal elements are always 0's if the first bit of the bitstring is 0.
这段话就可以构造出答案,猜出答案

The diagonal consists of the elements that are quadric residues modulo n. There are (n-1)/2 such distinct elements. When we mark them as 0, there are (n-1)/2 elements left. But a magic bitstring has equal number of 0's and 1's, so the remaining elements are 1.
这段话是证明猜想是对的,我还不太清楚


pku 2856 medals

仔细观察,发现 j, k, l 太大了和 他们小的时候本质上没什么区别,用n进制去理解,先假设 j, k, l 不相同那么只是需要三位数(n进制)就可枚举出所有的情况 ,相同的时候用三位数(n进制)绰绰有余, 所以 用三位数就足够枚举了


posted on 2009-02-25 22:49 wangzhihao 阅读(293) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理