問題一覧 > 通常問題

No.2965 Don't Stop the Game again

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.024秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 10
作問者 : twitteryou / テスター : 👑 qand
お気に入りにしたユーザー ProblemId : 11539 / 自分の提出
問題文最終更新日: 2024-11-17 21:16:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 453 (順位表) の他の問題:

Story

Your mother has hidden your game again. Once again it has been left on a server, and the password has been split up...

Because of what happened last time, countermeasures have been taken... but somehow it seems you can still send strange queries.

You are given the mission of recovering the password.

Problem Statement

There are integer sequences $A=(A_1,A_2,\cdots,A_{50})$ and $Q=(Q_1,Q_2,\cdots,Q_{50})$ of length $50$, and an integer $M$. It also holds that $\lbrace Q_1,Q_2,\cdots,Q_{50}\rbrace=\lbrace 1,2,\cdots,40\rbrace$.

Here, $Q$ and $M$ are given, but $A$ is not given and is kept hidden by the judge.

There is also an array $B$ of length $50$ whose elements are all initially $0$, and the following operations can be performed on $B$.

  • Operation $1$: Send an integer $j\ (1 \leq j \leq 50)\ $ to the judge. Each $B_i\ (1 \leq i \leq 50)$ is replaced by the remainder when the value obtained by adding $A_{j}^{Q_i}$ to it is divided by $M$.
  • Operation $2$: Send a permutation $P=(P_1,P_2,...,P_{50})$ of $(1,2,...,50)$ to the judge. Each $B_j(1 \leq j \leq 50)$ is replaced by the remainder when the value obtained by adding $\sum_{i=1}^{50} A_{P_i}j^{i-1}$ to it is divided by $M$.
  • Operation $3$: Send $3$ integers $i,j,k(1 \leq i,j,k \leq 50)$ to the judge. $B_k$ is replaced by the remainder when $B_i \times B_j$ is divided by $M$.
  • Operation $4$: Send $3$ integers $i,j,k(1 \leq i,j,k \leq 50)$ to the judge. $B_k$ is replaced by the remainder when $B_i + B_j$ is divided by $M$.
  • Operation $5$: Send $3$ integers $i,j,k(1 \leq i,j,k \leq 50)$ to the judge. $B_k$ is replaced by the remainder when $B_i^{B_j}$ is divided by $M$.

  • You can perform at most $250$ operations in total. Perform operations so that $\sum_{i=1}^{50}A_i \equiv \sum_{i=1}^{50}B_i$ holds modulo $\text{mod}$ $M$.

    Input

    $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$
  • The input and $A_i (1\leq i \leq 50)$ are all integers.
  • Output

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

    Let $K$ be the number of operations, and output in the format above. Here, $1 \leq K \leq 250$ must hold.

    Each $\text{op}_i(1 \leq i \leq K)$ must be output in one of the following forms.

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


    The following constraints must be satisfied. Otherwise, your answer is judged as incorrect.
  • In operation $1$, $1 \leq j \leq 50$
  • In operation $2$, $(P_1,P_2,\cdots,P_{50})$ is a permutation of $(1,2,\cdots,50)$
  • In operations $3$, $4$, and $5$, $1 \leq i,j,k \leq 50$
  • Sample

    Here, for simplicity, the operations are explained with the arrays $A,B,Q$ having length $3$. Note that this differs from the actual problem.
    Program outputJudge outputExplanation
    7
    1 2 3
    First, $Q$ and $M$ are given. At this point, the judge is hiding $A=(1,2,3)$. Also, $B=(0,0,0)$.
    5First, output the number of operations.
    1 3Operation $1$ is performed with $j=3$. Then $B$ changes to $(A_3^1$ $\text{mod}$ $7,A_3^2$ $\text{mod}$ $7,A_3^3$ $\text{mod}$ $7)=(3,2,6)$.
    2 1 2 3Operation $2$ is performed with $P=(1,2,3)$. Then $B$ changes to $(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 3Operation $3$ is performed with $i=1,j=2,k=3$. Then $B$ changes to $(2,5,B_1 \times B_2$ $\text{mod}$ $7)=(2,5,3)$.
    4 2 1 3Operation $4$ is performed with $i=2,j=1,k=3$. Then $B$ changes to $(2,5,B_2+B_1$ $\text{mod}$ $7)=(2,5,0)$.
    5 1 1 1Operation $5$ is performed with $i=1,j=1,k=1$. Then $B$ changes to $(B_1^{B_1}$ $\text{mod}$ $7,5,0)=(4,5,0)$. Clearly, $\sum_{i=1}^{3}A_i \neq \sum_{i=1}^{3}B_i$ modulo $\text{mod}$ $7$, so this is incorrect.

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