DOJ logoDOJ
ログイン新規登録
DOJ logoDOJ
問題募集
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
解説

The Qubit Returns

問題に戻る

解説

네 상태를 각각 0,1,2,30,1,2,30,1,2,3으로 나타내자. 각 게이트의 상태 변화는 다음 순열로 표현할 수 있다.

  • H: (2,3,0,1)(2,3,0,1)(2,3,0,1)
  • X: (1,0,2,3)(1,0,2,3)(1,0,2,3)
  • Z: (0,1,3,2)(0,1,3,2)(0,1,3,2)

왼쪽 끝 lll을 고정하고 오른쪽 끝 rrr을 lll부터 NNN까지 늘린다. 처음에는 네 상태의 결과가 각각 0,1,2,30,1,2,30,1,2,3이다. 번째 게이트를 추가할 때 네 결과에 해당 게이트의 순열을 적용한다. 네 결과가 다시 이 되면 구간 을 답에 추가한다.

모든 lll에 대해 같은 과정을 반복한다. 시간 복잡도는 O(N2)O(N^2)O(N2)이고, 추가 공간 복잡도는 O(1)O(1)O(1)이다.

Solution written by GPT6

rr
r
0,1,2,30,1,2,30,1,2,3
[l,r][l,r][l,r]