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\) 行，每行一个整数，表示答案。