No.3533 Difficult Counting Problem?
タグ : / 解いたユーザー数 77
作問者 :
nauclhlt
/ テスター :
あいすあうと
問題文
$N\times N$ の $2$ 次元グリッドがあります。このグリッドの上から $i(1\leq i\leq N)$ 行目、左から $j(1\leq j\leq N)$ 列目のマスをマス $(i, j)$ と呼びます。
マス $(1, 1)$ から隣り合うマスに移動することを $0$ 回以上繰り返してマス $(N, N)$ に到達する道順のうち、同じマスを $2$ 回以上通らないようなものを良い道順といいます。
$N$ が与えられるので、良い道順の総数を計算してください。答えは非常に大きくなることがあるので、$2$ で割った余りを求めてください。
$T$ 個のケースについて解いてください。
良い道順の形式的な定義
マスの座標全体の集合を $I=\lbrace (i, j) \ |\ i, j\in \lbrace 1, 2, \cdots, N\rbrace \rbrace$ とします。
このとき、良い道順とは以下の条件をすべて満たすような列 $X=(X_1, X_2, \cdots, X_K)$ のことをいいます。
- $i=1, 2, \cdots, K$ に対して $X_i\in I$
- $X_i=(1, 1)$
- $X_K=(N, N)$
- $X_1, X_2, \cdots, X_K$ は相異なる
- $1\leq i\leq K-1$ を満たす任意の整数 $i$ に対して $X_i$ の表すマスと $X_{i+1}$ の表すマスは $1$ 辺を共有して隣接する
- すなわち、$X_i=(i_1, j_1), X_{i+1}=(i_2, j_2)$ を満たす $i_1, j_1, i_2, j_2$ をとると、$|i_1-i_2|+|j_1-j_2|=1$ を満たす
また、$2$ つの道順 $A, B$ は次のいずれかを満たすときに限り別々のものとして数えます。
- $|A|\neq |B|$
- $|A|=|B|$ かつ、ある $i\ (1\leq i\leq |A|)$ が存在して $A_i\neq B_i$
ここで $|A|, |B|$ はそれぞれ列 $A, B$ の長さを表します。
「$T$ 個のケースについて解いてください」とは
本問題では $1$ つのファイルに複数のテストケースが含まれます。
一行目にテストケースの数を表す正整数 $T$ が与えられるので、それを受け取り、その後 $T$ 回に渡って上述の問題を解いてください。
実行時間はファイルごとに計測されます。すなわち、$T$ 個のテストケースのうちひとつひとつを $2$ 秒以内に解けていたとしても、$T$ 回合わせた実行時間が $2$ 秒を超えていればTLEになることに注意してください。
入力
$T$ $N_1$ $N_2$ $\vdots$ $N_T$
$N_i$ は $i$ 番目のテストケースにおける $N$ の値を表す。
- $1\leq T\leq 1000$
- $1\leq N\leq 10^9$
- 入力はすべて整数
出力
良い道順の総数を $2$ で割った余りを $1$ 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 1 2 4
出力
1 0 0
- $1$ つ目のテストケースについて、$N=1$ のときマス $(1, 1)$ のみが存在し、移動もできないため、マス $(1, 1)$ から移動しないような $1$ 通りの良い道順が存在します。よって $1$ が答えです。
- $2$ つ目のテストケースについて、$N=2$ のとき良い道順はちょうど $2$ 通り存在するので、$0$ が答えです。
- $3$ つ目のテストケースについて、$N=4$ のとき良い道順はちょうど $184$ 通り存在するので、$0$ が答えです。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。