[AGC 012 C] Tautonym Puzzle

题面翻译

我们称一个字符串 \(x\) 是好的当且仅当它满足以下条件：

\(x\) 可以被表示为另外一个串 \(y\) 复制一遍得到，即 \(x=\overline {yy}\)。

举个例子：aa 和 bubobubo 是好的，a、abcabcabc 和 abba 不是。

现在要求一个串 \(s\) 满足下列条件，可以证明这个串存在：

\(|s|\leqslant 200\)
字符集大小为 \(100\)，每个字符用 \([1,100]\) 的整数表示。
在 \(s\) 的所有的 \(2^{|s|}\) 个子序列中，恰好有 \(N\)（\(1 \le N \le 10 ^ {12}\)）个串是好的，其中 \(N\) 是给出的。

输入格式

\(N\)

\(1\ \leq\ N\ \leq\ 10^{12}\)

输出格式

第一行，打印 \(|s|\)，即 \(s\) 的长度。第二行，依次打印 \(s\) 中的元素，中间留空格。任何满足上述条件的字符串都将被接受。

样例 #1

样例输入 #1

样例输出 #1

1
2

4
1 1 1 1

样例 #2

样例输入 #2

样例输出 #2

1 2	23 32 11 11 73 45 8 11 83 83 8 45 32 32 10 100 73 32 83 45 73 32 11 10

Solution

和1922(Edu161div2) E 类似，需要开 ll ？

#define int long long
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, t = 0;
    vector<int> ans;
    cin >> n;
    int x = n;
    for (int i = 1; i <= 100; i++)
        ans.push_back(i);
    while (x >= pow(2, t + 1) - 1ll)
        t++;
    for (int i = 1; i <= t; i++)
        ans.push_back(2 * i);
    n = n - pow(2, t) + 1ll;
    for (int i = t; i >= 1; i--)
        if (n & (1ll << (i - 1)))//(n >> (i - 1)) & 1)
            ans.push_back(2 * i - 1);
            
    cout << ans.size() << endl;
    for (auto x : ans)
        cout << x << " ";
}

signed main()
{
    vector<int> s, t;
    cin >> n;
    int p = 101;
    n++;
    while (n > 1)
    {
        if (n & 1)
            t.push_back(--p), n--;
        else
            s.push_back(--p), n >>= 1;
    }
    cout << ((s.size() + t.size()) << 1) << '\n';
    for (int i = 0; i < (int)t.size(); i++)
        cout << t[i] << " ";
    for (int i = s.size() - 1; ~i; i--)
        cout << s[i] << " ";
    for (int i = 100 - (s.size() + t.size()) + 1; i <= 100; i++)
        cout << i << " ";
}

洛谷还有挺多想法的 (可惜看不懂 \(\dots\))

有了思路，如果用我自己的方法做呢？(待更 \(\dots\))

FXJFXJ

012C