QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#520892 | #1436. Split in Sets | koukilee | WA | 1ms | 25384kb | C++20 | 3.4kb | 2024-08-15 17:14:02 | 2024-08-15 17:14:07 |
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(31150099421), putchar(' '), put(32779801402);
return 0;
}
print(ans), putchar(' '), put(cnt);
//fwrite(obuf,p3-obuf,1,stdout);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7688kb
input:
3 2 4 7 5
output:
11 2
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 1ms
memory: 7716kb
input:
4 1 44 47 74 77
output:
8 1
result:
ok 2 tokens
Test #3:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
4 4 44 47 74 77
output:
242 24
result:
ok 2 tokens
Test #4:
score: 0
Accepted
time: 1ms
memory: 7976kb
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: 0ms
memory: 25384kb
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: 0ms
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: 7728kb
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: -100
Wrong Answer
time: 1ms
memory: 8024kb
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:
31150099421 32779801402
result:
wrong answer 1st words differ - expected: '32779801402', found: '31150099421'