2024/10/2 CSP-S daimayuan
contest link (Day 7)
A. 序列
题面描述
给你一个序列 \(r_1,r_2,\dots,r_n\)，问有多少非负整数序列 \(x_1,x_2,\dots,x_n\) 满足：
对于所有 \(i\)，\(0 \leq x_i \leq r_i\)。
满足 \(x_1|x_2|…|x_n=x_1+x_2+⋯+x_n\)，左边为二进制或。
输出答案对 \(998244353\) 取模的结果。
输入 & 输出 & 样例 & 数据范围
输入第一行一个整数 \(n\)。
接下来一行，一共 \(n\) 个整数 \(r_1,r_2,\dots,r_n\)。
输出一个整数，表示答案。
对于所有数据，保证 \(1 \leq n \leq 16,0 \leq ri < 260\)。
5
1 2 3 4 5
思路解析
首先考虑将那个按位或的条件转换一下，可以得到条件等价于要求对于所有的 \((i,j)\) 都有 \(x_i \& x_j=0\)，相当于我们查看所有 \(x\) 的第 \(k\) 位，只有一个或没有 \(x\) 在当前位上为 \(1\)。有这种想法后我们就可以想数位 dp，但是在二进制数位下。我们在常规的数位 dp 下需要记录是否有顶头，这里同理，但是需要记录 \(n\) 个元素的信息，因为 \(n\) 的范围较小，用状压存储即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 18, M = 64;
const ll P = 998244353;
ll n, r[N], f[2][1 << N];
int g(ll x, int y) {return (x >> y) & 1;
}
int main() {cin >> n;for(int i = 1; i <= n; i++) cin >> r[i];f[63 & 1][0] = 1;for(int i = 62; i >= 0; i--) {for(int j = 0; j < (1 << n); j++) f[i & 1][j] = 0;for(int j = 0; j < (1 << n); j++) {int tmp = 0;for(int k = 1; k <= n; k++) {if(g(j, k - 1) || g(r[k], i)) tmp += (1 << (k - 1));}f[i & 1][tmp] += f[(i + 1) & 1][j];for(int k = 1; k <= n; k++) {int top = ((g(j, k - 1) || g(r[k], i)) ? 1 : 0);if(g(j, k - 1) || g(r[k], i)) {int now = ((tmp ^ (1 << (k - 1))) | ((g(j, k - 1)) << (k - 1)));f[i & 1][now] += f[(i + 1) & 1][j]; f[i & 1][now] %= P;}}}}ll ans = 0;for(int j = 0; j < (1 << n); j++) ans = (ans + f[0][j]) % P;cout << ans;return 0;
}
B. 合并数字
题面描述
有 \(n\) 个数字，\(a_1,a_2,\dots,a_n\)。每次可以选择两个数字 \(x,y\) 删除，然后加入数字 \(K−x−y\)。\(n−1\) 轮之后只剩下一个数字，问最后剩下的数字最大可能是多少？
你要对 \(q\) 个不同的 \(K\) 进行回答。每组询问独立，都是对于一开始的序列操作。
输入第一行两个整数 \(n,q\)。
接下来一行 \(n\) 个整数 \(a_1,a_2,\dots,a_n\)。
接下来一行 \(q\) 个整数 \(K_1,K_2,\dots,K_q\)，表示每次询问的值。
输出一共 \(q\) 行，每行一个整数，表示答案。
