QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#478491#8487. Scooter numbersrania__#AC ✓583ms13712kbC++201.8kb2024-07-15 01:54:442024-07-15 01:54:44

Judging History

你现在查看的是最新测评结果

  • [2024-07-15 01:54:44]
  • 评测
  • 测评结果:AC
  • 用时:583ms
  • 内存:13712kb
  • [2024-07-15 01:54:44]
  • 提交

answer

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 7, P1 = 31, P2 = 37, mod = 1e9 + 7;

int mul(int a, int b) { return (1LL * a * b) % mod; }

int add(int a, int b) {
  a = (a + mod) % mod;
  b = (b + mod) % mod;
  return (a + b) % mod;
}

int fp(int b, int p) {
  if (b == 1 or p == 0) return 1;

  int ret = fp(b, p >> 1);
  ret = mul(ret, ret);

  if (p & 1) ret = mul(ret, b);

  return ret;
}

ll modInv(ll n) { return fp(n, mod - 2); }

ll fact[N], inv[N];

void pre() {
  fact[0] = inv[0] = 1;
  for (ll i = 1; i < N; i++)
    fact[i] = (fact[i - 1] * i) % mod, inv[i] = fp(fact[i], mod - 2);
}

ll nCr(ll n, ll r) { return ((fact[n] * inv[r]) % mod * inv[n - r]) % mod; }

ll nPr(ll n, ll r) { return ((fact[n] * inv[n - r])) % mod; }
int dp[1005][1005][2], tmp;
int solve(int last, int rem , int u ) {
  if (last == 1001) {
    return (!rem);
  }
  int &ret = dp[last][rem][u];
  if (~ret) return ret;
  ret = 0;
  // take
  if (last <= rem && last != tmp)
  ret = add(ret , solve( last , rem-last , 1));
  // leave
  if ( u  || last>= tmp)
  	ret = add(ret , solve(last+1  , rem , 0));
  return ret;
}
void doWork() {
  int n;
  cin >> n;
  tmp = 46;
  ll ans = 0;
  while (tmp > 0) {
    memset(dp, -1, sizeof dp);
    ans = add(ans, mul(solve(1, n,0), tmp));
    tmp--;
  }
  cout << ans << endl;
}

int main() {
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);
  int t = 1;
  // cin >> t;
  while (t--) {
    doWork();
  }
  return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 11ms
memory: 13504kb

input:

1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 14ms
memory: 12764kb

input:

3

output:

6

result:

ok 1 number(s): "6"

Test #3:

score: 0
Accepted
time: 13ms
memory: 12084kb

input:

2

output:

3

result:

ok 1 number(s): "3"

Test #4:

score: 0
Accepted
time: 10ms
memory: 11640kb

input:

5

output:

14

result:

ok 1 number(s): "14"

Test #5:

score: 0
Accepted
time: 10ms
memory: 12716kb

input:

7

output:

32

result:

ok 1 number(s): "32"

Test #6:

score: 0
Accepted
time: 14ms
memory: 12264kb

input:

10

output:

93

result:

ok 1 number(s): "93"

Test #7:

score: 0
Accepted
time: 14ms
memory: 12784kb

input:

15

output:

426

result:

ok 1 number(s): "426"

Test #8:

score: 0
Accepted
time: 151ms
memory: 12296kb

input:

431

output:

939569366

result:

ok 1 number(s): "939569366"

Test #9:

score: 0
Accepted
time: 102ms
memory: 12304kb

input:

339

output:

779167693

result:

ok 1 number(s): "779167693"

Test #10:

score: 0
Accepted
time: 266ms
memory: 11696kb

input:

619

output:

95446348

result:

ok 1 number(s): "95446348"

Test #11:

score: 0
Accepted
time: 204ms
memory: 11716kb

input:

527

output:

577792800

result:

ok 1 number(s): "577792800"

Test #12:

score: 0
Accepted
time: 32ms
memory: 11640kb

input:

131

output:

124115481

result:

ok 1 number(s): "124115481"

Test #13:

score: 0
Accepted
time: 17ms
memory: 12764kb

input:

39

output:

91904

result:

ok 1 number(s): "91904"

Test #14:

score: 0
Accepted
time: 99ms
memory: 13532kb

input:

319

output:

584973336

result:

ok 1 number(s): "584973336"

Test #15:

score: 0
Accepted
time: 63ms
memory: 11860kb

input:

227

output:

115048980

result:

ok 1 number(s): "115048980"

Test #16:

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

input:

135

output:

277566229

result:

ok 1 number(s): "277566229"

Test #17:

score: 0
Accepted
time: 335ms
memory: 12568kb

input:

719

output:

145078347

result:

ok 1 number(s): "145078347"

Test #18:

score: 0
Accepted
time: 484ms
memory: 12844kb

input:

898

output:

683435513

result:

ok 1 number(s): "683435513"

Test #19:

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

input:

806

output:

146315038

result:

ok 1 number(s): "146315038"

Test #20:

score: 0
Accepted
time: 140ms
memory: 12552kb

input:

410

output:

459095697

result:

ok 1 number(s): "459095697"

Test #21:

score: 0
Accepted
time: 572ms
memory: 12712kb

input:

994

output:

630763622

result:

ok 1 number(s): "630763622"

Test #22:

score: 0
Accepted
time: 249ms
memory: 12664kb

input:

598

output:

336568276

result:

ok 1 number(s): "336568276"

Test #23:

score: 0
Accepted
time: 193ms
memory: 13024kb

input:

506

output:

472335883

result:

ok 1 number(s): "472335883"

Test #24:

score: 0
Accepted
time: 143ms
memory: 13596kb

input:

414

output:

34633570

result:

ok 1 number(s): "34633570"

Test #25:

score: 0
Accepted
time: 315ms
memory: 12516kb

input:

694

output:

33145311

result:

ok 1 number(s): "33145311"

Test #26:

score: 0
Accepted
time: 250ms
memory: 13548kb

input:

602

output:

36309295

result:

ok 1 number(s): "36309295"

Test #27:

score: 0
Accepted
time: 56ms
memory: 12596kb

input:

206

output:

965741458

result:

ok 1 number(s): "965741458"

Test #28:

score: 0
Accepted
time: 100ms
memory: 13712kb

input:

320

output:

644124816

result:

ok 1 number(s): "644124816"

Test #29:

score: 0
Accepted
time: 61ms
memory: 13620kb

input:

229

output:

347321847

result:

ok 1 number(s): "347321847"

Test #30:

score: 0
Accepted
time: 193ms
memory: 12032kb

input:

509

output:

595982025

result:

ok 1 number(s): "595982025"

Test #31:

score: 0
Accepted
time: 139ms
memory: 12528kb

input:

417

output:

16909210

result:

ok 1 number(s): "16909210"

Test #32:

score: 0
Accepted
time: 11ms
memory: 12016kb

input:

21

output:

2048

result:

ok 1 number(s): "2048"

Test #33:

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

input:

909

output:

839672399

result:

ok 1 number(s): "839672399"

Test #34:

score: 0
Accepted
time: 193ms
memory: 12424kb

input:

513

output:

267443664

result:

ok 1 number(s): "267443664"

Test #35:

score: 0
Accepted
time: 27ms
memory: 12104kb

input:

117

output:

14068061

result:

ok 1 number(s): "14068061"

Test #36:

score: 0
Accepted
time: 15ms
memory: 12628kb

input:

25

output:

5248

result:

ok 1 number(s): "5248"

Test #37:

score: 0
Accepted
time: 254ms
memory: 13056kb

input:

609

output:

920742555

result:

ok 1 number(s): "920742555"

Test #38:

score: 0
Accepted
time: 232ms
memory: 13060kb

input:

575

output:

758146156

result:

ok 1 number(s): "758146156"

Test #39:

score: 0
Accepted
time: 176ms
memory: 13448kb

input:

483

output:

987545474

result:

ok 1 number(s): "987545474"

Test #40:

score: 0
Accepted
time: 360ms
memory: 11952kb

input:

763

output:

122202604

result:

ok 1 number(s): "122202604"

Test #41:

score: 0
Accepted
time: 301ms
memory: 12788kb

input:

671

output:

936583162

result:

ok 1 number(s): "936583162"

Test #42:

score: 0
Accepted
time: 77ms
memory: 11860kb

input:

275

output:

325917930

result:

ok 1 number(s): "325917930"

Test #43:

score: 0
Accepted
time: 446ms
memory: 12852kb

input:

859

output:

43843479

result:

ok 1 number(s): "43843479"

Test #44:

score: 0
Accepted
time: 168ms
memory: 12288kb

input:

463

output:

161854379

result:

ok 1 number(s): "161854379"

Test #45:

score: 0
Accepted
time: 124ms
memory: 13640kb

input:

372

output:

14874157

result:

ok 1 number(s): "14874157"

Test #46:

score: 0
Accepted
time: 82ms
memory: 12184kb

input:

280

output:

844882342

result:

ok 1 number(s): "844882342"

Test #47:

score: 0
Accepted
time: 224ms
memory: 12156kb

input:

560

output:

580084876

result:

ok 1 number(s): "580084876"

Test #48:

score: 0
Accepted
time: 423ms
memory: 11700kb

input:

830

output:

746490347

result:

ok 1 number(s): "746490347"

Test #49:

score: 0
Accepted
time: 154ms
memory: 13600kb

input:

434

output:

233044050

result:

ok 1 number(s): "233044050"

Test #50:

score: 0
Accepted
time: 18ms
memory: 13312kb

input:

38

output:

76198

result:

ok 1 number(s): "76198"

Test #51:

score: 0
Accepted
time: 504ms
memory: 12372kb

input:

926

output:

841519650

result:

ok 1 number(s): "841519650"

Test #52:

score: 0
Accepted
time: 205ms
memory: 13488kb

input:

530

output:

267785088

result:

ok 1 number(s): "267785088"

Test #53:

score: 0
Accepted
time: 32ms
memory: 12432kb

input:

134

output:

760275453

result:

ok 1 number(s): "760275453"

Test #54:

score: 0
Accepted
time: 333ms
memory: 12516kb

input:

718

output:

481253387

result:

ok 1 number(s): "481253387"

Test #55:

score: 0
Accepted
time: 268ms
memory: 11892kb

input:

626

output:

374754869

result:

ok 1 number(s): "374754869"

Test #56:

score: 0
Accepted
time: 211ms
memory: 13248kb

input:

534

output:

761711975

result:

ok 1 number(s): "761711975"

Test #57:

score: 0
Accepted
time: 401ms
memory: 12252kb

input:

814

output:

132485354

result:

ok 1 number(s): "132485354"

Test #58:

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

input:

781

output:

266853746

result:

ok 1 number(s): "266853746"

Test #59:

score: 0
Accepted
time: 312ms
memory: 12172kb

input:

689

output:

550306339

result:

ok 1 number(s): "550306339"

Test #60:

score: 0
Accepted
time: 88ms
memory: 12304kb

input:

293

output:

362728334

result:

ok 1 number(s): "362728334"

Test #61:

score: 0
Accepted
time: 55ms
memory: 12032kb

input:

201

output:

459517496

result:

ok 1 number(s): "459517496"

Test #62:

score: 0
Accepted
time: 175ms
memory: 12792kb

input:

481

output:

236863306

result:

ok 1 number(s): "236863306"

Test #63:

score: 0
Accepted
time: 131ms
memory: 13484kb

input:

389

output:

753961872

result:

ok 1 number(s): "753961872"

Test #64:

score: 0
Accepted
time: 550ms
memory: 12992kb

input:

973

output:

492222103

result:

ok 1 number(s): "492222103"

Test #65:

score: 0
Accepted
time: 468ms
memory: 12504kb

input:

881

output:

974520537

result:

ok 1 number(s): "974520537"

Test #66:

score: 0
Accepted
time: 180ms
memory: 12092kb

input:

485

output:

882444680

result:

ok 1 number(s): "882444680"

Test #67:

score: 0
Accepted
time: 25ms
memory: 12748kb

input:

89

output:

177271582

result:

ok 1 number(s): "177271582"

Test #68:

score: 0
Accepted
time: 51ms
memory: 12220kb

input:

204

output:

476964940

result:

ok 1 number(s): "476964940"

Test #69:

score: 0
Accepted
time: 23ms
memory: 11820kb

input:

112

output:

844981858

result:

ok 1 number(s): "844981858"

Test #70:

score: 0
Accepted
time: 320ms
memory: 13556kb

input:

696

output:

139422249

result:

ok 1 number(s): "139422249"

Test #71:

score: 0
Accepted
time: 255ms
memory: 13072kb

input:

604

output:

95116575

result:

ok 1 number(s): "95116575"

Test #72:

score: 0
Accepted
time: 473ms
memory: 13420kb

input:

884

output:

358504338

result:

ok 1 number(s): "358504338"

Test #73:

score: 0
Accepted
time: 393ms
memory: 13260kb

input:

792

output:

149579090

result:

ok 1 number(s): "149579090"

Test #74:

score: 0
Accepted
time: 135ms
memory: 11856kb

input:

396

output:

735811611

result:

ok 1 number(s): "735811611"

Test #75:

score: 0
Accepted
time: 564ms
memory: 11896kb

input:

980

output:

960754618

result:

ok 1 number(s): "960754618"

Test #76:

score: 0
Accepted
time: 471ms
memory: 13328kb

input:

888

output:

215533287

result:

ok 1 number(s): "215533287"

Test #77:

score: 0
Accepted
time: 183ms
memory: 11900kb

input:

492

output:

678232209

result:

ok 1 number(s): "678232209"

Test #78:

score: 0
Accepted
time: 165ms
memory: 12704kb

input:

458

output:

654077127

result:

ok 1 number(s): "654077127"

Test #79:

score: 0
Accepted
time: 583ms
memory: 11832kb

input:

1000

output:

667750064

result:

ok 1 number(s): "667750064"

Extra Test:

score: 0
Extra Test Passed