問題一覧 > 通常問題

No.2965 Don't Stop the Game again

レベル : / 実行時間制限 : 1ケース 2.024秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 10
作問者 : ねしんねしん / テスター : 遭難者遭難者
0 ProblemId : 11539 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-11-17 21:16:03

ストーリー

またゲームを母親に隠されてしまいました。またサーバーに預けられ、パスワードを分割してしまいました…

前回のこともあり、対策されましたが…どうにかまた変なクエリーは送れるようです。

あなたにはパスワード奪還の任務を与えます。

問題文

長さが $50$ の整数列 $A=(A_1,A_2,\cdots,A_{50})$、$Q=(Q_1,Q_2,\cdots,Q_{50})$、整数 $M$ があります。また $\lbrace Q_1,Q_2,\cdots,Q_{50}\rbrace=\lbrace 1,2,\cdots,40\rbrace$ が成り立っています。

ここで、$Q$、$M$ は与えられますが、$A$ は与えられず、ジャッジ側が隠し持っています。

また、始めすべての要素が $0$ である長さが $50$ の配列 $B$ があり、$B$ に対し次の操作が行えます。

  • 操作 $1$ :整数 $j\ (1 \leq j \leq 50)\ $ をジャッジ側に送る。それぞれの $B_i\ (1 \leq i \leq 50)$ に $A_{j}^{Q_i}$ の値を足して $M$ で割った余りに置き換える。
  • 操作 $2$ : $(1,2,...,50)$ の順列 $P=(P_1,P_2,...,P_{50})$ をジャッジ側に送る。$B_j(1 \leq j \leq 50)$ にそれぞれ $\sum_{i=1}^{50} A_{P_i}j^{i-1}$ を足して $M$ で割った余りに置き換える。
  • 操作 $3$ : $3$ つの整数 $i,j,k(1 \leq i,j,k \leq 50)$ をジャッジ側に送る。$B_k$ を $B_i \times B_j$ を $M$ で割った余りに置き換える。
  • 操作 $4$ : $3$ つの整数 $i,j,k(1 \leq i,j,k \leq 50)$ をジャッジ側に送る。$B_k$ を $B_i + B_j$ を $M$ で割った余りに置き換える。
  • 操作 $5$ : $3$ つの整数 $i,j,k(1 \leq i,j,k \leq 50)$ をジャッジ側に送る。$B_k$ を $B_i^{B_j}$ を $M$ で割った余りに置き換える。

    • 操作は合計で $250$ 回まで行うことが出来ます。$\text{mod}$ $M$ 上で $\sum_{i=1}^{50}A_i \equiv \sum_{i=1}^{50}B_i$ が成り立つように操作を行ってください。

    入力

    $M$
$Q_1$ $Q_2$ $\cdots$ $Q_{50}$

  • $0 \leq A_i < M (1\leq i \leq 50)$
  • $2 \leq M \leq 10^{9}$
  • $\lbrace Q_1,Q_2,\cdots,Q_{50}\rbrace=\lbrace 1,2,\cdots,40\rbrace$
  • 入力と $A_i (1\leq i \leq 50)$ はすべて整数

    • 出力

    $K$
$\text{op}_1$
$\text{op}_2$
$\ldots$
$\text{op}_K$

    操作数を $K$ としたとき、上記の様に出力してください。ただし $1 \leq K \leq 250$ である必要があります。

    また $\text{op}_i(1 \leq i \leq K)$ は以下のいずれかの形で出力してください。 

    $1$ $j$
    $2$ $P_1$ $P_2$ $\cdots$ $P_{50}$
    $3$ $i$ $j$ $k$
    $4$ $i$ $j$ $k$
    $5$ $i$ $j$ $k$


    ただし、以下の制約を守る必要があります。満たしていない場合は不正解です。
  • 操作 $1$ では $1 \leq j \leq 50$
  • 操作$2$では $(P_1,P_2,\cdots,P_{50})$ は $(1,2,\cdots,50)$ の順列
  • 操作 $3$、操作 $4$、操作 $5$ では $1 \leq i,j,k \leq 50$

    • サンプル

    ここでは簡略化のため、配列 $A,B,Q$ の長さを $3$ にして操作の説明を行います。実際とは違うことに注意してください。
    プログラム側の出力ジャッジ側の出力説明
    7
    1 2 3    		まず、始めに $Q$ と $M$ が渡されます。このとき、ジャッジ側では $A=(1,2,3)$ を隠し持っています。また $B=(0,0,0)$ です
    5まず操作数を出力します。
    1 3$j=3$ で操作 $1$ を行いました。そのとき、$B$ は $(A_3^1$ $\text{mod}$ $7,A_3^2$ $\text{mod}$ $7,A_3^3$ $\text{mod}$ $7)=(3,2,6)$ に変わります。
    2 1 2 3$P=(1,2,3)$ で操作 $2$ を行いました。そのとき、$B$ は $(3+A_1 \times 1^0+A_2 \times 1^1+A_3 \times 1^2$ $\text{mod}$ $7,2+A_1 \times 2^0+A_2 \times 2^1+A_3 \times 2^2$ $\text{mod}$ $7,6+A_1 \times 3^0+A_2 \times 3^1+A_3 \times 3^2$ $\text{mod}$ $7)=(2,5,5)$ に変わります。
    3 1 2 3$i=1,j=2,k=3$ として操作 $3$ を行いました。そのとき、$B$ は $(2,5,B_1 \times B_2$ $\text{mod}$ $7)=(2,5,3)$ に変化します。
    4 2 1 3$i=2,j=1,k=3$ として操作 $4$ を行いました。そのとき、$B$ は $(2,5,B_2+B_1$ $\text{mod}$ $7)=(2,5,0)$ に変化します。
    5 1 1 1$i=1,j=1,k=1$ として操作 $5$ を行いました。そのとき、$B$ は $(B_1^{B_1}$ $\text{mod}$ $7,5,0)=(4,5,0)$に変化します。明らかに、$\text{mod}$ $7$ 上で $\sum_{i=1}^{3}A_i \neq \sum_{i=1}^{3}B_i$ なので不正解です。

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