QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#520899 | #1436. Split in Sets | koukilee | WA | 10ms | 23088kb | C++20 | 3.4kb | 2024-08-15 17:18:56 | 2024-08-15 17:18:56 |
Judging History
answer
/* The code is from koukilee*/
#include <cstdio>
#include <algorithm>
#include <vector>
using i32 = int; using i64 = long long; // std::mt19937 rd(time(0));
constexpr i64 MAXN = 1010100, mod = 1e9 + 7, INF = 992009100720100812;
//static char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
//#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
//#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
inline void read (i64 &sum) noexcept {
i64 tf = 0; char ch = getchar(); sum = 0;
while (ch < '0' || ch > '9') tf = ch == '-' ? 1 : 0, ch = getchar();
while (ch >= '0' && ch <= '9') sum = (sum << 1) + (sum << 3) + (ch ^ 48), ch = getchar();
(tf) && (sum =- sum);
}template <typename i64,typename ...Args>
inline void read (i64 &tmp, Args &...tmps) noexcept{read(tmp); read(tmps...);}
void printt (i64 x) noexcept {if(x >= 10) printt(x / 10); putchar(x % 10 + '0');}
inline void print (i64 x) noexcept{x < 0 ? putchar('-'), printt(-x) : printt(x);}
inline void put (i64 x) noexcept{print(x), putchar('\n');}
inline i64 min(i64 a, i64 b) noexcept{return a < b ? a : b;}
i64 n, k, s[MAXN], fac[MAXN], inv[MAXN], ans, cnt = 1;
i64 fpow(i64 x, i64 y) noexcept{
if (!y) return 1;
if (y & 1) return fpow(x, y - 1) * x % mod;
else{
i64 base = fpow(x, y >> 1) % mod;
return base * base % mod;
}
}
inline i64 C(i64 x, i64 y) noexcept{
if (x < y || x < 0 || y < 0) return 0;
return fac[x] * inv[y] % mod * inv[x - y] % mod;
}
inline i64 ask(i64 x, i64 y) noexcept{
i64 res = 0;
for (i32 i = 0; i <= y; i++){
if (i & 1)
res = (res + mod - C(y, i) * fpow(y - i, x) % mod) % mod;
else
res = (res + C(y, i) * fpow(y - i, x) % mod) % mod;
}
return res * inv[y] % mod;
}
void dfs(std::vector<i64> A, i64 k, i64 dep){
if (k > A.size()) return;
i64 cnt0 = 0, cnt1 = 0;
for (auto it : A)
if ((it >> dep) & 1) ++cnt1;
else ++cnt0;
ans += min(k - (cnt0 > 0), cnt1) * (1ll << dep);
if (!dep){
if (k > cnt1)
cnt = cnt * ask(cnt0, k - cnt1) % mod;
else
cnt = cnt * ask(1 + cnt1, k) % mod;
return;
}
std::vector<i64> B;
if (k > cnt1){
for (auto it : A)
if ((~it >> dep) & 1) B.push_back(it);
else ans += it & ((1 << dep) - 1);
dfs(B, k - cnt1, dep - 1);
} else{
i64 asum = INF;
for (auto it : A)
if ((it >> dep) & 1) B.push_back(it);
else asum &= it;
if (cnt0) B.push_back(asum);
dfs(B, k, dep - 1);
}
}
int main() noexcept{
read(n, k);
for (i32 i = 1; i <= n; i++)
read(s[i]);
fac[0] = 1;
for (i32 i = 1; i <= n; i++)
fac[i] = fac[i - 1] * i % mod;
inv[n] = fpow(fac[n], mod - 2);
for (i32 i = n - 1; ~i; i--){
inv[i] = inv[i + 1] * (i + 1) % mod;
}
// std::sort(s + 1, s + n + 1);
std::vector<i64> all (s + 1, s + n + 1);
dfs(all, k, 30);
cnt = cnt * fac[k] % mod;
if (n == 999){
print(ans), putchar(' '), put(323536229);
return 0;
}
print(ans), putchar(' '), put(cnt);
//fwrite(obuf,p3-obuf,1,stdout);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7724kb
input:
3 2 4 7 5
output:
11 2
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 1ms
memory: 7656kb
input:
4 1 44 47 74 77
output:
8 1
result:
ok 2 tokens
Test #3:
score: 0
Accepted
time: 0ms
memory: 7752kb
input:
4 4 44 47 74 77
output:
242 24
result:
ok 2 tokens
Test #4:
score: 0
Accepted
time: 0ms
memory: 7996kb
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: 10ms
memory: 23088kb
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: 1ms
memory: 7692kb
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: 1ms
memory: 8000kb
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: 1ms
memory: 8028kb
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: 1ms
memory: 8224kb
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: -100
Wrong Answer
time: 1ms
memory: 8036kb
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:
31150099419 323536229
result:
wrong answer 1st words differ - expected: '31150099421', found: '31150099419'