首页 > 其他分享 >ARC146C

ARC146C

时间:2022-09-30 13:34:17浏览次数:48  
标签:int 元素 个数 合法 异或 ARC146C mod

若 \(S\) 合法,则首先这个条件显然等同于没有一个 \(S\) 的非空子集满足元素个数为偶数且元素异或和为 \(0\)。
对于一个满足条件的 \(S\),我们能加入哪些非负数使得条件仍然满足呢?
设 \(T\) 是 \(S\) 的一个元素个数为奇数的子集,令 \(x\) 为 \(T\) 中元素异或和。那么显然,\(x\) 是不能被加入 \(S\) 中的。
然后接下来是最关键的性质,对于一个合法的 \(S\),如果 \(T,U\) 均是 \(S\) 的一个元素个数为奇数的子集,且 \(T,U\) 不同,那么 \(T,U\) 中元素异或和也不同。
证明:若两者元素异或和相同,那么这样一个集合(由只存在于 \(T\) 中的元素和只存在于 \(U\) 中的元素组成的集合)必然满足元素个数为偶数且异或和为 \(0\)。而这个集合显然是 \(S\) 的非空子集,这与 \(S\) 合法矛盾。
因此,对于所有合法的 \(S\),能加进 \(S\) 且依然合法的非负元素数量为 \(2^N-\) \(S\) 的元素个数为奇数的非空子集的数量。
于是可以 DP 了。
设 \(f_i\) 表示元素数量为 \(i\) 的合法 \(S\) 数量。
初值为 \(f_0=1,f_1=2^N\)。
转移为 \(f_i=\frac{f_{i-1}\ \ \ \times\ \ \ (2^N\ -\ 2^{i\ -\ 2}\ \ \ )}{i}(i\ge2)\)。
除以 \(i\) 是因为集合是无序的。
而且通过上述转移,可以发现不存在元素个数超过 \(N+1\) 的合法的集合。
时间复杂度为 \(\mathcal O(N)\) 或 \(\mathcal O(N\log N)\),取决是否预处理逆元。

Code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N = 100005, mod = 998244353;
int n;
int ans;

int qpow(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}

int inv(int x) { return qpow(x, mod - 2); }

signed main() {
	scanf("%lld", &n);
	ans = 1; ll now = qpow(2, n);
	ans = (ans + now) % mod;
	for (int i = 2; i <= n + 1; ++i) {
		now = now * (qpow(2, n) - qpow(2, i - 2) + mod) % mod * inv(i) % mod;
		ans = (ans + now) % mod;
	}
	printf("%lld", ans);
	return 0;
}

标签:int,元素,个数,合法,异或,ARC146C,mod
From: https://www.cnblogs.com/Kobe303/p/16744614.html

相关文章

  • ARC146C Even XOR(线性基,组合)
    ARC146CEvenXOR有多少集合\(S\),每个元素都在\([0,2^N)\)之间,且所有偶数大小的子集的异或和不为\(0\)。CODE奇数大小的子集\(\oplus\)和可以为\(0\),可是如果......