問題一覧 > 通常問題

No.1683 Robot Guidance

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 71
作問者 : SumitacchanSumitacchan / テスター : 👑 hitonanodehitonanode 👑 ygussanyygussany
3 ProblemId : 6820 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-29 18:27:13

問題文

$xy$ 平面上の原点 $(x,y)=(0,0)$ にロボットが置かれています。このロボットは、最初は $x$ 軸正の方向を向いています。

あなたはこのロボットに対し、次の $2$ 種類の命令を行うことができます。

  • G: ロボットは向いている方向に $1$ 進む。
  • T: ロボットは反時計回りに $90$ 度回転する。すなわち、この命令が行われるごとにロボットの向きは、 $x$ 軸正 → $y$ 軸正 → $x$ 軸負→ $y$ 軸負 → $x$ 軸正 → $\cdots$ と順に変わる。

あなたは、 $A$ 回の命令Gと $B$ 回の命令Tをある順番で行うことを考えています (そのような命令順は $\binom{A+B}{A}$ 通り考えられます)。
あなたの目標は、$A+B$ 回の全ての命令が終わった後にロボットが $(x,y)=(X,Y)$ にいるようにすることです。
この目標を達成できるような命令順は何通りあるでしょうか。
答えは非常に大きくなることがあるので $10^9+7$ で割った余りを出力してください。

入力

$A\ \ B\ \ X\ \ Y$

  • $0\le A,B\le 10^6$
  • $A+B>0$
  • $-10^6\le X,Y\le 10^6$
  • 入力は全て整数である。

出力

ロボットが最終的に $(x,y)=(X,Y)$ にいるような命令順の数を $10^9+7$ で割った余りを出力してください。

サンプル

サンプル1
入力
2 1 1 1
出力
1

命令Gを $2$ 回、命令Tを $1$ 回行うような命令順はTGG, GTG, GGTの $3$ 通りです。

そのうちGTGのみ、ロボットの最終位置が $(x,y)=(1,1)$ になります。
GTGという命令順の下で、ロボットは次のように動きます。

  • 最初の命令Gで $(x,y)=(1,0)$ に進む。
  • 次の命令Tで $y$ 軸正の方向を向く。
  • 最後の命令Gで $(x,y)=(1,1)$ に進む。
  • サンプル2
    入力
    1 6 0 1
    出力
    2

    TGTTTTT, TTTTTGTの $2$ 通りです。

    サンプル3
    入力
    998 244 35 3
    出力
    634338670

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。