E - Or Plus Max
已知数组 \(a\), \(i|j≤k\) 求 \(max(a_i+a_j)\).
枚举 \(k\), SOSDP 处理 \(k\) 的二进制子集中最大值和次大值.
最后循环输出最大值与次大值之和即可.
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();
const int D = 20;
const int N = 1 << D;
const int M = N - 1;
array<int, 2> f[N];
int main() {
int n;
cin >> n;
n = 1 << n;
for (int i = 0 ; i < n ; i++) {
cin >> f[i][0];
f[i][1] = 0x7fffffff + 1;
}
for (int i = 0 ; i < D ; i++) {
for (int mask = 0 ; mask < n ; mask++) {
if (mask & 1LL << i) {
auto x = f[mask];
auto y = f[mask ^ 1LL << i];
if (x < y) swap(x, y);
x[1] = max(x[1], y[0]);
f[mask] = x;
}
}
}
int ans = 0;
for (int i = 1 ; i < n ; i++) {
ans = max(ans, f[i][0] + f[i][1]);
cout << ans << "\n";
}
return 0;
}
|
Problem - F - Codeforces
已知 \(i<j<k\) 求 \(max(a_i|(a_j\&a_k))\)
以 \(f_{i,j}\) 表示为 二进制为 \(i\) 的第 \(j\) 小的下标, 因为这里只有 \(a_j\&a_k\) 所以只需要最小的 \(2\) 个值.
然后做子集前缀和, 最后从小到大枚举 \(i\), 再大到小枚举 \(a_i\) 二进制为 \(0\) 的位, 检查是否存在 \(a_j\&a_k\) 的这一位为1.
答案取 \(max(a_i|(a_j\&a_k))\)
代码
| C++ |
|---|
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();
const int B = 21;
const int N = 1 << B;
const int M = N - 1;
array<int, 2> f[N];
int a[N];
void add(int x, int val) {
if (val > f[x][0]) {
swap(val, f[x][0]);
}
if (val > f[x][1]) {
swap(val, f[x][1]);
}
}
int main() {
int n;
cin >> n;
fill(f, f + N + 1, array<int, 2>{-1, -1});
for (int i = 1 ; i <= n ; i++) {
cin >> a[i];
add(a[i], i);
}
for (int i = 0 ; i < B ; i++) {
for (int mask = 0 ; mask <= M ; mask++) {
if (mask & 1LL << i) {
add(mask ^ 1LL << i, f[mask][0]);
add(mask ^ 1LL << i, f[mask][1]);
}
}
}
int ans = 0;
for (int i = 1 ; i <= n - 2 ; i++) {
int res = 0;
for (int j = B - 1 ; j >= 0 ; j--) {
if (a[i] & 1LL << j) continue;
if (f[res ^ 1LL << j][1] > i) {
res ^= 1LL << j;
}
ans = max(ans, res | a[i]);
}
}
cout << ans << "\n";
return 0;
}
|
F - Subsequence LCM (atcoder.jp)
\(n\) 个数(\(1\leq a_i\leq10^{16}\)), 问有多少个子序列满足 \(lcm=m\)。
先考虑 \(m=1\)，此时答案为 \(2^k-1\)，\(k\) 为 \(a_i=1\) 的个数。
然后 \(m>1\)，\(10^{16}\) 最多是 \(15\) 个不同的质数的乘积。
所以我们可以考虑处理 \(a_i\)。
如果 \(cnt_j(a_i)=cnt_j(m)\)，则二进制第 \(j\) 位为1。
如果 \(cnt_j(a_i)>cnt_j(m)\)，则 \(a_i\) 没有贡献。
如果 \(cnt_j(a_i)<cnt_j(m)\)，则说明可选可不选，二进制第 \(j\) 位为0。
通过 SOSDP 可以求得子集前缀和，然后通过子集反演，容斥出恰好每个质因数都满足条件的个数。
代码
| C++ |
|---|
| using i64 = long long;
const i64 P = 998244353;
i64 qpow(i64 a, i64 b = P - 2, i64 res = 1) {
while (b) {
if (b & 1) res = res * a % P;
a = a * a % P;
b >>= 1;
}
return res;
}
i64 dp[1 << 16];
int main() {
int n;
cin >> n;
i64 m;
cin >> m;
vector<i64> a;
vector<pair<i64, int>> prime;
i64 temp = m;
for (i64 i = 2 ; i * i <= temp ; i++) {
if (temp % i == 0) {
int cnt = 0;
while (temp % i == 0) {
temp /= i;
cnt++;
}
prime.push_back({i, cnt});
}
}
if (temp > 1) {
prime.push_back({temp, 1});
}
for (int i = 0 ; i < n ; i++) {
i64 a;
cin >> a;
if (m % a != 0) continue;
int res = 0;
bool flag = true;
for (int j = 0 ; j < (int) prime.size() ; j++) {
int cnt = 0;
while (a % prime[j].first == 0) {
a /= prime[j].first;
cnt++;
}
if (cnt > prime[j].second) {
flag = false;
break;
}
if (cnt == prime[j].second) {
res |= 1 << j;
}
}
if (flag && a == 1) {
dp[res]++;
}
}
if (m == 1LL) {
cout << (qpow(2, dp[0]) - 1 + P) % P << "\n";
return 0;
}
int k = prime.size();
for (int i = 0 ; i < k ; i++) {
for (int mask = 0 ; mask < 1 << k ; mask++) {
if (mask & 1 << i) {
dp[mask] = (dp[mask ^ 1 << i] + dp[mask]) % P;
}
}
}
i64 ans = 0;
for (int i = 0 ; i < 1 << k ; i++) {
dp[i] = qpow(2, dp[i]);
ans = (ans + ((k - __builtin_popcount(i)) & 1 ? P - 1 : 1) * dp[i] % P) % P;
}
cout << ans;
return 0;
}
|