QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#243660 | #4939. Red Black Ball | ideograph_advantage# | WA | 8ms | 4400kb | C++17 | 3.8kb | 2023-11-08 15:35:18 | 2023-11-08 15:35:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define iter(v) v.begin(), v.end()
#define SZ(v) (int)v.size()
#define pb emplace_back
#define ff first
#define ss second
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U>
void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
while(l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) void()
#define pary(...) void()
#endif
template<class A, class B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.ff << ',' << p.ss << ')';
}
const ll MOD = 998244353;
vector<ll> fac(105);
vector<ll> invf(105);
ll inv(ll a){
ll b = MOD - 2;
ll ans = 1;
while(b > 0){
if(b & 1) ans = ans * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return ans;
}
void init(){
fac[0] = invf[0] = 1;
for(int i = 1; i < 105; i++){
fac[i] = fac[i - 1] * i % MOD;
invf[i] = inv(fac[i]);
}
}
ll C(int n, int k){
return fac[n] * invf[k] % MOD * invf[n - k] % MOD;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
init();
int n, m;
cin >> n >> m;
vector<pll> fix(n);
int black = 0;
for(int i = 0; i < n; i++){
cin >> fix[i].ff;
string s;
cin >> s;
if(s == "BLACK") fix[i].ss = 1, black++;
else fix[i].ss = 0;
}
sort(iter(fix));
fix.pb(pii(fix.back().ff + 1e9, fix.back().ss));
pary(iter(fix));
vector<ll> ps(m);
for(int i = 0; i < m; i++) cin >> ps[i];
sort(iter(ps));
vector<int> grp;
vector<ll> knap(m + 1);
knap[0] = 1;
int ptr = 0;
for(int t = 0; t < n; t++){
vector<ll> p;
p.pb(fix[t].ff);
while(ptr < m && ps[ptr] <= fix[t + 1].ff)
p.pb(ps[ptr++]);
p.pb(fix[t + 1].ff);
grp.pb(SZ(p) - 2);
int c1 = fix[t].ss, c2 = fix[t + 1].ss;
debug("test", c1, c2, fix[t].ff, fix[t + 1].ff);
pary(iter(p));
int sz = SZ(p);
vector<vector<vector<ll>>> dp(sz, vector<vector<ll>>(sz, vector<ll>(sz + 1)));
for(int i = 0; i + 1 < sz; i++){
dp[i][i + 1][0] = 1;
}
for(int len = 2; len < sz; len++){
for(int l = 0; l + len < sz; l++){
int r = l + len;
ll lx = p[l], rx = p[r];
for(int mid = l + 1; mid < r; mid++){
ll mx = p[mid];
if(mx - lx <= rx - mx){
int b1 = c1 == 1 ? mid - l : 0;
debug("ok left", l, r, mid, b1);
for(int b = 0; b < sz; b++){
if(b - b1 < 0) continue;
debug("b", b, ":", dp[mid][r][b - b1], C(r - l - 2, mid - l - 1), fac[mid - l - 1]);
dp[l][r][b] += dp[mid][r][b - b1] * C(r - l - 2, mid - l - 1) % MOD * fac[mid - l - 1] % MOD;
dp[l][r][b] %= MOD;
}
}
else{
int b2 = c2 == 1 ? r - mid : 0;
debug("ok right", l, r, mid, b2);
for(int b = 0; b < sz; b++){
if(b - b2 < 0) continue;
debug("b", b, ":", dp[l][mid][b - b2] * C(r - l - 2, r - mid - 1) % MOD * fac[r - mid - 1] % MOD);
dp[l][r][b] += dp[l][mid][b - b2] * C(r - l - 2, r - mid - 1) % MOD * fac[r - mid - 1] % MOD;
dp[l][r][b] %= MOD;
}
}
}
debug("dp", l, r);
pary(iter(dp[l][r]));
}
}
vector<ll> knap2(m + 1);
for(int b = 0; b <= sz; b++){
debug("dp", b, dp[0][sz - 1][b]);
for(int i = 0; i + b <= m; i++){
//debug("test", b, dp[0][sz - 1][b], "->", i, knap[i] * dp[0][sz - 1][b] % MOD);
knap2[i + b] += knap[i] * dp[0][sz - 1][b] % MOD;
knap2[i + b] %= MOD;
}
}
knap.swap(knap2);
}
ll ans = 0;
for(int b = 0; b <= m; b++){
int r = n + m - b - black;
if(r > b + black){
ans += knap[b];
ans %= MOD;
}
}
ans = ans * fac[m] % MOD;
for(int i : grp){
ans = ans * invf[i] % MOD;
}
cout << ans << "\n";
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3528kb
input:
2 3 1 BLACK 10 RED 2 5 7
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
2 3 1 RED 10 BLACK 2 4 7
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3440kb
input:
2 3 1 RED 10 BLACK 7 4 2
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
20 46 238846592 BLACK 199923217 RED 526626128 BLACK 62308338 RED 523811748 RED 59432 BLACK 273113193 BLACK 730729301 BLACK 973259012 RED 225318015 BLACK 611574923 RED 234880345 RED 485448383 BLACK 405607946 BLACK 747693124 RED 794086621 BLACK 91585417 BLACK 466451303 RED 244184598 RED 334788273 RED ...
output:
850819974
result:
ok single line: '850819974'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
24 46 1579 BLACK 10321 BLACK 7159 RED 13111 RED 11437 RED 277 BLACK 11623 BLACK 9391 RED 1765 RED 6787 BLACK 12367 BLACK 8647 RED 1207 RED 3811 RED 4183 BLACK 649 BLACK 11995 RED 6043 RED 2137 BLACK 8833 BLACK 7345 BLACK 463 RED 4369 RED 5113 BLACK 10507 7717 2509 4741 3997 5299 10879 8275 9763 5671...
output:
988708148
result:
ok single line: '988708148'
Test #6:
score: 0
Accepted
time: 7ms
memory: 4316kb
input:
2 49 747 RED 38197 BLACK 23966 11982 30707 20970 32205 23217 1496 24715 36699 20221 8986 8237 32954 29209 35950 18723 11233 13480 5990 22468 12731 27711 7488 2245 26213 16476 17225 34452 19472 15727 14978 9735 3743 4492 2994 33703 6739 17974 5241 21719 14229 28460 25464 29958 26962 35201 37448 10484...
output:
554620557
result:
ok single line: '554620557'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
5 49 18120 BLACK 7140 BLACK 39348 RED 552 RED 10068 RED 28368 2748 23244 10800 21780 34956 20316 15192 13728 6408 3480 22512 18852 2016 36420 4944 31296 37152 17388 7872 35688 32760 16656 34224 37884 19584 1284 11532 33492 26904 24708 15924 21048 4212 9336 5676 32028 29100 29832 23976 12996 27636 26...
output:
680298042
result:
ok single line: '680298042'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
13 49 107689803 BLACK 17641182 BLACK 719317410 RED 998074505 RED 629653125 BLACK 596623825 RED 302505396 BLACK 755371774 BLACK 894467843 BLACK 4346620 RED 67686851 RED 195025022 RED 843051518 RED 549024576 858137241 623250360 760797781 289351341 882742196 363095414 925898076 534873997 550178294 5220...
output:
48457350
result:
ok single line: '48457350'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
16 47 57366995 RED 142257512 RED 269104096 BLACK 85386190 BLACK 947963705 RED 327042464 RED 249359510 RED 779101020 BLACK 572804408 RED 14976978 BLACK 994513563 BLACK 12270136 RED 832385903 BLACK 827404778 RED 349299284 BLACK 157782755 BLACK 194509365 275027783 635585542 141178577 746922135 28144721...
output:
110578970
result:
ok single line: '110578970'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
4 47 557094997 BLACK 977689947 RED 524426310 RED 37970126 BLACK 490604903 841435598 941812205 445138440 510338155 186951281 171655969 622981900 583907196 970645377 428450182 138362981 621613180 99063603 462141100 154435607 547626426 298066536 620132019 171659177 777569078 731639638 947801880 4924222...
output:
371087856
result:
ok single line: '371087856'
Test #11:
score: 0
Accepted
time: 8ms
memory: 4332kb
input:
2 50 211 BLACK 160 RED 195 205 189 187 179 175 163 164 161 199 169 194 182 192 162 197 173 165 174 167 201 176 207 206 184 196 181 204 190 191 198 183 180 210 186 208 209 203 171 178 193 202 168 185 172 200 170 188 177 166
output:
502060921
result:
ok single line: '502060921'
Test #12:
score: 0
Accepted
time: 8ms
memory: 4324kb
input:
2 50 60 RED 9 BLACK 30 31 37 10 32 11 22 50 41 33 40 42 49 16 25 53 45 38 47 18 35 15 12 57 59 28 52 24 58 13 17 44 34 19 21 56 23 46 51 36 14 39 20 26 43 55 27 29 54 48
output:
912286572
result:
ok single line: '912286572'
Test #13:
score: 0
Accepted
time: 7ms
memory: 4304kb
input:
2 49 797 BLACK 847 RED 815 845 846 831 798 814 802 836 804 822 824 843 813 811 829 821 835 808 819 825 842 809 799 816 840 817 803 838 832 833 841 812 839 823 844 837 826 828 805 830 818 810 807 827 800 834 820 801 806
output:
98264595
result:
ok single line: '98264595'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3452kb
input:
4 10 1 RED 10 BLACK 20 RED 30 BLACK 2 4 7 11 15 19 22 27 31 35
output:
302400
result:
ok single line: '302400'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3436kb
input:
50 50 997819057 RED 571068710 RED 12923796 BLACK 675274557 BLACK 198891694 BLACK 35760570 RED 104656205 BLACK 907695902 RED 667522196 RED 277759900 BLACK 875662039 RED 487653162 RED 420664476 RED 491922817 RED 106960712 BLACK 730434518 BLACK 91269203 RED 540551083 BLACK 329623764 RED 101423414 RED 1...
output:
77653369
result:
ok single line: '77653369'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3424kb
input:
50 50 760120586 RED 588967894 BLACK 184525860 BLACK 485139836 BLACK 747407168 RED 255273339 BLACK 318087840 BLACK 348327067 BLACK 401897466 BLACK 401842061 RED 20723866 BLACK 792840588 BLACK 159804240 BLACK 122209685 BLACK 406224603 RED 541094593 BLACK 480516505 BLACK 141575045 BLACK 377818141 BLACK...
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
50 50 473161614 RED 887795743 RED 411353593 RED 434247969 RED 97587809 RED 849158159 BLACK 873680796 BLACK 982248995 RED 244554900 RED 747842313 BLACK 644666252 RED 895305511 BLACK 582107071 RED 777547831 RED 488402073 RED 936072807 RED 866154596 RED 716491641 RED 2902554 BLACK 694922113 RED 6692575...
output:
849583562
result:
ok single line: '849583562'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3428kb
input:
50 50 29384 RED 24223 RED 39309 BLACK 14695 BLACK 26208 BLACK 38912 RED 30178 BLACK 16680 RED 25017 BLACK 34148 BLACK 17871 BLACK 1197 BLACK 25811 RED 23429 BLACK 21047 BLACK 19062 RED 20650 RED 8343 BLACK 9931 BLACK 34545 RED 21444 RED 12313 RED 11916 BLACK 7946 RED 38515 BLACK 32957 RED 32163 BLAC...
output:
512746563
result:
ok single line: '512746563'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
50 50 2279 BLACK 9242 RED 18315 BLACK 9031 BLACK 7765 RED 19370 RED 4178 BLACK 2912 RED 13040 BLACK 8820 RED 16416 BLACK 8609 BLACK 8187 BLACK 6288 BLACK 10508 RED 19159 BLACK 11985 RED 20636 BLACK 10930 BLACK 11352 RED 13462 BLACK 4600 BLACK 10297 BLACK 14939 RED 13884 RED 13251 RED 21269 BLACK 126...
output:
789991323
result:
ok single line: '789991323'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
10 50 37475 RED 66161 RED 82241 RED 43176 RED 7004 RED 65343 RED 120 BLACK 99208 RED 61453 BLACK 62536 RED 2963 40424 2197 8523 77068 1912 39966 53086 10329 53693 86718 35523 84835 83332 2995 28115 68212 19056 95915 88930 84279 60631 31622 79633 77581 72053 2919 66568 95832 36510 91400 93723 73726 5...
output:
700438304
result:
ok single line: '700438304'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
2 10 2494 BLACK 85628 RED 55969 51376 16212 22266 6560 5510 26504 6615 14428 36949
output:
51000
result:
ok single line: '51000'
Test #22:
score: 0
Accepted
time: 8ms
memory: 4276kb
input:
1 50 490066032 RED 551961788 215302426 963443925 458426999 741724505 214314722 995586101 839107331 375208660 356687250 815273320 935339219 75603053 765499380 141630034 172221255 689719940 102671067 164678582 985793723 404144776 421517520 563048529 591716729 104682725 567187037 126036133 206929346 28...
output:
700438304
result:
ok single line: '700438304'
Test #23:
score: 0
Accepted
time: 3ms
memory: 4400kb
input:
1 50 250265415 BLACK 352594208 434120831 446255973 621708546 653896547 736975633 658060669 50257939 1485366 322555994 191748779 614012427 831810047 69881780 4145022 87369940 628602900 286911367 999458990 653472084 961369495 341700627 691144081 898039038 716953405 559163331 772686256 457355982 942099...
output:
0
result:
ok single line: '0'
Test #24:
score: 0
Accepted
time: 8ms
memory: 4388kb
input:
2 50 1000000000 BLACK 362757848 RED 89146245 161503614 453245193 19628531 1437240 116209607 235049737 42396644 157881205 210344379 414606924 104165204 132631391 57776815 452504274 132369248 163315429 231924898 131474038 320207563 83957669 387314840 390239636 305059496 229192532 259250466 289302826 2...
output:
700438304
result:
ok single line: '700438304'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3460kb
input:
2 9 454895874 RED 921212094 BLACK 693523525 585063856 906523440 647212240 589284011 669546420 909729625 767928733 636562059
output:
268560
result:
ok single line: '268560'
Test #26:
score: 0
Accepted
time: 8ms
memory: 4308kb
input:
3 50 26578416 RED 995790908 BLACK 586231 BLACK 283825140 938879764 800187797 383781793 377888658 490576153 565762562 646638653 400548408 374045211 250368413 91339784 702315121 640019908 231282062 309849633 394735598 644452551 405237222 8019044 728060750 757146403 667508182 87372221 432745875 5768523...
output:
169391133
result:
ok single line: '169391133'
Test #27:
score: 0
Accepted
time: 3ms
memory: 3688kb
input:
3 50 5532952 BLACK 987313564 BLACK 367367354 RED 780878647 617485102 170881973 954620849 754788652 34653180 762846057 85964945 684469911 810789085 586174557 514735247 632231752 115116660 947344876 871812393 717910057 650378258 950484075 553662460 452924940 767781881 508033403 185705097 27655787 1241...
output:
149593064
result:
ok single line: '149593064'
Test #28:
score: 0
Accepted
time: 2ms
memory: 3632kb
input:
3 50 385468244 BLACK 991391520 RED 49406700 RED 937974503 628776105 311292195 465013373 369936767 761172953 403720768 137104638 114090342 528165262 559285052 320258983 303693757 982442377 744903788 677392648 203746396 383698291 385592132 479830480 781197638 364676061 965252124 735032904 259952578 62...
output:
286688955
result:
ok single line: '286688955'
Test #29:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
7 50 481432738 BLACK 473865321 RED 986281738 BLACK 48570161 BLACK 389648020 BLACK 349284785 RED 522279245 RED 188304326 497511854 620848633 929801867 431029982 674025060 209273353 813213553 61071495 534032833 91349743 666975405 124445036 486113908 940626667 447419364 930707104 707883483 367587321 39...
output:
984156727
result:
ok single line: '984156727'
Test #30:
score: 0
Accepted
time: 2ms
memory: 3724kb
input:
3 50 41400523 RED 659747844 BLACK 969749547 RED 424378460 873897144 46089501 255562659 540895096 262027828 771619212 176665657 887835885 421369112 880492390 260529845 785585718 779078650 510659924 691941012 244128573 162065111 357633368 73929233 830120599 781126502 957327259 233713696 373337872 5955...
output:
593433617
result:
ok single line: '593433617'
Test #31:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
3 50 990310479 BLACK 560682068 RED 10397383 BLACK 501565640 358649047 346103002 842598032 574353306 311651462 848008667 126746164 648623326 944005180 300769842 518170880 81138976 764494060 989688315 543648611 600408276 515461451 969138119 789000285 634428462 864645480 476871732 783646463 889961146 2...
output:
77202729
result:
ok single line: '77202729'
Test #32:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
50 49 284867275 BLACK 544239955 BLACK 964172845 BLACK 245507363 BLACK 73114412 BLACK 34419461 RED 579620204 BLACK 50242298 RED 636600340 RED 138186937 BLACK 692004163 RED 631324891 BLACK 999735876 BLACK 246496162 RED 989122604 RED 262396810 BLACK 616426477 RED 944379004 RED 526251894 RED 828097035 B...
output:
652885152
result:
ok single line: '652885152'
Test #33:
score: 0
Accepted
time: 1ms
memory: 3420kb
input:
17 48 285920251 RED 816096611 BLACK 893609675 RED 427336531 RED 563260337 BLACK 950284979 BLACK 660413524 RED 380346005 BLACK 756205543 RED 699250271 BLACK 980631598 RED 713196 RED 207066922 BLACK 89433012 RED 126507978 BLACK 163237996 RED 46070175 BLACK 844884527 421944862 136072802 32435814 810568...
output:
413535450
result:
ok single line: '413535450'
Test #34:
score: 0
Accepted
time: 1ms
memory: 3424kb
input:
11 50 263365186 RED 473921873 BLACK 116141847 RED 973058580 BLACK 351009129 BLACK 626198532 RED 395664159 RED 213579423 BLACK 2216881 BLACK 734145681 BLACK 850147353 RED 454823767 60529149 481450455 215925204 73959831 176436522 876564502 37752828 617467809 533164492 175754632 224072016 593329683 295...
output:
517178047
result:
ok single line: '517178047'
Test #35:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
30 29 536871256 BLACK 536871425 BLACK 536877772 BLACK 536871038 BLACK 536888489 BLACK 536881561 BLACK 536884737 BLACK 536883080 BLACK 536878913 BLACK 536870913 RED 536892865 BLACK 536870940 BLACK 536872641 BLACK 536872244 BLACK 536870921 BLACK 536895302 BLACK 536890596 BLACK 536874288 BLACK 53688017...
output:
1
result:
ok single line: '1'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3460kb
input:
2 10 892 RED 1508 BLACK 1172 1116 1060 1284 1004 1228 1396 1340 1452 948
output:
2074320
result:
ok single line: '2074320'
Test #37:
score: 0
Accepted
time: 4ms
memory: 4288kb
input:
2 50 1000000000 BLACK 362757848 RED 89146245 161503614 453245193 19628531 1437240 116209607 235049737 42396644 157881205 210344379 414606924 104165204 132631391 57776815 452504274 132369248 163315429 231924898 131474038 320207563 83957669 387314840 390239636 305059496 229192532 259250466 289302826 2...
output:
700438304
result:
ok single line: '700438304'
Test #38:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
5 41 512889008 RED 515371563 RED 567896597 BLACK 850108281 RED 872059529 BLACK 21709340 76274387 93554370 113717426 126996195 145189408 150700499 153924418 200072831 232519175 284064424 362276370 395396340 421749460 445239869 489787693 495509692 508524581 508532760 558858439 560330375 577000110 6099...
output:
736050414
result:
ok single line: '736050414'
Test #39:
score: -100
Wrong Answer
time: 1ms
memory: 3520kb
input:
9 38 839 RED 3924 BLACK 10094 BLACK 10711 BLACK 14413 RED 18732 RED 20583 BLACK 23051 RED 26753 BLACK 222 1456 2073 2690 3307 4541 5158 5775 6392 7009 7626 8243 8860 9477 11328 11945 12562 13179 13796 15030 15647 16264 16881 17498 18115 19349 19966 21200 21817 22434 23668 24285 24902 25519 26136 273...
output:
604556096
result:
wrong answer 1st lines differ - expected: '345959282', found: '604556096'