C - Tautonym Puzzle

[AGC 012 C] Tautonym Puzzle

题面翻译

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

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

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

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

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

输入格式

$N$

• $1\le N\le {10}^{12}$

输出格式

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

样例 #1

样例输入 #1

7

样例输出 #1

4
1 1 1 1

样例 #2

样例输入 #2

299

样例输出 #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$)