つーさのくーかん

超久しぶりに参加した。
250を解くのが遅すぎたし、500には手も足も出なかった。
案の定レーティング下がった。
停滞は後退とよく言ったモノで。青から再出発。

Easy 250

public class WinterAndPresents
{
　public long getNumber(int[] apples, int[] oranges);
}

リンゴとオレンジが入ったバッグがいくつかある。
apples[i], oranges[i] は、i番目のバッグのリンゴとオレンジの数を表す。
ある正の数Xを決め、それぞれのバッグからX個ずつ同じ数の果物を取って1つのギフトセットを作ることを考える。
全部で何種類のギフトセットが作れるか返すメソッドgetNumberを実装せよ。
2つのギフトセットについて、リンゴまたはオレンジの数が異なるとき、それらは異なるセットと見なす。

制約: apples.Length = oranges.Length <= 50
制約: apples[i], oranges[i] < 1000000
制限: 実行時間2秒 メモリ64MB

サンプル

getNumber({1},{1}) → 3 // {apples, oranges} = {1,0}, {0,1}, {1,1} の組み合わせの3種類
getNumber({1, 2, 0, 3}, {4, 5, 0, 6}) → 0 // 空のバッグがあるのでギフトセットは作れぬ。
getNumber({2, 2, 2}, {2, 2, 2}) → 16 // {0,3}, {1,2}, {2,1}, {3,0}, {0,6}, {1,5}, {2,4}, {3,3}, {4,2}, {5,1}, {6,0}, {3,6}, {4,5}, {5,4}, {6,3}, {6,6}
getNumber({7, 4, 5}, {1, 10, 2}) → 46
getNumber({1000000}, {1000000}) → 1000002000000

Normal 500

public class WinterAndSnowmen
{
  public int getNumber(int N, int M);
}

二人の雪だるまがゲームをするらしい。
正の整数集合a, bを次の条件を満たすように作る。
・集合 a に含まれる整数はN以下
・集合 b に含まれる整数はM以下
・aとbに同じ数は含まれない
・aに含まれる全ての数をXORしたもの < bに含まれる全ての数をXORしたもの。

このような集合ペアの作り方は何通りあるか計算し答えるメソッドを実装せよ。
なお、結果は非常に大きくなる場合があるので、1,000,000,007で割った余りを答えること

制約：N, M <= 2000
制限: 実行時間2秒 メモリ64MB

サンプル

getNumber(2, 2) → 4 // { {},{1} }, { {},{2} }, { {},{1,2} }, { {1},{2} } の4通り
getNumber(1, 1) → 1 // {}, {1} しかない
getNumber(3, 5) → 74
getNumber(7, 4) → 216
getNumber(47, 74) → 962557390

Hard 950

読んでない