AOJ 3211 Symmetric Nbase Number (OUPC 2020 C)

初手実験に走れたのは割とよかった。そういう戦い方もできるようになってきた。

• 問題へのリンク
• editorial

問題概要

正の整数 を 先頭に 0 を含まないように 進数表現したときの各位の数を、小さい位から順に要素とした数列を とする。次のような感じ。

• 
• 

正の整数 が与えられる。, を満たす整数組 であって、

を満たすものの個数を 998244353 で割ったあまりを求めよ。

制約

• 
• 

考えたこと

まずは という条件をわかりやすく言い換えることが急務となる。実験によって、次のことがわかった。

---

を 進法で表したときに、

• 桁数が奇数である
• 偶数桁目の値がすべて 0 である

という条件を満たすことが必要十分である。

---

たとえば、 などは条件を満たす。ちゃんとした証明は editorial を参照。

ningenme.hatenablog.com

あとは を固定したときに、 を素早く数え上げられれば OK。桁 DP だったり、その他いろんな方法が考えられそう。ここでは、

• 以下の整数のうち、条件を満たす最大の整数を 進法で求めて
• それを偶数番目を除去したものを 10 進法に直す

という方法でやってみた。

コード

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
int main() {
    long long A, B;
    cin >> A >> B;
    long long res = 0;

    auto solve = [&](long long b) -> long long {
        vector<long long> vec;
        long long A2 = A;
        while (A2) vec.push_back(A2 % b), A2 /= b;
        reverse(vec.begin(), vec.end());

        if (vec.size() % 2 == 0) {
            vec.pop_back();
            for (int i = 0; i < vec.size(); ++i) {
                if (i % 2 == 0) vec[i] = b-1;
                else vec[i] = 0;
            }
        } else {
            bool change = false;
            for (int i = 0; i < vec.size(); ++i) {
                if (i % 2 == 1) {
                    if (vec[i] != 0) {
                        change = true;
                        vec[i] = 0;
                    }
                }
                else if (change) vec[i] = b-1;
            }
        }

        long long res = 0;
        for (int i = 0; i < vec.size(); ++i) {
            if (i % 2 == 1) continue;
            res = (res * b) + vec[i];
        }
        return res;
    };
        
    for (long long b = 2; b <= B; ++b) res = (res + solve(b)) % MOD;
    cout << res << endl;      
}