与えられた操作を「わかりやすいものに読み替える」というのが本質な問題だと思う。AtCoder でもよく見られるタイプの

問題概要

$1, 2, \dots, N$ の書かれた $N$ 枚のカードを順に並べたものに対し

左から偶数番目のみを順に取り出して並べたものを A
右から偶数番目のみを順に取り出して並べたものを B

として、AB の順に左から並べるか、BA の順に左から並べるかのいずれかの操作を行う。

このような操作を $Q$ 回行って作られうる順列をすべて考えた時、 $K$ と書かれたカードが左から $D$ 番目に来ることがありうるかどうかを判定せよ。

制約

$N$ は偶数
$N \le 10^{15}$
$Q \le 10^{6}$

考えたこと

順列に関する問題に思えるが、実は順列の問題ではない！！！

このような「配列全体に対する操作を何回か行う」という問題では、しばしば

個別の要素がどのように動いていくか

に着目すると良いイメージがある。かなりの確率でその方向性の考察によって物事が見えて来る印象。

さて、今回まさにその考察をすると見えて来る。実はこの操作は、左から $x$ 番目 (0-indexed) にあるカードを

$x/2$ 番目 (小数点切り捨て)
$x/2 + \frac{n}{2}$ 番目

のいずれかに移動させる操作だと思うことができる。よって問題は、

整数 $x$ を $x/2$ か $x/2 + \frac{n}{2}$ のいずれかに変更する操作があって、 $K$ からスタートして $Q$ 回行うことで $D$ にすることができるかどうかを判定せよ

ということになる。このままでもまだよくわからない。この操作をさらに読み替える！！！！！！
操作を逆順に見るとなんと

整数 $x$ を $2x$ % $n$ か $(2x + 1)$ % $n$ のいずれかに更新する操作

をなっている！！！！！！！
% $n$ の違いはあとでまとめて吸収してしまえばいいので、実質的に

$x$ をビット列とみて左にビットシフト
$x$ をビット列とみて左にビットシフトして 1 を足す

のいずれかの操作であると読み替えることができる。よって問題は、

$D$ を $Q$ 回左にビットシフトして (それを $D'$ とする)、下位 $Q$ 桁に 0 か 1 を任意に立てたものが、 ${\rm mod}. N$ で $K$ と一致させることができるかどうか判定せよ

ということになる。少し考えてみると

$diff = K - D' ({\rm mod}. N)$ の最高位の $1$ が右から $Q-1$ 桁目以内にあるかどうかが、実現可能かどうかの必要十分条件

ということがわかる。同時に逆順での操作順も求めることができて、こんな感じにできる:

    vector<long long> tmp;
    while (diff) {
        tmp.push_back(diff & 1);
        diff >>= 1;
    }
    if (tmp.size() > Q) { cout << -1 << endl; return; }
    while (tmp.size() < Q) tmp.push_back(0);
    reverse(tmp.begin(), tmp.end());

tmp が逆順で

0: $x$ を $2x$ にする
1: $x$ を $2x + 1$ にする

と操作を対応させて、 $D$ から $K$ へ遷移させる解になっている。

操作を前から順で見ると...

ただし以上の操作を前から順に見るときには注意が必要になる。 $x$ を $2x$ にするのと $2x+1$ にするのは、操作を通常順で見たときにピッタリ「0」と「1」に対応するわけではない。。。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using pint = pair<int,int>;

long long N, Q, K, D;
void solve() {
    --K, --D;
    long long pK = K, pD = D;
    for (int i = 0; i < Q; ++i) D = D * 2 % N;
    long long diff = (K - D + N) % N;

    // tmp: 逆順で見たときの 0: 2x、1: 2x+1
    vector<long long> tmp;
    while (diff) {
        tmp.push_back(diff & 1);
        diff >>= 1;
    }
    if (tmp.size() > Q) { cout << -1 << endl; return; }
    while (tmp.size() < Q) tmp.push_back(0);
    reverse(tmp.begin(), tmp.end());

    // 実際の操作に適合した復元
    vector<long long> res;
    for (int q = 0; q < tmp.size(); ++q) {
        long long nD = pD * 2;
        if (tmp[q]) ++nD;
        nD %= N;

        // nD -> pD が実際には 0 なのか 1 なのかを判定
        if (nD % 2 == 0) {
            if (pD == nD/2) res.push_back(0);
            else res.push_back(1);
        }
        else {
            if (pD == nD/2) res.push_back(1);
            else res.push_back(0);
        }
        pD = nD;
    }
    reverse(res.begin(), res.end());
    for (int i = 0; i < Q; ++i) cout << res[i] << endl;
}

int main() {
    cin >> N >> Q >> K >> D;
    solve();
}