题解：T496174 「金坷垃杯 R1」子集数量

还是计数问题。

前面 说过了，计数问题不是搜索、dp，就是数学方法。

其实这个题就是个数学题（题目背景不是说了吗）。我们可以先搜，找找规律。令去重（显然可以用个 set）后的元素个数为 ，打表也可以发现子集数量就是 。

为什么呢？

因为集合中每个元素在子集当中都只有出现 / 不出现两种可能，根据乘法原理就可以推出来了。

所以只需要写一个快速幂解决问题（ps：快速幂这东西多少年没考了……）。

那该如何计算其它的值呢？非空子集数量就是集合中去掉了一个，所以答案是 ，真子集同理，非空真子集两个都去掉了就是 。

现在的问题就是取余之后万一是 呢？

注意到余数有可加性、可减性和可乘性，我们统一对其加上 余数不变，这个时候去减是减的动的，最后输出的时候再模回去就可以了。

---

std：

/*Code by Leo2011*/
#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define EPS 1e-8
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
#define log printf
#define IOS                      \
	ios::sync_with_stdio(false); \
	cin.tie(nullptr);            \
	cout.tie(nullptr);

using namespace std;

typedef long long ll;
typedef __int128 i128;

ll p, t, ans;
set<ll> st;

template <typename T>

inline T read() {
	T sum = 0, fl = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar())
		if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}

template <typename T>

inline void write(T x) {
	static T sta[35];
	int top = 0;
	do { sta[top++] = x % 10, x /= 10; } while (x);
	while (top) putchar(sta[--top] + 48);
}

ll power(ll x, ll y) {
	if (y == 1) return x % p;
	ll ret = power(x, y >> 1) % p;
	ret = ret * ret, ret %= p;
	if (y % 2) ret *= x, ret %= p;
	return ret % p;
}

int main() {
	cin >> p;
	while (cin >> t) st.insert(t);

	cout << st.size() << '\n';

	ans = power(2, st.size()) + p; // 公式
	cout << ans % p << '\n';

	--ans;
	cout << ans % p << '\n';

	cout << ans % p << '\n';

	--ans;
	cout << ans % p << '\n';
	return 0;
}

upd1：赛时突然发现 std 和数据的 generator 都 TM 写挂了，已更正。以后再也不敢出题不验题、不写数据的 chekcer 了。

upd2：本题必须要使用快速幂，直接位运算相当于计算 ，肯定会原地爆炸，因此需要慢慢取模。赛时有一个大哥就因为这一点和没开 long long 导致正解变 50。什么破毒瘤题。