QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#521015 | #1436. Split in Sets | c20251515 | TL | 200ms | 47332kb | C++14 | 1.6kb | 2024-08-15 19:52:35 | 2024-08-15 19:52:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,mod=1e9+7;
ll n,K,a[N],ans1=0,ans2=1;
ll fac[N],inv[N];
ll maxn=0;
bool vis[N];
vector<ll> p;
ll ksm(ll x,ll k){
ll tmp=1;
while(k){
if(k%2==1) tmp=tmp*x%mod;
x=x*x%mod;
k/=2;
}
return tmp;
}
void init(){
fac[0]=1;
for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
inv[1000000]=ksm(fac[1000000],mod-2);
for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
ll c(ll x,ll y){
if(x<y) return 0;
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void get(ll x){
ll now=0;
while(x){
x/=2;
now++;
}
maxn=max(maxn,now-1);
}
ll strling(ll x,ll y){
if(x<y) return 0;
if(y==0) return 0;
if(x==y) return 1;
if(y==1) return 1;
return (strling(x-1,y-1)+y*strling(x-1,y)%mod)%mod;
}
void dfs(vector<ll> s,ll k,ll deep){
if((ll)s.size()<k) exit(0);
ll cnt0=0,cnt1=0;
for(auto x:s){
if(x&(1ll<<deep)) cnt1++;
else cnt0++;
}
ans1+=(1ll<<deep)*min(k-(cnt0>0),cnt1);
if(deep==0){
if(cnt1>=k) ans2=ans2*strling(cnt1+1,k)%mod;
else ans2=ans2*strling(cnt0,k-cnt1)%mod;
return;
}
if(k > cnt1) {
vector<ll> B;
for(auto i : s) if((~i >> deep) & 1) B.push_back(i); else ans1 += i & ((1 << deep) - 1);
dfs(B,k - cnt1,deep - 1);
} else {
vector<ll> B;ll andsum = INT_MAX;
for(auto i : s) if((i >> deep) & 1) B.push_back(i); else andsum &= i;
if(cnt0) B.push_back(andsum);
dfs(B,k,deep - 1);
}
}
int main(){
cin>>n>>K;
init();
for(int i=1;i<=n;i++){
cin>>a[i];
get(a[i]);
p.push_back(a[i]);
}
dfs(p,K,maxn);
ans2=ans2*fac[K]%mod;
cout<<ans1<<" "<<ans2;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 12ms
memory: 20384kb
input:
3 2 4 7 5
output:
11 2
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 7ms
memory: 20948kb
input:
4 1 44 47 74 77
output:
8 1
result:
ok 2 tokens
Test #3:
score: 0
Accepted
time: 3ms
memory: 22000kb
input:
4 4 44 47 74 77
output:
242 24
result:
ok 2 tokens
Test #4:
score: 0
Accepted
time: 10ms
memory: 21168kb
input:
1000 975 633065 7087 25267 3940676 618039 1695 2043 728466935 3498 13604984 4 99 119488 151315 12 32 52705062 26815 1902279 33952 480604 390647001 60 1 12566875 7591859 6 119892 7829822 2129 4 11644639 17 33200 5330 338 2 9 6862 3781 148087 57 198 13224999 10493180 1 5755424 216 1757297 210 1002623 ...
output:
35467198613 671056390
result:
ok 2 tokens
Test #5:
score: 0
Accepted
time: 30ms
memory: 31316kb
input:
99988 19981 11771832 114 110908254 348 553453 840525742 342620766 12408 27914 2 29 4914992 79461083 133 0 44575 11059027 13445407 3508312 227 50410231 1253800 12277 201525297 39 88 20236754 417742 0 8412502 172886086 35315 144742219 211319 352393 10445 1330114 56814394 90807971 3 69704 104497 0 9176...
output:
3435071736287 430589528
result:
ok 2 tokens
Test #6:
score: 0
Accepted
time: 8ms
memory: 20008kb
input:
1000 1 275655344 268458939 268461191 268677493 268927841 297911693 268483017 269854162 282115927 398697060 270400289 268437312 268466898 268435457 268435467 291748742 268564621 268453835 269779105 268693603 268435666 386584345 268451187 268435457 268442250 268437405 268444979 268435461 268435461 268...
output:
0 1
result:
ok 2 tokens
Test #7:
score: 0
Accepted
time: 4ms
memory: 19924kb
input:
1000 3 14805621 496 64344582 2 2114 6 393783989 7458616 0 1362 55976 126045279 108353345 20049189 44 95 437 745121320 88093 3 405373757 6238 45971 1341575 1 121 2946771 15902 7578234 164 1 429590578 6739 27643 38 11 231 78030263 55 1983150 163716760 906563 446949 1 586409 3 420 2 85423631 4 73606102...
output:
1935584369 6
result:
ok 2 tokens
Test #8:
score: 0
Accepted
time: 12ms
memory: 21108kb
input:
999 953 2750440 111153032 5897842 4179 155767 26 1217 10613 33021973 2364 606 1039 2 25708532 44356 2731336 8131509 11 47 3374 10217 864014889 1335035 1626 6 1662 1926995 1413154 617430049 169873 21691 22 1157896 43 38228 9499179 1025427 922 1873902 2254 514565 13064 187 49 65341 289382656 262263674...
output:
32779801402 323536229
result:
ok 2 tokens
Test #9:
score: 0
Accepted
time: 11ms
memory: 20760kb
input:
1000 643 625292105 664789381 501359 59390402 3826 1916700 188553 25542353 117 3255788 600392 40389 227 959553533 22576447 21215 337 55920 12494719 69695 1347123 957900536 1582668 1940738 14913866 191 64 237683 6 364 39030728 0 23 3576723 1331 26293699 2 1634 1345 14969765 13 113 13 27624021 644496 1...
output:
35728055254 859009553
result:
ok 2 tokens
Test #10:
score: 0
Accepted
time: 11ms
memory: 20504kb
input:
999 864 53881381 162 296733 6281 464002 9422336 2900839 134930677 790267398 5 4754 13566793 29 3929593 13 8195474 54 43407395 10 126 2107750 6069954 87281283 837636 462057 5 10 31 1783891 5 24688892 18498742 396677 142874288 110426 130150825 5 384815 3908 4 236065713 117 2218343 3804283 182646101 5 ...
output:
31150099421 67557702
result:
ok 2 tokens
Test #11:
score: 0
Accepted
time: 5ms
memory: 21520kb
input:
1000 932 15449702 61147 2927951 459066 114406 6 32 243404061 2346088 1 11431422 5436 457840086 322 1 6 2055572 2855 2 30523 1 510 759314112 2335380 3 7 887 20 29368330 41771322 463238532 247672 45136 279744 499 900 4 2027 3 35 67 247245759 2 48110 7 20 15148 113139830 0 302812 870 2734366 7 11506972...
output:
35119427319 129193269
result:
ok 2 tokens
Test #12:
score: 0
Accepted
time: 7ms
memory: 20316kb
input:
999 821 175 57037 225 50240 440761311 3766393 4 0 39149 2319 137 2926301 1117101 928166927 171266 24745051 101092645 100165465 7500541 30118 1 272 149003 81613 466 47 38756751 3451 96 3554717 473433834 27 6929202 1493 94 9 60972 638981 10 360464986 3586673 297014 1473925 90571774 53723025 390 2214 2...
output:
34107496485 389323593
result:
ok 2 tokens
Test #13:
score: 0
Accepted
time: 7ms
memory: 20180kb
input:
1000 656 258 893 985020 262 259 357043937 13046 269 289 257 415376990 293 303 21349699 264 6332 10986 53635219 5692270 257 282217 356 305 259 845 224403462 3081 244618773 230272 428653671 24934305 6775286 22650461 256 268 13840 366581 5491960 7174525 16099 27964029 225008 2829359 1880 6695852 132239...
output:
30901843021 613472351
result:
ok 2 tokens
Test #14:
score: 0
Accepted
time: 200ms
memory: 20544kb
input:
1000 966 598 7662 16 205599 422 1949160 11388992 4 14538 3265 3620 5312455 3308 1612 835572 317539332 81 2552 316246 8 686 1986 44541 618460472 254488 6557 56495 46240563 6 34795150 2 26223984 1477 57363879 1641 2626735 2831 1 30112 95377571 18341025 552 35054 82685 1639412 117583137 20 1 56010 3381...
output:
30802651637 372287691
result:
ok 2 tokens
Test #15:
score: 0
Accepted
time: 7ms
memory: 20320kb
input:
1000 899 8 12828215 2343611 8 325786 702677184 18093754 16 46 100 1 50 7035 913 1 43761627 823587 854647 30671 234337151 3 100615086 14090819 12 83778 0 10 26 82 9001140 6822279 7299667 132 1658331 35919777 235131974 4 767 191187 395596 4 1086 19100 354 0 6603931 2080312 2 20156 623973 185 54027223 ...
output:
26166543443 367069113
result:
ok 2 tokens
Test #16:
score: 0
Accepted
time: 7ms
memory: 20312kb
input:
999 996 476178 1783726 661 59419724 406020859 493226 9347 28463 14972872 0 1342 11 11 44 512 10681475 471659 70251 17006243 147720596 0 7339279 165038496 46557 236 849 3865900 31738 281018855 266 198 5765667 3686352 6522 728 1 36 135414 334607226 53283797 12949 401252317 160 9634 106189504 2005610 1...
output:
33488159442 820131433
result:
ok 2 tokens
Test #17:
score: 0
Accepted
time: 11ms
memory: 20504kb
input:
1000 833 61741547 20 1905 541 43 1 457 1578 8 127349738 2 2 208249393 182 56972454 3 8 241 28680403 203 12409672 2943367 1316 17 3554982 25476 6738 4733093 385675 3 1604 867 270437 963016775 30551495 479526 1634 75361 861559337 217 255889256 17061659 334602 49 4 1062561 382 12079191 126742 37 6 49 5...
output:
34310887754 147968537
result:
ok 2 tokens
Test #18:
score: 0
Accepted
time: 40ms
memory: 24708kb
input:
99907 2000 134218414 134221684 197183649 148833615 134217740 159844432 134217766 134220587 134217729 134224771 184225248 134328268 134217731 135416787 134218036 134217840 134217761 134217732 136229015 146153653 134246238 134219532 134217730 145300843 134223166 138322294 134217728 134234237 134217745...
output:
1404375175408 100292593
result:
ok 2 tokens
Test #19:
score: 0
Accepted
time: 9ms
memory: 21480kb
input:
9993 1000 34 33007 1007 744921132 212 2166364 1410 18 33 8963 2 69 2 696 128 802262 1059337 3775 697698274 15 569 394503 21987 9863952 119 5344 320 1 434 12662 519300 75058676 18047861 39250 5 11603153 40112395 2724 7554 425 120441 338710978 330 2097 18501 5949 2 33958776 6921713 1 72985988 308 3757...
output:
310503274150 641419708
result:
ok 2 tokens
Test #20:
score: 0
Accepted
time: 29ms
memory: 47332kb
input:
99931 80543 2347 10 50 56008528 11 596158709 10395 286413905 122175137 468751766 97 1204542 497 9 23064694 170235 763 25751387 69 9 20 2069 91379154 1210 119 1188 6130540 65081973 6794794 9 59405 1000403 242408162 8 102 34982 127765 50883 14300889 11 9 344950 11 18142631 10 70 263 104 742 82664067 2...
output:
3455570020385 886983330
result:
ok 2 tokens
Test #21:
score: 0
Accepted
time: 23ms
memory: 26416kb
input:
99939 6997 55 7597854 2397998 272 52263011 1153 1861503 337127 13506549 2 227 283744 1787225 401 348620 0 3175711 5245 9977 11 30231 12 15 476 171675603 3696363 12846 6874713 2686 342676 494718 1 61154779 504 14 192160 74 313 29 418553761 743 5 1526818 64103 20307 230 55549370 1861 397201 34 1 32317...
output:
2739544563076 882365528
result:
ok 2 tokens
Test #22:
score: 0
Accepted
time: 11ms
memory: 20352kb
input:
999 164 445765817 6917 0 553 52 78974 641083 59627 1468 1908 3189250 0 6773 261 15 34343 364156 3 29 15 16636931 340 333 5 288 222916038 22 11 120442 35572 10 428173 896793470 26 2 1 3686 108402 4 4 27623 2 3711595 6 371413699 7319408 482 23 52007 498416506 251 25 1605 8632971 245161066 1451 237076 ...
output:
32578471599 448450838
result:
ok 2 tokens
Test #23:
score: 0
Accepted
time: 19ms
memory: 20192kb
input:
999 933 26405 31 359800 670 140550889 4669381 142122068 1 934047573 9547732 6649102 137620582 1855 1977 1349 31544 0 420 5123 142457 45 50350 763693021 4 7 57088 4049 27297915 5430817 4034276 166232 117589983 55 9545 2 37 635667 5808976 0 15995292 630071 11478 14221 4 23791980 4 189 33433610 6 184 1...
output:
35436857939 298991816
result:
ok 2 tokens
Test #24:
score: 0
Accepted
time: 23ms
memory: 35768kb
input:
99934 29975 770560 89399 27260 242182 89905976 15581 134 2805220 116533212 936363 80 5581 80041 6264 133 258639465 168 231916 892359 26831874 14340332 12 17481 1 3669 1225 14 5764 495 285 199352824 9216 131484 114 33496 506 5564 8 51 33 404 93 1 15732 32 16181 12089637 3169 40855 8280304 50987 3073 ...
output:
3434385418330 579431178
result:
ok 2 tokens
Test #25:
score: 0
Accepted
time: 39ms
memory: 23220kb
input:
99952 70 268435751 268435531 270576547 268435482 268436959 283824170 268435457 268464652 268445320 268442711 268442493 269627235 268554131 268809657 268443317 275399961 280752581 268442184 268435458 345467000 271634930 268468073 268440985 268435491 268449854 271879296 268435553 268498140 268435456 2...
output:
59179530987 108669496
result:
ok 2 tokens
Test #26:
score: 0
Accepted
time: 39ms
memory: 38172kb
input:
99969 39999 233625341 90 454618351 176 3 123 5225863 222 707 25 63971 6286 132629406 5385 1 1765872 164976848 61498 96372467 1919 168 431995 144970 49 205832 1910799 994247 19246332 1 1084 2049 213 7121593 1 537924 7202 545 3225125 1647 200948109 12616 0 292085533 0 185 3338 3767 1 3970 20838 10397 ...
output:
3478238570365 32310564
result:
ok 2 tokens
Test #27:
score: 0
Accepted
time: 8ms
memory: 20552kb
input:
1000 999 0 31595 169 1 923973661 16919 204322 31027 63464902 2 2 3594560 102894 10797961 361407414 2669 779 103402385 409 1 460545591 309866446 217231 166396 957 454681619 922 2382 1086373 1269520 2800 1327 31753 208 260789 899353 2191 8163618 100308849 23 3 1042 2 379779105 10660309 0 29867 2 15311...
output:
35946467742 784167957
result:
ok 2 tokens
Test #28:
score: 0
Accepted
time: 14ms
memory: 20140kb
input:
9990 25 937024 656593 93 996249 96201492 111049 70171 3820507 9 6528 2570576 8567 37452 6 25245434 218349 7068 1546 769 756095650 3801 3 111 140012 61282407 3751 21053800 2 110476486 1488287 1 344 0 112 7 1508 122 1249 30 1 717541 7693031 91166785 1473873 26 504301 324695921 299552 22102358 89815280...
output:
23248381982 440732388
result:
ok 2 tokens
Test #29:
score: 0
Accepted
time: 187ms
memory: 20468kb
input:
1000 952 1 467357 370612 119 16 1174684 8430 102 8251196 12399 204 8 8088350 598341 11 58004 858456 15153 0 10409893 86042 4105854 57027 86414773 16 15 9656176 1 44467684 2 2 308287 15 10004909 214899657 5917 31310 29354653 30 2542 14778864 5 226563677 52289218 0 15721 12 254494 778 89010 27870935 4...
output:
35399197883 64703191
result:
ok 2 tokens
Test #30:
score: -100
Time Limit Exceeded
input:
99938 95599 4 87 41 25967175 13584439 17117487 2302 395268 14354 4048085 2833 3633 348602 33163677 7735 125868899 28021280 8173703 281368 3 161361 19395954 226256 405 114 38060 2 30 3101146 197010170 3842 285632564 560 24404967 2014799 3732 8616628 2 7885871 1633 32 4 33301954 729 22 1448 666 13 930...