제출 #965061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
965061		roadtoimo	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	552 KiB

numbers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll M = 1e9 + 7;
const int MAXN = 1e5 + 5;
const int MAXZ = 1e5 + 5;
const ll INF = 1e18 + 5;
const int MOD = 998244353;
vector<ll> num;
int k, s;
ll a, b;
ll dp[20][12][12][2][2];
ll inv[20], p[20];

ll bin(ll x, ll m) {
    if (m == 0) return 1;
    ll u = bin(x, m / 2);
    u = (u * u) % MOD;
    if (m & 1) u = (u * x) % MOD;
    return u;
}

ll ans(int i, int prev, int second_prev, bool tight, bool leading) {
    if (i == num.size()) return 1;

    ll& ret = dp[i][prev][second_prev][tight][leading];

    if (ret != -1) return ret;

    ret = 0;
    ll next = num[i];
    if (tight) {
        for (int d = 0; d <= next; ++d) {
            bool is_leading = (d == 0 && leading);
            int new_prev = is_leading ? 11: d, new_second_prev = is_leading ? 11: prev;
            if (d == prev) continue;
            if (d == second_prev) continue;
            ret += ans(i + 1, new_prev, new_second_prev, d == next, is_leading);
        }
    } else {
        for (int d = 0; d <= 9; ++d) {
            bool is_leading = leading && (d == 0);
            int new_prev = is_leading ? 11: d, new_second_prev = is_leading ? 11: prev;
            if (d == prev) continue;
            if (d == second_prev) continue;
            ret += ans(i + 1, new_prev, new_second_prev, false, is_leading);
        }
    }
    return ret;
}

ll solve(ll x) {
    num.clear();
    while(x) {
        num.push_back(x % 10);
        x /= 10;
    }
    reverse(num.begin(), num.end());
    memset(dp, -1, sizeof dp);
    s = num.size();
    ll r = ans(0, 11, 11, true, true);
    return r;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

//    freopen("time.in", "r", stdin);
//    freopen("time.out", "w", stdout);

    cin >> a >> b;
    cout << solve(b) - solve(a - 1);

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

numbers.cpp: In function 'll ans(int, int, int, bool, bool)':
numbers.cpp:27:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if (i == num.size()) return 1;
      |         ~~^~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75