oj.uz

답안 #965061

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
965061 2024-04-18T04:49:28 Z roadtoimo Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 1 ms 552 KB 
#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;
}

Compilation message

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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 344 KB Output is correct

Subtask #2
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 464 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 552 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 460 KB Output is correct
32 Correct 1 ms 548 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 344 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 1 ms 464 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct