![解法
個数をどうやって数える？
後半は無視して前半がどうなるかだけを考える。
簡単な組み合わせの計算。二項係数を用いたり、
(|S|/2)! / (Π (n[c]/2)!)
( ただし、 n[c] は S に文字 c が何回表れるか )
を用いたり。計算量は O(|S|) 。
64bit 整数を使えばオーバーフローとか気にせず計
算できます。](https://image.slidesharecdn.com/anagram-120318040647-phpapp02/85/Anagram-4-320.jpg)
More Related Content
What's hot (20)
Anagram
- 1. 回文なアナグラム 原案?問題文：宮村 解答：宮村、橋本 解説：宮村
- 2. 問題概要 文字列 S が与えられる。 S のアナグラムで回文に なっているものの個数を求めてください。 |S| ≦ 40
- 3. 解法 解を持たない条件は？ 奇数回出現する文字が 2 個以上存在するとき それ以外の場合は必ず解を持つ
- 4. 解法 個数をどうやって数える？ 後半は無視して前半がどうなるかだけを考える。 簡単な組み合わせの計算。二項係数を用いたり、 (|S|/2)! / (Π (n[c]/2)!) ( ただし、 n[c] は S に文字 c が何回表れるか ) を用いたり。計算量は O(|S|) 。 64bit 整数を使えばオーバーフローとか気にせず計 算できます。
- 5. 解答例 宮村： C 37 行 501 byte 橋本： Java 32 行 632 byte