QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#478491 | #8487. Scooter numbers | rania__# | AC ✓ | 583ms | 13712kb | C++20 | 1.8kb | 2024-07-15 01:54:44 | 2024-07-15 01:54:44 |
Judging History
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,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
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