結果

問題 No.2995 The Ruler Sequence Concatenation
ユーザー 👑 Nachia
提出日時 2024-12-19 02:07:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 3,326 bytes
コンパイル時間 1,459 ms
コンパイル使用メモリ 92,284 KB
最終ジャッジ日時 2025-02-26 15:38:08
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using i64 = long long;
using namespace std;
#include <atcoder/modint>
using Modint = atcoder::static_modint<998244353>;
using Modint2 = atcoder::static_modint<998244352>;
// a**2**x
Modint powpow2(
    Modint a,
    i64 x
){
    if(a.val() == 0) return 1;
    i64 idx = (Modint2(2).pow(x) - 1).val();
    return a.pow(idx) * a;
}
// (a**2**x - 1) / (a - 1)
Modint geometric(
    Modint a,
    i64 x
){
    if(a.val() == 0) return 1;
    if(a.val() == 1) return Modint(2).pow(x);
    return (powpow2(a,x) - 1) / (a - 1);
}
// freq count a**2**k ( 0 <= k < n )
vector<pair<Modint, i64>> counter(Modint a, i64 n){
    vector<Modint> f;
    f.push_back(a);
    i64 cybeg = -1;
    for(i64 t=1; t<n; t++){
        Modint nx = f.back() * f.back();
        for(i64 q=0; q<(i64)f.size(); q++){
            if(nx.val() == f[q].val()){
                cybeg = q;
                break;
            }
        }
        if(cybeg == -1){
            f.push_back(nx);
        } else {
            break;
        }
    }
    vector<pair<Modint, i64>> res;
    for(i64 i=0; i<(i64)f.size(); i++){
        res.push_back({ f[i], 1 });
    }
    if(cybeg != -1){
        i64 n2 = n - f.size();
        i64 cylen = f.size() - cybeg;
        for(i64 k=0; k<cylen; k++){
            res[cybeg+k].second += (n2 + cylen - 1 - k) / cylen;
        }
    }
    sort(res.begin(), res.end(),
        [](auto l, auto r){ return l.first.val() < r.first.val(); });
    return res;
}
pair<Modint, Modint> sub2(
    i64 len,
    Modint n,
    Modint interval
){
    if(len == 1){
        return { n, interval };
    }
    n -= 1;
    auto base = counter(interval, len);
    Modint ans = geometric(interval, len) * n;
    Modint ointerval = powpow2(interval, len);
    Modint t = powpow2(interval, len) - 1;
    for(auto [u,v] : base){
        if(u.val() != 1){
            ans += t / (u - 1) * v;
        } else {
            ans += ointerval * v;
        }
    }
    ans -= n;
    ans -= len;
    ans /= interval;
    ointerval /= interval;
    return { ans, ointerval };
}
pair<Modint, Modint> sub(
    i64 len,
    Modint n,
    Modint val,
    Modint interval1,
    Modint interval2
){
    auto [u,v] = sub2(len, val * interval2 + n, interval1 * interval2);
    return { u * interval1 + val, v * interval1 };
}
Modint naive(
    i64 n
){
    Modint ans = 0;
    Modint k = 1;
    for(i64 i=1; i<=n; i++){
        i64 len = to_string(i).size();
        Modint j = Modint(10).pow(len);
        ans = ans * j * k + Modint(i) * k + ans;
        k = k * j * k;
    }
    return ans;
}
void testcase(){
    i64 n; cin >> n;
    i64 dig = 1;
    i64 m = 1;
    while(m <= n/10){
        dig += 1;
        m *= 10;
    }
    vector<pair<i64, pair<i64,i64>>> A;
    for(i64 k=1; k<dig; k++){
        i64 f = 1;
        for(i64 i=1; i<k; i++) f *= 10;
        A.push_back({ k, { f, f * 10 - 1 } });
    }
    A.push_back({ dig, { m, n } });
    Modint ans = 0;
    Modint interval = 1;
    for(auto [d, lr] : A){
        auto [l,r] = lr;
        auto [u,v] = sub(r-l+1, l, ans, interval, Modint(10).pow(d));
        ans = u;
        interval = v;
    }
    cout << ans.val() << '\n';
}
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    testcase();
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0