QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#19256#1377. Liczba PotyczkowaElegia10 ✓1259ms23896kbC++173.5kb2022-01-28 17:08:292022-05-06 04:32:03

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 04:32:03]
  • Judged
  • Verdict: 10
  • Time: 1259ms
  • Memory: 23896kb
Show
  • [2022-01-28 17:08:29]
  • Submitted

answer

/*
_/_/_/_/    _/_/_/_/_/  _/_/_/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/  _/  _/
_/      _/  _/  _/    _/    _/_/
_/_/_/_/      _/_/     _/_/_/_/_/

_/_/_/_/    _/    _/  _/      _/
_/      _/   _/  _/   _/_/  _/_/
_/      _/    _/_/    _/ _/_/ _/
_/      _/     _/     _/  _/  _/
_/      _/    _/_/    _/      _/
_/      _/   _/  _/   _/      _/
_/_/_/_/    _/    _/  _/      _/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/
*/
#include <cassert>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &x : v)
    is >> x;
  return is;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int lcm(int a, int b) { return a / gcd(a, b) * b; }

const int U = 1 << 9, L = 2520;

int lt[U];
ll dp[U][L], tmp[U][L];
int d[20];

ll solve(ll n) {
  int k = 0;
  while (n) {
    d[k++] = n % 10;
    n /= 10;
  }
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  ll ret = 0;
  auto contribute = [&]() {
    memcpy(tmp, dp, sizeof(tmp));
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i != U; ++i)
      for (int j = 0; j != L; ++j)
        for (int x = 1; x <= 9; ++x)
          dp[i | (1 << (x - 1))][(j * 10 + x) % L] += tmp[i][j];
  };
  auto getAns = [&]() {
    ll res = 0;
    for (int i = 0; i != U; ++i)
      for (int j = 0; j != L; j += lt[i])
        res += dp[i][j];
    return res;
  };
  for (int rep = 1; rep < k; ++rep) {
    contribute();
    ret += getAns();
  }
  memset(dp, 0, sizeof(dp));
  int mask = 0;
  for (int i = k - 1; i >= 0; --i) {
    contribute();
    if (mask != -1)
      for (int j = 1; j < d[i]; ++j) {
        int nask = mask | (1 << (j - 1));
        ++dp[nask][(n * 10 + j) % L];
      }
    n = n * 10 + d[i];
    if (mask == -1 || d[i] == 0) mask = -1;
    else mask |= 1 << (d[i] - 1);
  }
  return ret + getAns();
}

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  lt[0] = 1;
  for (int i = 1; i != U; ++i)
    for (int j = 0; j != 9; ++j)
      if ((i >> j) & 1) {
        lt[i] = lcm(lt[i ^ (1 << j)], j + 1);
        break;
      }

  ll l, r;
  cin >> l >> r;
  cout << solve(r + 1) - solve(l) << '\n';

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}
源文件, 语言: C++17

详细

Subtask #1:

score: 1
Accepted

Test #2:

score: 1
Accepted
time: 373ms
memory: 23696kb

input:

363144 876899

output:

3411

result:

ok single line: '3411'

Test #3:

score: 0
Accepted
time: 391ms
memory: 23716kb

input:

340230 874639

output:

3617

result:

ok single line: '3617'

Test #4:

score: 0
Accepted
time: 334ms
memory: 23696kb

input:

32302 781583

output:

6807

result:

ok single line: '6807'

Test #5:

score: 0
Accepted
time: 363ms
memory: 23896kb

input:

88488 631722

output:

5170

result:

ok single line: '5170'

Test #6:

score: 0
Accepted
time: 243ms
memory: 23740kb

input:

1 999999

output:

9039

result:

ok single line: '9039'

Test #7:

score: 0
Accepted
time: 40ms
memory: 23824kb

input:

1 3

output:

3

result:

ok single line: '3'

Subtask #2:

score: 1
Accepted

Test #8:

score: 1
Accepted
time: 383ms
memory: 23768kb

input:

179929 564769

output:

3604

result:

ok single line: '3604'

Test #9:

score: 0
Accepted
time: 353ms
memory: 23740kb

input:

31711 762820

output:

6733

result:

ok single line: '6733'

Test #10:

score: 0
Accepted
time: 382ms
memory: 23892kb

input:

256077 909855

output:

4760

result:

ok single line: '4760'

Test #11:

score: 0
Accepted
time: 35ms
memory: 23828kb

input:

1 1

output:

1

result:

ok single line: '1'

Test #12:

score: 0
Accepted
time: 413ms
memory: 23740kb

input:

999999 999999

output:

1

result:

ok single line: '1'

Test #13:

score: 0
Accepted
time: 218ms
memory: 23760kb

input:

7 777777

output:

7647

result:

ok single line: '7647'

Subtask #3:

score: 1
Accepted

Test #14:

score: 1
Accepted
time: 1242ms
memory: 23808kb

input:

122131631847754346 122131631848754346

output:

3453

result:

ok single line: '3453'

Test #15:

score: 0
Accepted
time: 1183ms
memory: 23696kb

input:

128432334112486543 128432334113486543

output:

4125

result:

ok single line: '4125'

Test #16:

score: 0
Accepted
time: 1184ms
memory: 23716kb

input:

743991663373248757 743991663374248757

output:

750

result:

ok single line: '750'

Test #17:

score: 0
Accepted
time: 1142ms
memory: 23792kb

input:

479733667788711858 479733667789711858

output:

540

result:

ok single line: '540'

Test #18:

score: 0
Accepted
time: 1124ms
memory: 23768kb

input:

984884249721569329 984884249722569329

output:

538

result:

ok single line: '538'

Test #19:

score: 0
Accepted
time: 1146ms
memory: 23812kb

input:

842181284281211148 842181284282211148

output:

4895

result:

ok single line: '4895'

Test #20:

score: 0
Accepted
time: 1119ms
memory: 23844kb

input:

111111111999111111 111111111999999999

output:

3471

result:

ok single line: '3471'

Test #21:

score: 0
Accepted
time: 1180ms
memory: 23772kb

input:

739711793799117979 739711793800117960

output:

909

result:

ok single line: '909'

Test #22:

score: 0
Accepted
time: 1220ms
memory: 23840kb

input:

128188218820028888 128188218821028888

output:

0

result:

ok single line: '0'

Subtask #4:

score: 1
Accepted

Test #23:

score: 1
Accepted
time: 1210ms
memory: 23832kb

input:

741243251591748310 741243251592748310

output:

0

result:

ok single line: '0'

Test #24:

score: 0
Accepted
time: 1246ms
memory: 23764kb

input:

667248191241322668 667248191242322668

output:

514

result:

ok single line: '514'

Test #25:

score: 0
Accepted
time: 1258ms
memory: 23624kb

input:

690471708215144656 690471708215929947

output:

0

result:

ok single line: '0'

Test #26:

score: 0
Accepted
time: 1186ms
memory: 23744kb

input:

822917689289508021 822917689290278919

output:

267

result:

ok single line: '267'

Test #27:

score: 0
Accepted
time: 1122ms
memory: 23768kb

input:

887303869896247348 887303869896952857

output:

0

result:

ok single line: '0'

Test #28:

score: 0
Accepted
time: 1122ms
memory: 23820kb

input:

111111111111111111 111111111111999999

output:

7356

result:

ok single line: '7356'

Test #29:

score: 0
Accepted
time: 1093ms
memory: 23712kb

input:

919319939131000000 919319939132000000

output:

3496

result:

ok single line: '3496'

Test #30:

score: 0
Accepted
time: 1098ms
memory: 23768kb

input:

999999999998999599 999999999999999569

output:

3473

result:

ok single line: '3473'

Test #31:

score: 0
Accepted
time: 1087ms
memory: 23744kb

input:

844748474847484872 844748474848484872

output:

1274

result:

ok single line: '1274'

Subtask #5:

score: 1
Accepted

Test #32:

score: 1
Accepted
time: 534ms
memory: 23832kb

input:

812434728 993348936

output:

338337

result:

ok single line: '338337'

Test #33:

score: 0
Accepted
time: 529ms
memory: 23744kb

input:

623332122 894148438

output:

486872

result:

ok single line: '486872'

Test #34:

score: 0
Accepted
time: 547ms
memory: 23760kb

input:

407616095 921231288

output:

830323

result:

ok single line: '830323'

Test #35:

score: 0
Accepted
time: 497ms
memory: 23844kb

input:

48017092 403952154

output:

914030

result:

ok single line: '914030'

Test #36:

score: 0
Accepted
time: 286ms
memory: 23820kb

input:

1 888888888

output:

1914280

result:

ok single line: '1914280'

Test #37:

score: 0
Accepted
time: 314ms
memory: 23696kb

input:

1 999999999

output:

2087730

result:

ok single line: '2087730'

Test #38:

score: 0
Accepted
time: 517ms
memory: 23836kb

input:

888888888 999999998

output:

173450

result:

ok single line: '173450'

Test #39:

score: 0
Accepted
time: 528ms
memory: 23768kb

input:

999999998 999999998

output:

0

result:

ok single line: '0'

Test #40:

score: 0
Accepted
time: 562ms
memory: 23696kb

input:

999999999 999999999

output:

1

result:

ok single line: '1'

Subtask #6:

score: 1
Accepted

Test #41:

score: 1
Accepted
time: 522ms
memory: 23772kb

input:

612898103 960422119

output:

626204

result:

ok single line: '626204'

Test #42:

score: 0
Accepted
time: 525ms
memory: 23740kb

input:

307767660 774168456

output:

836226

result:

ok single line: '836226'

Test #43:

score: 0
Accepted
time: 501ms
memory: 23828kb

input:

28144825 679458009

output:

1453616

result:

ok single line: '1453616'

Test #44:

score: 0
Accepted
time: 542ms
memory: 23764kb

input:

835232893 846324384

output:

31546

result:

ok single line: '31546'

Test #45:

score: 0
Accepted
time: 284ms
memory: 23788kb

input:

1 999999998

output:

2087729

result:

ok single line: '2087729'

Test #46:

score: 0
Accepted
time: 539ms
memory: 23792kb

input:

888888888 888888888

output:

1

result:

ok single line: '1'

Test #47:

score: 0
Accepted
time: 551ms
memory: 23788kb

input:

888888888 999999999

output:

173451

result:

ok single line: '173451'

Test #48:

score: 0
Accepted
time: 568ms
memory: 23628kb

input:

999999998 999999999

output:

1

result:

ok single line: '1'

Subtask #7:

score: 1
Accepted

Test #49:

score: 1
Accepted
time: 703ms
memory: 23740kb

input:

131718361824 249218928144

output:

98771504

result:

ok single line: '98771504'

Test #50:

score: 0
Accepted
time: 649ms
memory: 23628kb

input:

6261249492 441624183311

output:

351176580

result:

ok single line: '351176580'

Test #51:

score: 0
Accepted
time: 737ms
memory: 23764kb

input:

174446473236 631149932124

output:

274057587

result:

ok single line: '274057587'

Test #52:

score: 0
Accepted
time: 712ms
memory: 23760kb

input:

193314293316 538746482501

output:

236940170

result:

ok single line: '236940170'

Test #53:

score: 0
Accepted
time: 366ms
memory: 23808kb

input:

1 888888888888

output:

571424397

result:

ok single line: '571424397'

Test #54:

score: 0
Accepted
time: 405ms
memory: 23624kb

input:

1 999999999999

output:

631897069

result:

ok single line: '631897069'

Test #55:

score: 0
Accepted
time: 716ms
memory: 23624kb

input:

888888888888 999999999998

output:

60472672

result:

ok single line: '60472672'

Test #56:

score: 0
Accepted
time: 716ms
memory: 23768kb

input:

999999999998 999999999998

output:

0

result:

ok single line: '0'

Test #57:

score: 0
Accepted
time: 747ms
memory: 23756kb

input:

999999999999 999999999999

output:

1

result:

ok single line: '1'

Subtask #8:

score: 1
Accepted

Test #58:

score: 1
Accepted
time: 675ms
memory: 23768kb

input:

18819362664 912809626995

output:

556209369

result:

ok single line: '556209369'

Test #59:

score: 0
Accepted
time: 703ms
memory: 23628kb

input:

684391892328 713600370978

output:

13707982

result:

ok single line: '13707982'

Test #60:

score: 0
Accepted
time: 721ms
memory: 23892kb

input:

325274351910 419236628615

output:

69657750

result:

ok single line: '69657750'

Test #61:

score: 0
Accepted
time: 703ms
memory: 23768kb

input:

461249448192 484837848767

output:

20061229

result:

ok single line: '20061229'

Test #62:

score: 0
Accepted
time: 369ms
memory: 23772kb

input:

1 999999999998

output:

631897068

result:

ok single line: '631897068'

Test #63:

score: 0
Accepted
time: 721ms
memory: 23892kb

input:

888888888888 888888888888

output:

1

result:

ok single line: '1'

Test #64:

score: 0
Accepted
time: 784ms
memory: 23896kb

input:

888888888888 999999999999

output:

60472673

result:

ok single line: '60472673'

Test #65:

score: 0
Accepted
time: 928ms
memory: 23692kb

input:

999999999998 999999999999

output:

1

result:

ok single line: '1'

Subtask #9:

score: 1
Accepted

Test #66:

score: 1
Accepted
time: 1259ms
memory: 23716kb

input:

334337497414427632 563247418137418257

output:

16565546623710

result:

ok single line: '16565546623710'

Test #67:

score: 0
Accepted
time: 1249ms
memory: 23624kb

input:

222985405251591914 722886846342448367

output:

39144022836804

result:

ok single line: '39144022836804'

Test #68:

score: 0
Accepted
time: 1201ms
memory: 23756kb

input:

422758300424788386 991151974928048033

output:

40736108260842

result:

ok single line: '40736108260842'

Test #69:

score: 0
Accepted
time: 1185ms
memory: 23840kb

input:

246953072129180722 729186768937319112

output:

36372878116410

result:

ok single line: '36372878116410'

Test #70:

score: 0
Accepted
time: 588ms
memory: 23628kb

input:

1 888888888888888888

output:

75624142376194

result:

ok single line: '75624142376194'

Test #71:

score: 0
Accepted
time: 635ms
memory: 23756kb

input:

1 999999999999999999

output:

85088767344190

result:

ok single line: '85088767344190'

Test #72:

score: 0
Accepted
time: 1122ms
memory: 23824kb

input:

888888888888888888 999999999999999998

output:

9464624967996

result:

ok single line: '9464624967996'

Test #73:

score: 0
Accepted
time: 1140ms
memory: 23628kb

input:

999999999999999998 999999999999999998

output:

0

result:

ok single line: '0'

Test #74:

score: 0
Accepted
time: 1166ms
memory: 23744kb

input:

999999999999999999 999999999999999999

output:

1

result:

ok single line: '1'

Subtask #10:

score: 1
Accepted

Test #75:

score: 1
Accepted
time: 1127ms
memory: 23824kb

input:

714776677442744785 987126628667872896

output:

21760578239081

result:

ok single line: '21760578239081'

Test #76:

score: 0
Accepted
time: 1177ms
memory: 23756kb

input:

138884332647783744 238173673273438896

output:

9863665459360

result:

ok single line: '9863665459360'

Test #77:

score: 0
Accepted
time: 1172ms
memory: 23840kb

input:

214981933829884632 443134094745786315

output:

23694479164106

result:

ok single line: '23694479164106'

Test #78:

score: 0
Accepted
time: 1181ms
memory: 23712kb

input:

811832226268144129 999639293318282736

output:

17340049537490

result:

ok single line: '17340049537490'

Test #79:

score: 0
Accepted
time: 613ms
memory: 23696kb

input:

1 999999999999999998

output:

85088767344189

result:

ok single line: '85088767344189'

Test #80:

score: 0
Accepted
time: 1169ms
memory: 23768kb

input:

888888888888888888 888888888888888888

output:

1

result:

ok single line: '1'

Test #81:

score: 0
Accepted
time: 1196ms
memory: 23768kb

input:

888888888888888888 999999999999999999

output:

9464624967997

result:

ok single line: '9464624967997'

Test #82:

score: 0
Accepted
time: 1166ms
memory: 23744kb

input:

999999999999999998 999999999999999999

output:

1

result:

ok single line: '1'

Subtask #11:

score: 9.09091
Accepted
English 繁體中文 简体中文

服务器时间: 2025-02-08 18:02:08 | 开源项目