题目归结为判断两个自然数多集（允许有重复元素的集合）a, b是否相等。用快排比较的效率是O(nlgn)，下面提出一种O(n)的方法供大家参考。

猜想：若 sum(a^i) = sum(b^i)，i = 0, 1, 2, 则 a = b。
证明：？

注意
sum(s^0) 是多集s中元素的数目
sum(s^1) 是多集s中元素的和
sum(s^2) 是多集s中元素的平方和

即比较多集的三个统计值即可。以上算法是AC的。但是我还没有一个满意的证明。

• HAHA HEHE 输出YES 怎么A的 (3) longpo 2009-01-12 17:11:04
  • Re:HAHA HEHE 输出YES 怎么A的 (48) asterix314 2009-01-12 20:38:20
    • Re:HAHA HEHE 输出YES 怎么A的 (36) longpo 2009-01-13 10:41:58
      • Re:HAHA HEHE 输出YES 怎么A的 (239) asterix314 2009-01-13 19:56:22
        • Re:HAHA HEHE 输出YES 怎么A的 (15) MasterLuo 2009-01-13 20:12:12
          • Re:HAHA HEHE 输出YES 怎么A的 (936) asterix314 2009-01-13 20:56:36
        • 理解了， 果然大牛啊 (10) longpo 2009-01-13 22:34:45
• Re:一种O(n)算法 (320) watergear 2010-05-17 20:21:51
  • Re:一种O(n)算法 (119) darkcaller 2010-12-12 12:44:20
• 这样算不算证明？ (418) oikid 2010-06-07 22:14:06
• 大致证明思路 (64) ip96cns 2010-12-01 20:04:30
• Re:一种O(n)算法 (316) endkiller 2011-02-27 01:53:34