2019-09-21

会津大学競技プログラミング合宿2019 参加記

日常

会津大学 競技プログラミング合宿2019

大学生になり、開催日が夏休みに含まれるようになったので念願のACPCに参加してきました
JAG合宿から一日あいてすぐなので疲労がやばいと思っていたけど思ってたより疲れてなくて自分の体力を褒めてあげたい

Day0

普通に寝落ちしてしまった、眠いから寝る

Day1

寝落ちしてしまったので荷造りを一瞬で終わらせる、ホテルはタオルが用意されてるから神なんだよな

通勤ラッシュの中、クソデカスーツケースを持って東京に向かって新幹線に乗る、新幹線は快適
郡山についたら軽く朝ごはん的なものを食べた

郡山 pic.twitter.com/1KAkydVr0F
— 迷路 (@pazzle1230) 2019年9月18日

なんちゃらかんちゃら線に乗るんですが、1号車に乗ろうとしたら変なところに乗っていた、謎の力が働いてしまった...

コミュ障力を発揮して電車の中に無限に競プロerっぽい人がいるのをスルーし、他の号車に入った
— 迷路 (@pazzle1230) 2019年9月18日

会津若松に着くまでの間に唯一の夏休みの宿題が、夏休みが始まって1ヶ月以上でようやく終わった、長く苦しい戦いだった
まずワシントンホテルにスーツケースを預けに行った、天才なので
そしてplatypusさんが高速バスで来るのでそれを待ってから歩いて会津大学に向かった. 過去のPCKで忘れ物をして会津大学→ワシントンホテル→会津大学を徒歩で移動した経歴を持っているので余裕やろと思っていたら最初の方向を間違えていたため知らない道を歩いていくことになった、Google Mapありがとう、世界一好きなサービスです！

自己紹介フェーズをなんとか無難に終わらせ、Fixstarsさんの会社紹介聞いた、労働してーなー！俺も

チーム分けは事前にコミュニケーションをして根回しができないので†ランダム†で、よこさんとshotさんと組んだ

コンテスト

まずCを読んで、SCC貼るだけやんけ！コピペして終わりや！と思ったけどとりあえずAを実装してもらう
Aが通るのでCを書いて提出してPresentationErrorになってキレる

DとEを読む
Dはシミュレーションすればいいかなと思ってshotさんに書いてもらったら詰まってたので僕が書くことにした。僕は無限にバグらせた。
もう一回最初から書き直すことであとはコーナーケースだけというところになったのでソート順を変えて頑張った

EはDPっぽいんですがなんか無理だなぁとなってしまいボーッとしていた、するとshotさんがR+Tで降順ソートすれば勝ちと言っていたので実装する
添字がアで無限にバグらせました

終わり

バグらせるのやめてぇ

ほか

喜多方ラーメンを食べにいく
こういうPCKのときはできなかったことをして会津を満喫していきたい

実質1333ラーメンを食べた pic.twitter.com/1RtjQPfukW
— 迷路 (@pazzle1230) 2019年9月18日

ラーメンを食べたらホテルに戻り、コドフォに向けて英気を養う

つもりだったんですがいつの間にか寝ていて起きたら1時半だった
風呂に入ってTwitterをして寝る

Day2

ホテルについてきたこだわりの朝食を食べる
ヨーグルトが激おいしすぎてやばい、これが会津のべこの牛乳か...

ガスライトでこだわりの朝食 pic.twitter.com/qL0AoZDFCR
— 迷路 (@pazzle1230) 2019年9月18日

楽をしたすぎるのでバスを使って会津大学に向かう

PASMOって...使えますか？と聞いてしまう
整理券式なのに気づかず先にお金を払おうと値段がどこに書いてるか見つけようとしてしまう
お釣りは出ませんと書いていて、両替の場所があるのに570円を払ってしまう

すいませんでした！！！！

チームはplatypusさんとwk1080idさんと組む
この日は5時間セットだしランダムで事故るのは厳しいのでは？と思って組んでしまった

コンテスト

Bを考察,実装する
Cをplatypusさんから受け取って実装する
Mをplatypusさんが書いた式をそのまま写す
Iを実装して、答えが全然合わないのでキレて最後の答えを出すとき1点取得をしまくることにすると合う、時間をめっちゃ潰したけど原因はセグ木のバグだった
セグ木...信じてたのに... Gの実験コードを適当に書いて規則性を見つけようとするが、普通にplatypusさんが解くまで実験コードすらバグっていた
Hみたいなのは包除なんですよ！ｗと言いながらなかなか立てられない式を適当に実装してみると答えが合うので提出したらAC
Lはどう見てもSCCで、マンハッタン距離なので8通りをsetで用意して候補はbeginかendなんだよな〜！マージテク！ｗとか言ってたが SCCの結果を木だと勘違いしていてだめだった、結局8通りの最小値しか見なくていいことがわかってただのDAG上DPになるけどバグって通せなかった

実装下手すぎないか？競プロやめたい

ほか

懇親会があるので大学から歩いて会場に向かう
未成年なので成人している人たちがどうなるか見るのを楽しみにしていた
中華料理うまいなぁ、辛いなあと思いながら適当に食べまくり、コーラを飲みまくったらお腹が一杯になった
やっぱみんなどんどん声が大きくなったり酔っぱらってるような行動になっていて面白かった

beetさんが気づいたら倒れていたのがとても面白かった、ACPC懇親会の醍醐味らしいので来年も楽しみにしていきたい

部屋に戻ってダラダラFを通したら気づくと寝ていた

Day3

もういちどこだわりの朝食を食べる
やっぱヨーグルトがうまいんだよな〜！

この日はチームはランダムで出た

コンテスト

四人チームになったので、A,B,C,Dをまず割り振って僕はDから読んだ
ただの桁DPだったのでAとCが通されてから実装してAC
Bが明らかに見た目ヤバそうで自分では実装したくないな...となっていたのでありがとうという気持ち

Eを読み、更新なければO(N)で解けるな〜累積させて〜クエリを〜とか考えて永遠に詰まっていた
僕はDUSTをといたことありますが...
結局『maximum sum of subarray update』とかで検索するとただのセグ木の問題ですみたいなことが書いてたのでわかって通す
これわからないの真面目に辛くなってしまったな
Fは一瞬うまくオートマトンとかをつくって受理されるか〜みたいな問題が存在するのかな...とか思ったけどDPをやれば良いことがわかり、実装を始める
いつものようにSA-ISとLCPを取り出し、使い方を忘れている中考察を詰めなかったので[tex: O(N log² N)]を実装してTLEになり、assertを消して通そうとして通らず泣いていた
結局にぶたんが一つでいいことがわかったので実装バグらせて1WAだしたりREをだしながら $O(N log N)$ で通す
解説に前計算すれば早くなるって書いていて、確かにO(N)じゃ〜ん！となってしまった

Gは明らかにすこしめんどくさい全方位木DPなんですが、全方位木DPを思考停止で書けないので残り時間的に不可能だなぁとなってしまった
おしまい

実装力の無さを無限に感じてしまうな...

ほか

忙しい大学生なので予定が詰まっていたため早めに帰る必要があったので解説を聞かずに誰とも挨拶をしないで帰る

さようなら… pic.twitter.com/TTRvXsORR1
— 迷路 (@pazzle1230) 2019年9月20日

前もってバスを調べていたので余裕なんですよねとか思いながらバスを待っていたら10分経ってもこなくて、バス停にいたもう一人の人がタクシーを呼んでいなくなってしまい電車の時間的にもやばくなってしまったのでタクシーを呼ぶ決意をしてタクシーを呼んだ

バスが来ねえ
— 迷路 (@pazzle1230) 2019年9月20日

最悪電車間に合わないのでは？
— 迷路 (@pazzle1230) 2019年9月20日

やばいのでタクシーを呼んだ直後にくるの、なに
— 迷路 (@pazzle1230) 2019年9月20日

タクシー、こなくないか
— 迷路 (@pazzle1230) 2019年9月20日

ゆるせない

なんとか電車に間に合ったのでそのまま帰宅する

お疲れさまでした！2泊3日のACPC楽しかったです！JAG合宿からそのままということで体力的にきついものがありましたがゆっくり休みたいと思います！

ここどーこだ pic.twitter.com/CWGpc5jRsK
— 迷路 (@pazzle1230) 2019年9月20日

友達との旅行に、家に30分ぐらい滞在してすぐに出発した
体力終了

2019-09-17

Japan Alumni Group Summer Camp 2019 参加記

JAG 夏合宿にチームメイトがだれも参加しないという異常事態のなか参加しました
僕が春合宿とかPCKでよく話していた人が誰もいない気持ちになって不安がやばかったんですが、なんとか他の人とコミュニケーションを積極的には取らないことで乗り切りました、乗り切れてません

Day1

お昼を早めに食べてから会場に向かう

おひる pic.twitter.com/I1htqP2pMQ
— 迷路 (@pazzle1230) 2019年9月14日

チームメイトがいないのでぐっちょっぱーで分かれるやつをして、olpheさんとferinさんのチームに入らせてもらうことになった

コンテスト

BとJを実装しました、チーム戦難しすぎるなぁという気持ちになった
実装のバグや勘違いをolpheさんに直してもらったりとかした

前にUKUNICHIA、右にSeica on the World、左を忘れてしまったけどそれぞれ数個風船を得ていて囲まれてしまったという気持ちになった

夕ご飯

写真を取り忘れたんですが、ビビンバの具が異常に少なくてかなしくなった

ほか

風呂が異常混雑していてやばいんですが、やばい
100円を忘れずにうまくロッカーから取り出してカフェオレを飲んで勝ち

ボードゲームをしたかったんですが、なんか埋まっていたので悲しくなりながら部屋に戻り、気づいたときにはコドフォにレジってAを提出してしまっていたので部屋で黙々とコドフォをした
5時間セットが久しぶりすぎて疲れてたので実装が全然うまくできなかった、疲れてなければもっと順位高くてレートも上がったんだろうな〜！

Day2

朝ごはんを8時ぐらいに食べに行くことで混雑を回避できて常勝ｗ

チームは、余った人で組んで2人チームで参加することになった

コンテスト

虐殺セットに虐殺されてしまった〜！
DとEを担当しました、やるだけをやるだけの人生、つらいもの

懇親会

天才なので空いてるうちにと思ってすぐに風呂に入りに行った

懇親会素晴らしいね
3000円のディナー、豪華絢爛

はやさ pic.twitter.com/RsQ4uVhqwc
— 迷路 (@pazzle1230) 2019年9月15日

ほか

ABCがありましたね、僕はボードゲームをしたいので出ません
と宣言して結局出ました、ベッドに寝っ転がりながら出たら眠気にやられて死亡してしまった
ボードゲーム、一回もできませんでしたが僕は何をしにJAG合宿に参加したのでしょうか

なんかルームメイトはまだ起きてそうだったけど眠くなりすぎてしまったので寝た

Day3

部屋を片付けて、荷物を持っていきながら朝食を食べれば効率的やん！って言いながらやったらまずシーツの回収が行われていなかったので優しい方のお世話になってなんとかした
当然8時に行くと空いてたので8時半に行けばとても空いていて快適朝食エクスペリエンスが得られるんですが、普通に少し混んでいるのに加え米がなくなっていた

この画像の変なところを探そう！ pic.twitter.com/ZgshjFLDLa
— 迷路 (@pazzle1230) 2019年9月15日

チームは、tubuannさんがWriter側にいることで枠が空いたUKUNICHIAに入る感じになった
これでTTPCでtubuannさんと組んだので現UKUNICHIAの全員と組んだことあることになるね、やったぜ

コンテスト

A、Eをやって、Bを考察した
Bみたいなの、自分で実装したら絶対バグらせるのでbeetさんに実装してもらう贅沢をしてしまった
Eもデバッグしてもらったしすごいね

ほか

帰宅した
家に帰って22時ぐらいに眠くなって寝てしまい、更に6時ぐらいに起きたのでJAGの生活リズム改善能力に恐れをなしてしまったけど来年からも夏休み最後に生活リズムを直すために行きたい
これだけでも参加した価値あったね

2019-07-13

ICPC 2019 国内予選参加記

競技プログラミング日常

ICPC 2019 国内予選

大学生になったのでICPCの国内予選に出ました
チーム名は『Lesages』で33位でした。順位表

ABCDの4完で、僕はABCDを担当しました(仕方ないね)

国内予選まで

大学生、自由になって時間がありあまり、遊びまくれると思っていたら授業が難しいしテスト多いし全然何もできないなとなり競プロもそこで時間を割いてまでやるか？という感じでモチベーションが消えてしまう
週末のABCぐらいは頑張って出ようとしてたが週明けというのは課題か小テストがあるものでそれを言い訳に出ないことが多々あった
実装力や考察力が恐ろしく下がったので継続って重要だなとおもいました

チームでの練習は色々とグダグダで、毎週木曜に大学？サークル？で競プロの集まりがありそこで1時間4問ぐらいの軽いバチャをするんですが最初の方は普通にバラバラで解いてたし、最後までいい練習場所を見つけられなかった

普通にチーム練をしたのは一回だけで、カラオケで去年の国内予選をしたが僕がA,B,Cを解いてしまっていたという失敗がありそこらへんは全部任せたが普通にチームメイトが通せて安心した
僕はDが解けてFは解法わかったがカラオケで延長失敗して追い出されて途中終了したので家で実装した(いい練習場所をください)

模擬国内予選

模擬国内予選にもカラオケから出て、このときは延長に成功して途中で追い出されはしなかった
結果としてはABCDの4完で全体27位、現役20位だったのでまあいいでしょうとなる。順位表
Cみたいな適当に詰める必要がある問題をチームメイトに投げるのが楽で良いなという気持ちになった

ただ、序盤の問題も早く解かないとICPCルールのペナルティがきついので最初の動きとかどうするべきかわからず、これは結局本番でもわからなかった(僕がタイピング一番早いので僕が全部実装することになったんですが)

ライブラリも印刷する
お守りとして某チームのライブラリも当然印刷し、beetさんとかうしさんのところから適当に拝借したやつと自分のを適当に混ぜたやつも前回の記事のやつでプリントした
大学さん、印刷代無料にしてくれ
ライブラリは目次が必要だなと思いました(はい)

前日

前日も木曜日なので大学の練習があり、ここでも1時間バチャをしたが普通に学内の他のチームに負けて険しい気持ちになる。構文解析無理ですが...
†ホスト校†なのでまあ本当に事故らなければ通るでしょ...となんとか気持ちを落ち着けて寝ようとするが寝られない、現実は非情である。次の日はテストがあるのだ。
試験勉強のためRedBull駆動で4時就寝6時半起床をする。

当日

眠いモンスターをとりあえず一気飲みする
電子的準備がどこから入るかわからず全ウインドウを閉じる人になった
なんか普通にコンテストのページぐらいは開いててもよかったのかな？わからず

国内予選

Aを読んでやるだけなので実装する、普通に時間かかってしまう
Bの問題概要を聞いて実装する。去年とは打って変わった楽さ、軽くバグらせ時間がかかってしまう
Dを軽く読むが普通にわからない
Cの問題概要と軽い考察を聞いて確かに、となったので実装する。バグらせて時間がかかってしまう
Dを考える、何回押すかは決まってるからDP行けるなとなるがWA
チームメイトがF, G, Hを適当に読んで考察をしている
僕は順当にEとFの考察をしていてほしかったですが...(このブログを見ていたらある程度難易度順に解く意識を身につけてほしい、難しくても点数は変わらないので)
Gがわかったらしく僕はDで詰まってるので実装してもらう
普通に学内2位で焦る
Gの解法、基本的なことはあってそうだったが微妙にダメそうだったので指摘したらDのだめそうなところを逆に教えてもらったので実装する
スパゲティになったがなんとか実装する
通る
学内1位なので†ホスト校†であることを考えると勝ち
Eを読むと苦行をすれば通りそうな雰囲気を感じる
時間がもうないので終了

予選通ったっぽいので競プロモチベ回復した！！！
Asia Yokohama Regionalに向けて頑張っていきたい

Codeforces Round #573

f:id:pazzle1230:20190713022627p:plain — こどふぉ順位表

競プロつまんないな、やめるか

2019-07-07

競プロライブラリをPDFにする無限にあるうちの一つの方法

プログラミング備忘録

競技プログラミングのライブラリをPDFにする無限にあるうちの一つの方法

もうすぐICPCなのでライブラリを印刷したいけど印刷できる状態にするのがめんどくさい...
そもそも綺麗にする方法なかなか見つからないし見つかってもファイル一つ一つやるのか...

そんな気分になったので競プロのライブラリをPDF(にできるようなTeXファイル)化するスクリプト書きました(誇張)
そこまで見た目が良くない(終わり)
そこまで楽でもない(はい)

リポジトリはこれなのでこっから適当にダウンロードして頑張ってください
template/template.texは使うので必要です. ちなみにプログラムへの引数のデフォルトは同じディレクトリにあること想定してるのでちゃんと指定するか移動させてください.

https://github.com/maze1230/Library-TeX-Generator

最初は細字だったんですが試しにコンビニで印刷してみたら掠れたので太字にしました
太字にしてから印刷してないのでもしかしたら文字が潰れるかもしれない(家にプリンターがほしすぎる)

準備

Python

使うライブラリの指定にtomlを使うのでtomlモジュールが必要

pip install toml

とかする

LaTeX

TeXファイルを作るだけなのでTeXファイルをコンパイルできる環境が必要
僕は"macOS Mojave 10.14.5"なのでその状況でのインストール

基本的にこれをした
少しだけ詰まったのでそこを書く

今これと同じようにmactexをインストールするとMacTeX2019が入るので気をつける

sudo tlmgr update --self --all

をしろと書いてあるが僕はパスが通ってなかったのでできなかった. 初心者なのでcommand not foundって言われて、ちゃんとインストールできなかったのか...？と数回インストールし直す人をした(初心者なので). brewでインストールしたんだからパス通ってると思っちゃわないか？思ってしまいました

sudo /usr/local/texlive/2019/bin/x86_64-darwin/tlmgr path add

みたいな感じのことをしてパスを通した、もう記憶曖昧なのでpathとadd逆かも

ついでに僕はLaTeXは書くとしたらVSCodeから書くかなぁという気持ちになったのでVSCodeのほうもやった
ここは関係ないところが原因だったけどなんか詰まって他の人のを参考にした. ただ、-shell-escapeが必要なので下みたいにargsを少し変えた.

"latex-workshop.chktex.enabled": true,
"latex-workshop.latex.recipes": [
    {
    "name": "Report",
    "tools": ["ptex2pdf"],
 }
],
"latex-workshop.latex.tools": [
    {   
        "name": "ptex2pdf",
        "command": "ptex2pdf",
        "args": [
            "-l",
            "-ot",
            "-kanji=utf8 -synctex=1 -file-line-error -shell-escape",
            "%DOC%"
        ]
    }
],
"latex-workshop.view.pdf.viewer": "tab",

ここまでやれば多分環境は整っている気がする.
スクリプトで生成したTeXファイルをVSCodeで開いてCmd+Shift+PからのBuild LaTeX Projectで行けるはず。
めっちゃ詰まっててごちゃごちゃいろいろしたのでなにか足りていないかもしれない.

使い方

Githubの方に書いてる(わかりにくいけど頑張って)
TOMLの流儀しらないから完全自己流の意味わからない設定方法になりましたが...

おわり

僕は必要だったからなんとなく書いたけど多分どこのチームも持ってるんだろうね
ここまでかいてこれ見つけちゃって泣いちゃった、みんなはちゃんと調べてから行動しような
フォントとか普段使ってるやつにしたかったけどLaTeXわからなすぎるな、悲しい
使う人、いなくないか？いなさそう
普通PCK参加した時点でみんなこういうの書くのかもしれないですが、僕は書かずにゴリ押しして1ファイルに付き1PDFファイルみたいなことをしてコンビニで頑張って印刷する悲しい人になっていました
PCK出る人とかも使ってくれると嬉しめ、左上のヘッダ部分にチーム名入れられるし(必要ないね)

2019-05-12

diverta 2019 E - Xor Partitioning

C/C++ プログラミング競技プログラミング

diverta 2019 Programming Contest E - XOR Partitioning

自分の頭が弱くなりすぎていて悲しい，どうにかしていきたい
4完した時点で11位だったのにね，そっからなにもできなかったね
unratedになっていただき助かった

問題概要

N 要素の数列 A が与えられる．
これをいくつかの区間に分けるような $2^{N-1}$ 通りのうち，それぞれの区間のxorが等しくなるようなものはいくつあるか．

解法

数列全体のxorが0でなければその値 X がそれぞれの区間の値になることがわかる．
- この場合は求めるのが簡単．僕は詰めきれなかったけど．
prefixから偶数個の区間のxorを取ると0になる
- prefixのxorが0になるような点で区切れば2つの区間ずつ考えていける
累積xorが0になるような区間の中に x が現れる場合，そこで区切るとそれぞれの区間のxorは x になる

最初に累積xor， B を取っておいて考える.

ここで $dp \lbrack i \rbrack \lbrack x \rbrack := \lbrack 0, i \rbrackをxorがxになる区間に分ける方法$ と置く．
また， $cnt \lbrack i \rbrack \lbrack x \rbrack := B の \lbrack 0, i ) にxが今まで何回登場したか$ も持つ．
$dp \lbrack x \rbrack$ を更新するタイミングは B に0が登場したタイミングだが，ここで毎回行うと $O(NA_{max})$ になってしまうので，次に B の中で $x$ が登場したときに更新するように遅延評価することにする．

$dp \lbrack i \rbrack \lbrack x \rbrack$ の更新の式は3.を利用すると, $dp \lbrack i \rbrack \lbrack x \rbrack = \sum dp_{j} \lbrack j \rbrack \lbrack x \rbrack \times (cnt \lbrack i \rbrack \lbrack x \rbrack - cnt \lbrack j \rbrack \lbrack x \rbrack)$ となることがわかる．
当然これをそのまま行うと遅延評価しようと計算量大爆発になってしまう．
$dp \lbrack i \rbrack = cnt \lbrack i \rbrack \sum dp \lbrack j \rbrack - \sum dp \lbrack j \rbrack \times cnt \lbrack j \rbrack$ と式変形すると，右辺は $cnt \lbrack i \rbrack$ しかiに依存しないので， $dp2 := \sum dp \lbrack j \rbrack$ , $dp3 := \sum dp \lbrack j \rbrack \times cnt \lbrack j \rbrack$ とする.
$dp = cnt \times dp2 - dp3$ となり，それぞれ $dp2 = dp2 + dp$ ， $dp3 = dp3 + dp \times cnt$ と更新することができる．

また, $x$ が現れる前に0が複数回現れているときのことを考える.
0が現れただけこの更新を行うと再び計算量大爆発なので， $O(1)$ で終わらせたい気持ちになる．cntが変化しないことを考慮すると，

$\displaystyle \begin{aligned} dp2' &= dp2 + dp \\ dp3' &= dp3 + dp \times cnt \\ dp' &= cnt \times dp2' - dp3' \\ &= cnt \times (dp2 + dp) - (dp3 + dp \times cnt) \\ &= cnt \times dp2 - dp3 \end{aligned}$

となるので， $dp$ は一回やったときと同じ結果になる． $dp2, dp3$ の変化は，更新した回数(同じ値) $dp$ が足し込まれるので，それまでに処理した0の個数と今の位置までの0の個数を持っとけばその差だけかけた値を足し込めばできる．

実際に解を出力する際には，総xorが0の場合と0以外の場合で分ける．

0のとき

まず遅延評価のうち評価できてない分を評価する．
それぞれの区間のxorが0になるような分け方は，0が B に現れる回数を $K$ としたとき， $2^{K-1}$ になるので別で計算する．
xorが $x$ になるような分け方は， $dp \lbrack N \rbrack \lbrack x \rbrack$ なので，これを答えに足す．

0以外のとき

A の総xorを $x$ とすると， $\sum dp \lbrack i \rbrack \lbrack x \rbrack$ が解になるが，これは既に計算していて $dp2$ なのでこれを出力する．

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int64 N;
    cin >> N;
    vector<int64> A(N);
    REP(i, N) cin >> A[i];
    vector<Mint> dp(1 << 20, 0), dp2(1 << 20, 1), dp3(1 << 20, 0);
    vector<int64> cnt(1 << 20, 0), zok(1 << 20, 0);
    int64 xx = 0;
    int64 zero = 0;

    REP(i, N) {
        xx ^= A[i];
        if (xx == 0) {
            zero++;
        } else {
            if (zok[xx] != zero) {
                dp[xx] = dp2[xx] * cnt[xx] - dp3[xx];
                dp2[xx] += dp[xx] * Mint(zero - zok[xx]);
                dp3[xx] += (dp[xx] * cnt[xx]) * Mint(zero - zok[xx]);
                zok[xx]++;
            }
            zok[xx] = zero;
        }
        cnt[xx]++;
    }

    Mint res = 0;
    if (xx == 0) {
        FOR(i, 1, dp.size()) {
            if (zok[i] != zero) 
                dp[i] = (dp2[i] * cnt[i] - dp3[i]);
            res += dp[i];
        }
        res += Mint(2).pow(zero-1);
        cout << res << endl;
    } else {
        if (zok[xx] != zero) {
            dp[xx] = dp2[xx] * cnt[xx] - dp3[xx];
            dp2[xx] += dp[xx] * Mint(zero - zok[xx]);
            dp3[xx] += (dp[xx] * cnt[xx]) * Mint(zero - zok[xx]);
        }
        cout << dp2[xx] << endl;
    }
}

2019-03-12

AGC 030 F - Permutation and Minimum

競技プログラミングプログラミング C/C++

AGC 030 F - Permutation and Minimum

初めて1600点とかいう高得点の問題をACできたので嬉しくてブログを書く

問題概要

いくつかの要素が欠けている1〜2Nで構成された順列Aが与えられるので，欠けている部分を埋めて順列A'を作る．
${min(A'[2i], A'[2i+1])}$ をB[i]とした数列Bを構成する．
このときBとなる数列は何種類できるか．

解法

なんか解説の解法はめっちゃ簡潔でした，僕の解法は簡潔ではありません(はい)
解説「2N→1の順に見ていきます」
ぼく「1→2Nの順に見ていきます(不穏)」

どう考えてもDPっぽいので，DPとしてどういう情報を持ちたいかを考えます
A[2i]とA[2i+1]をペアにして考えるべきだとわかるので
1. どちらもまだ決まっていないペアの数 2. 片方がaだと決まっていて，今見ている数xよりも大きいようなペアの数 3. 片方がaだと決まっていて，今見ている数xよりも小さいようなペアの数 4. どちらも決まっているペアの数

の4種類の情報がほしいことがわかります
ここで，ペアの総数，既にいくつ決まっているかがわかると4種類のうち，種類1か4の片方，種類2か3の片方が決まっていれば残りもわかるので，2種類だけ持てばいいことがわかります
これはよくある次元を減らすテクなのでここまでは自明です

今回はdp[i][j][k] := 現在iを見ていて，種類1のペアがj個，種類2のペアがk個として考えます．
Nがペアの総数，Mが既に決まっている要素数，種類3の数をk3, 種類4の数をk4とすると， ${k3+2*k4 = M-k，k3+k4 = N-j-k}$ の2式が立つので ${k3 = 2*N-M-2*j-k, k4 = M-N+j}$ となる

そして小さい方から見ていくとき，その数がAの中に含まれているときと含まれていないときを分けて考えます．

Aに含まれていないとき

このとき，iは種類1，種類2，種類3のペアのうちのどれに含めるかの選択肢があります．
ただし，種類3に含めるときは結果となるBに変化が起こらないため足し込むときに係数は1で，それ以外のときはBに影響するので係数はそのペアの数になります
種類1のペアに含めると，次のi+1を見るときのことを考えると種類3が増えますが，dp配列の添字には含まれないので種類1だけ減らします
同様に種類2だと種類4が増えますが種類4は添字にないので種類2だけ減らし，種類3のとき種類3が減って種類4が増えますがどちらもないので何もしません

if (j > 0) dp[i+1][j-1][k] += dp[i][j][k] * j;
if (k > 0) dp[i+1][j][k-1] += dp[i][j][k] * k;
if (k3 > 0) dp[i+1][j][k] += dp[i][j][k];

Aに含まれているとき

iのペアがAで決まっているときは最初から種類4の個数としてカウントされているので添字部分では何も変化しません．

iのペアがAで決まっていないとき，最初は種類2としてカウントされていますが，i-1までの間に種類4になっている可能性があります
つまり，dp[i][j][k]で，k個の中に含まれている場合と既に含まれていない場合があるので，含まれている場合はdp[i+1][j][k-1]に遷移してあげないといけません．

Aで，一方がi以上でもう一方が決まっていないようなペアの数をpとしておくと，p個のうちk個が残っているということになります(新たに増えた一方のみが決まっていないようなペアは種類3でありkにカウントされないので)
iのペアが既に決まっている場合の数は，p個のペアについて均等になっているはずなので，dp[i][j][k] * k / pとなります．
まだ決まっていないときは種類2としてカウントされてた分が種類3になるので種類2が一つ減るように遷移をします
よって遷移は次のようになります

if (k > 0) dp[i+1][j][k-1] += dp[i][j][k] * (p - k) / p;
dp[i+1][j][k] += dp[i][j][k] * k / p;

pは最初に累積和をしておくと簡単に求められます

~~ここまでをやると計算量はそのままO(N³)になります~~
beetさんから指摘されましたがModの割り算をしているのでlog MODがかかり，O(N³ log MOD)です

コードは下のようになりますが，変数名とか無駄な変数とか変なところがたくさんあるので参考にはなりません

int main(void) {
    int N;
    cin >> N;
    vector<int64> A(2*N), sc1(2*N+1, 0);
    vector<bool> used(2*N+1, 0), ispair(2*N+1, 0);
    int cnt[3] = {};
    int luz = 0;
    REP(i, 2*N) {
        cin >> A[i];
        if (A[i] != -1) used[A[i]-1] = 1;
        if (A[i] != -1) luz += 1;
        if (i%2) {
            cnt[(A[i-1] != -1) + (A[i] != -1)]++;
            if ((A[i-1] != -1) + (A[i] != -1) == 1) {
                sc1[max(A[i-1], A[i])]++;
            } else if ((A[i-1] != -1) + (A[i]!=-1) == 2) {
                ispair[A[i-1]-1] = 1;
                ispair[A[i]-1] = 1;
            }
        }
    }
    REP(i, 2*N) sc1[i+1] += sc1[i];
    vector<vector<Mint>> dp(310, vector<Mint>(310, 0));
    dp[cnt[0]][cnt[1]] = Mint(1);
    REP(i, 2*N) {
        vector<vector<Mint>> dp2(310, vector<Mint>(310, 0));
        REP(j, N+1) { // [-, -] のかず
            REP(k, N+1) { // [-, *]かつ*>iの数
                int64 rest = N-j-k;
                int64 latte = luz-N+j; // [*, *]
                int64 beet = 2*N-luz-2*j-k; // [-, *]かつ*<i
                if (j < 0 || k < 0 || rest < 0 || latte < 0 || beet <0) continue;
                if (used[i]) {
                    if (ispair[i]) {
                        dp2[j][k] += dp[j][k];
                    } else {
                        Mint exist_posi = Mint(k)/Mint(sc1[2*N]-sc1[i]), inv_posi = Mint(sc1[2*N]-sc1[i]-k)/Mint(sc1[2*N]-sc1[i]);
                        if (k > 0)
                            dp2[j][k-1] += dp[j][k] * exist_posi;
                        dp2[j][k] += dp[j][k] * inv_posi;
                    }
                } else {
                    if (j > 0)
                        dp2[j-1][k] += dp[j][k] * j;
                    if (k > 0)
                        dp2[j][k-1] += dp[j][k] * k;
                    if (beet > 0)
                        dp2[j][k] += dp[j][k];
                }
            }
        }
        if (!used[i]) luz++;
        swap(dp, dp2);
    }
    cout << dp[0][0] << endl;
}

2019-02-10

戻すDPわからない

はてなでの数式の扱い良くわからなくて意味わからないことになっている

戻すDPわからない

随分前から名前を見てたものの学ぼうとしてなかった
コドフォに出たことでTLでめっちゃ見えたので流石にやろうと思ったら理解に苦しんだので自分のためだけにブログを書く
実際には深く理解してないので意味のわからないことしか書けないけど

yukicoderのこれを見て理解できる人はすごいと思う．これが理解できるような人になりたい人生だった．

概要

DPで数え上げをするときに特定の要素を特別扱いしたくなることがある
そのとき，要素の順番を変えてもDPの結果が同じになるような場合ではその要素がなかったときの結果が求められる
これは例えばdp[i][j] := i番目まで見てi-1番目がj個残ってるときみたいな定義になるとダメ，多分(自信がない)
この場合でも当然，N個目を取り除いた場合が知りたければN-1個目までしか処理しなければ求められるけど，戻すDPが適用できる場合はそれが何個目の要素のときでもできるよというのが本質

戻すDPが適用できる条件は次の2つ
1. 要素の順番が数え上げに関係しない
2. DPの漸化式を式変形することでdp[i] = dp[i+1] * ... + ...みたいな雰囲気ができる

このとき，2.ができるためには情報が消えてはいけないので遷移に場合分けがあったらダメ

3問戻すDPを使う問題を解いたのでそのときの気持ちと解法を下に書く

注文の多い高橋商店

とりあえず簡単すぎると言われている方が解けないことには話にならないので解く．
僕ぐらいになるとここで詰まってしまうから悲しい
単純に考えるとDPの遷移は ${dp_{i, j} = i種類目まで見てj個選んでいるときの通り数}$ として一行目のようになっている
このままだと計算量大爆発( ${O(NM^2)}$ ぐらい)なため，累積和を使うことで削減できるがめんどくさい
ここで ${j-1}$ で計算したものが二行目のようになっていることを考えると引いて式変形することで三行目のような遷移になり単純になる
このとき，漸化式は左辺に ${dp_{i+1, j}}$ が来るようなもらう形になってるとなんか戻しやすい気がする．そんな関係ないかも

${\displaystyle dp_{i+1, j} = \sum_{k=0}^{a_i} dp_{i,j-k} \\ dp_{i+1, j-1} = \sum_{k=0}^{a_i} dp_{i,j-k-1} \\ dp_{i+1, j} - dp_{i+1, j-1} = \sum_{k=0}^{a_i} dp_{i,j-k} - \sum_{k=0}^{a_i} dp_{i,j-k-1} \\ \Leftrightarrow dp_{i+1, j} = dp_{i, j} - dp_{i, j-a_i-1} + dp_{i+1, j-1} }$

よって普通にDPができたので，これを戻せれば勝ち
ちなみに添字が0未満になるところは0として考える．これは場合分けになるから戻せなくなるのでは？みたいな気持ちになるけど0未満になる場合はありえなくて実際0通りなので問題ない．
僕はget(dp, i, j)みたいな感じで呼んだらどっちか0未満なら0を返すみたいなのを用意した

戻した結果として ${dp2_{i, j} = i種類目を使わないでj個選ぶ通り数}$ となるdp2を求める
ここで漸化式を式変形して左辺に ${dp_{i, j}}$ が来るようにすると ${dp_{i, j} = dp_{i+1, j} - dp_{i+1, j-1} + dp_{i, j-a_i-1}}$ となる．
なので，i番目を戻したい(除いた場合を考えたい)ときに行う遷移は ${dp2_{i, j} = dp_{N, j} - dp_{N, j-1} + dp2_{i, j-a_i-1}}$ となり，右辺で ${dp2}$ を参照するときの添字を考えて ${j}$ が小さい方から回すことになる．
${dp2}$ が求まったので，クエリの ${k_i}$ 種類目をちょうど ${x_i}$ 個使う時というのは ${k_i}$ 種類目を使わないで ${M-x_i}$ 個選ぶのと同じであることから答えは ${dp2_{k_i, M-x_i}}$ となる．
コードは下のやつなんですが，この問題だけModIntを使っていない

int main(void){
    for (auto& x : dp) for (auto& y : x) y = 0;
    for (auto& x : dp2) for (auto& y : x) y = 0;
    cin >> N >> M >> Q;
    a.resize(N);
    for (auto& x : a) cin >> x;
    dp[0][0] = 1;
 
    REP(i, N){
        REP(j, M+1){
            dp[i+1][j] = (get(dp, i+1, j-1) - get(dp, i, j-a[i]-1) + get(dp, i, j))%mod;
        }
    }
    REP(i, N){
        REP(j, M+1){
            dp2[i][j] = (get(dp, N, j) - get(dp, N, j-1) + get(dp2, i, j-a[i]-1))%mod;
            dp2[i][j] = (dp2[i][j] % mod + mod) %mod;
        }
    }
    while(Q--){
        int64 k, x;
        scanf("%lld %lld", &k, &x); k--;
        printf("%lld\n", dp2[k][M-x]);
    }
}

生放送とBGM

これは戻すDPなのかなあとなるけど戻すDPのところで紹介されてたので戻すDPだと思いながら考える(最悪)
特定の曲に注目して考えることになるので考えると，ある曲が再生されるときの通り数を全ての曲に対して求め足し合わせると答えになることがわかる

特定の曲が再生されるかどうかはその曲が再生され始める時間が ${L-1}$ 以下なら良いので ${dp_{i} = 曲の合計時間がiとなるような通り数}$ にして，戻した後に ${\sum_{k=0}^{L-1} dp_{k}}$ を求めれば良さそうとなる
しかしこの問題では全部の順列に対して求める必要があるので，時間が ${k}$ になる組み合わせではなく順列が知りたい．更に特定の曲の後に流れる予定の部分についても順番が区別されるため，この両方を求めるために特定の曲までに何曲流したのかも欲しい．

なので ${dp_{i, j} = i曲流した合計時間がj}$ としてDPを行う．
これを戻すと ${dp2_{k, i, j} = k曲目を除いてi曲流したときの合計時間がj}$ という配列が手に入るため，答えは ${\sum_{k=0}^{N} \sum_{i=0}^{N-1} \sum_{j=0}^{L-1} dp2_{k, i, j} \times i! \times (N-i-1)!}$ を求めた後に期待値なので ${N!}$ で割ればいい
僕は初心者なのでmodの問題でもないのにどうやってそんな大きい階乗をとれば...と思ってたけどdoubleでやれば大丈夫だった(それはそう)

肝心のDPの遷移と戻し方だが，普通のDPは ${dp'_{i, j} = dp_{i, j} + dp_{i-1, j-S_i}}$ でできる．
このときに配るDPをやろうとして，更に時間の合計がL以上になる部分はまとめていいだろ〜みたいな気持ちになり ${dp'_{i+1, min(L, j+S_i)} = dp_{i+1, min(L, j+S_I)} + dp_{i, j}}$ とかやると， ${min}$ が実質的に場合分けになっているので戻せなくなる．この場合は戻すときに ${dp_{N, L}}$ にどこから足されたかがわからなくなってしまうため
どちらの場合でも，この問題では一回戻すため一回戻せるだけの余裕をもたせる必要がある．

一曲の時間の最大値を ${S_{max}}$ とおくと配るDPなら ${min}$ のとり方を ${min(L+S_{max}, j+S_i)}$ にすれば良くて(普通のDPをする際には ${j}$ を ${L-1}$ までしか回す必要がないので配列を十分にとっておけばminを取らなくてもいい)
もらうDPなら ${j}$ を ${L+S_{max}}$ まで回せばいい

このとき，戻すDPの遷移は ${dp2_{k, i, j} = dp_{N, j} - dp2_{k, i-1, j-S_k}}$ でできる
今回も ${j}$ が小さい方から回すことになる

コード,initでfactを初期化している．
さっきのもそうだったけどdpの添字や配列名があってないのは空間計算量削減とかあるので許してください．

int main(void){
    init();
    cin >> N >> L;
    L *= 60;
    S.resize(N);
    REP(i, N){
        int64 m, s;
        scanf("%d:%d", &m, &s);
        S[i] = m*60+s;
    }
    vector<vector<int64>> dp(N+1, vector<int64>(L+60*60+1, 0));
    dp[0][0] = 1;
    REP(i, N){
        vector<vector<int64>> dp2(N+1, vector<int64>(L+60*60+1, 0));
        REP(j, N+1){
            REP(k, L+60*60+1){
                dp2[j][k] = get(dp, j-1, k-S[i]) + get(dp, j, k);
            }
        }
        swap(dp, dp2);
    }
    double res = 0;
    REP(i, N){
        vector<vector<int64>> dp2(N+1, vector<int64>(L+60*60+1, 0));
        REP(j, N+1){
            REP(k, L+60*60+1){
                dp2[j][k] = dp[j][k] - get(dp2, j-1, k-S[i]);
                if (k < L && N-j-1 >= 0)
                    res += dp2[j][k] * fact[j] * fact[N-j-1] / fact[N];
            }
        }
    }
    cout << fixed << setprecision(10) << res << endl;
}

Destroy the Colony

問題概要

僕が読解に苦しんだのでこれだけ問題概要
偶数長の英文字(大小)からなる文字列 ${S}$ が与えられる
これの並び替えのうち，文字列を前後半に分けた時に同じ文字が同じ側にある並び替えは嬉しい(Destroy the Colonyできる)
このとき次のクエリが与えられるので処理しなさい

${S_x}$ と ${S_y}$ が同じ側になるような並び替えは何通りあるか出力せよ

${S_x}$ と ${S_y}$ が同じなら普通に全部の嬉しい並び替えを答えればいいみたいな感じ
クエリの種類が実質 ${52^2}$ 種類しかない( ${S_x}$ と ${S_y}$ が逆でも答え一緒なので実際は半分強)ので先に計算しておけば勝ち

明らかに特別扱いしたいものがあるので戻すDPだなとなるが，2つあるので当然2回戻す

答えの求め方が僕の考えたTLEするやつと解説の方法がある．
解説のほうが明らかに明快(僕には難しくて難解だった)なのでそっちを先に書いて，僕の考えたやつは最後に書く(読みたい人は読んでって感じ)

解説解

それぞれの文字種がいくつ現れるかを ${c_i}$ とする. この時， ${|S|/2}$ 個ずつになるように分ける組み合わせがわかれば，そのときの組み合わせを ${x}$ とすると，前半と後半それぞれについて重複順列を求めてかけ合わせたものに ${x}$ をかければいいので下のようになる

${\displaystyle ans = \frac{x \times (|S|/2)! \times (|S|/2)!}{\prod_{i=0}^{51} c_i!} }$

${x}$ 以外の部分はどういう分け方でも共通なのであらかじめ計算しておく
じゃあ ${x}$ を求めればいいねとなり，これは上の二問よりも簡単では？みたいな気持ちになる
ここで ${dp_{i, j} = i番目まで見て前半にj個あるときの分け方の通り数}$ とすると ${dp_{i+1, j} = dp_{i, j} + dp_{i, j-c_i}}$ となる．
これを戻す形にすると ${dp_{i, j} = dp_{i+1, j} - dp_{i, j-c_i}}$ になる
${j}$ の範囲としては，2回戻す分必要かつそれぞれの文字種の個数が決まってないので ${|S|}$ まで回す必要がある？(ないかも)

文字種 ${a}$ で一回戻したときを ${dp1}$ ，文字種 ${b}$ で更に戻したときを ${dp2}$ とすると， ${dp1_{i} = dp_{N, i} - dp1_{i-c_a}}$ で ${dp1}$ がわかり，全く同じことをして ${dp2_{i} = dp1_{i} - dp2_{i-c_b}}$ で ${dp2}$ が求まる
${a=b}$ なら ${x = dp1_{|S|/2} = dp1_{|S|/2-c_a}}$ , そうでなければ ${x = dp2_{|S|/2} = dp2_{|S|/2-c_a-c_b}}$ となる
各 ${a}$ について ${dp1}$ を求め，それを用いて各 ${b}$ について ${dp2}$ を求めればいいので，計算量は使用されている文字の種類数を ${C}$ とすると ${O(C|S| + C^2|S|)}$ となり， ${O(C^2|S|)}$ である．
戻すときの処理が全く同じなのでそこを関数化すると簡単にかけるらしい

コード，僕はそれをしていない
MintがModIntで，fというのはFactorialライブラリ，f.comb(a, b)で ${_aC_b}$ を返す．
めっちゃコードが長くて何が起こってるかわからないね
これが1970msぐらい

int main(void){
    vector<int64> c(52, 0);
    cin >> s >> q;
    n = s.size();
    REP(i, s.size()) c[ctoi(s[i])]++;

    Mint W = f[n/2]*f[n/2];
    REP(i, 52) W /= f[c[i]];

    vector<Mint> dp(n+1, 0);
    dp[0] = 1;
    REP(i, 52){
        if (c[i] == 0) continue;
        vector<Mint> dp2(n+1, 0);
        REP(j, n+1){
            dp2[j] = get(dp, j-c[i]) + get(dp, j);
        }
        swap(dp, dp2);
    }
    vector<vector<Mint>> ans(52, vector<Mint>(52, 0));
    REP(i, 52){
        if (c[i] == 0) continue;
        vector<Mint> t1(n+1, 0);
        REP(j, n+1){
            t1[j] = get(dp, j) - get(t1, j-c[i]);
        }
        REP(j, 52){
            if (c[j] == 0) continue;
            if (i == j) {
                ans[i][j] = t1[n/2];
                continue;
            }
            vector<Mint> t2(n+1, 0);
            REP(k, n+1) {
                t2[k] = get(t1, k) - get(t2, k-c[j]);
            }
            ans[i][j] = t2[n/2];
        }
    }
    while(q--){
        int32 x, y;
        scanf("%d%d", &x, &y); x--; y--;
        x = ctoi(s[x]); y = ctoi(s[y]);
        cout << ans[x][y] * W * 2 << endl;
    }
}

僕の解法

DPは万能なので，DPで組み合わせだけ求めてそれに並び替えをかけなくても最初から並び替えた後を求められるじゃ～んみたいな気持ちになっていた
つまり， ${dp_{i, j} = i種類目まで見て前半にj個あるときの前半後半含めて並べ方}$ をした．
ここで，既に ${i}$ 個あるところにこれを並び替えず同じ種類のものを ${j}$ 個追加したときの並べ方は，ある種類のもの ${i}$ 個と別の種類のもの ${j}$ 個の並べ方と同じなので ${\frac{(i+j)!}{i!j!} = _{i+j}C_{j}}$ となる．

${sum_i = \sum_{k = 0}^{i-1} c_i}$ とする
前半に ${i}$ 種類目を追加するか後半に追加するかの二通りの遷移があるので合わせて ${dp_{i+1, j} = dp_{i, j-c_i} \times _jC_{c_i} + dp_{i, j} \times _{sum_i-j+c_i}C_{c_i}}$ となる
これを戻す形にすると下のような形になる．
戻す文字種を先ほどと同じように ${a, b}$ とすると，文字種を並び替えて一番後ろから ${a, b}$ にして，分母の ${sum_i-j+c_i}$ が一回目は ${sum_a+c_a = N}$ であることから ${N-j}$ ，二回目は ${sum_b+c_b = sum_a-c_b + c_b = N-c_a}$ となる．
こっちが最初に書いたやつなので答えの部分がすこしごちゃごちゃしてます.

${\displaystyle dp_{i, j} = \frac{dp_{i+1, j} - dp_{i, j-c_i} \times _jC_{c_i}}{_{sum_i-j+c_i}C_{c_i}} }$

二回戻した後， ${dp_{|S|/2}}$ が求まったら取り除いている分を追加したときの並び替えを答えないといけないので， ${dp_{|S|/2} \times _{|S|/2-c_a}C_{c_b} \times _{|S|/2}C_{c_a}}$ が答えになります
後は組み合わせが0になってゼロ割してしまわないように気をつけて下のコードのようになります
さっきのが1970msぐらいなので，遷移が定数倍重くなってるこっちは当然TLEします．
お疲れ様でした，多分test9までは通ってるので解法としてはあっているはず

int main(void){
    cin.tie(0);
    ios::sync\_with\_stdio(false);
    vector<int64> c(52, 0), sum(53, 0);
    cin >> s >> q;
    n = s.size();
    REP(i, s.size()) c[ctoi(s[i])]++;
    REP(i, 52) sum[i+1] += sum[i] + c[i];

    vector<Mint> dp(n+1, 0);
    dp[0] = 1;
    REP(i, 52){
        if (c[i] == 0) continue;
        vector<Mint> dp2(n+1, 0);
        REP(j, n+1){
            dp2[j] = dp[j] * f.comb(sum[i]-j+c[i], c[i]) + get(dp, j-c[i]) * f.comb(j, c[i]);
        }
        swap(dp, dp2);
    }
    vector<vector<Mint>> res(52, vector<Mint>(52, 0));
    vector<Mint> t1(n+1, 0);
    vector<Mint> t2(n+1, 0);
    REP(i, 52){
        if (c[i] == 0) continue;
        REP(j, n+1) {
            if (n-j >= c[i]) {
                t1[j] = (get(dp, j) - get(t1, j-c[i]) * f.comb(j, c[i])) / f.comb(n-j, c[i]);
            }
        }
        FOR(j, i, 52){
            if (c[j] == 0) continue;
            if (i == j) {
                res[i][j] = t1[n/2] * f.comb(n/2, c[i]) * 2;
                continue;
            }
            REP(k, n+1){
                if (n-c[i]-k >= c[j]) {
                    t2[k] = (get(t1, k) - get(t2, k-c[j]) * f.comb(k, c[j])) / f.comb(n-c[i]-k, c[j]);
                }
            }
            if (c[i]+c[j] <= n/2)
                res[i][j] = res[j][i] = t2[n/2] * f.comb(n/2-c[i], c[j]) * f.comb(n/2, c[i]) * 2;
        }
    }
    while(q--) {
        int64 x, y;
        cin >> x >> y; x--; y--;
        x = ctoi(s[x]); y = ctoi(s[y]);
        if (x == y) {
            cout << res[x][y] << endl;
        } else if (c[x] + c[y] > n/2) {
            cout << 0 << endl;
        } else {
            cout << res[x][y]  << endl;
        }
    }
}