集合专练？？？？？逆天！！！！！！！

T1 卷

逆天！！！！！！！！！！！！！！！！！！！！又没看懂题。独立集指集合里的每个点不相连呜呜呜呜呜，我还以为是剩下的点互不相连，直接寄掉。

式子好推，就不推了，咕。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#define mod 1000000007

using namespace std;

long long n, w[5211314 >> 3], beg;
long long cnt, head[5211314 >> 3], nex[5211314 >> 3], to[5211314 >> 3];
long double comp = 1, val[5211314 >> 3], dp_log[5211314 >> 3][2];
long long dp[5211314 >> 3][2];

inline void AddPoi(int v1, int v2) {
	cnt ++;
	nex[cnt] = head[v1];
	head[v1] = cnt;
	to[cnt] = v2;
	return;
} 

void DFS(int fa, int now) {
	dp_log[now][1] = val[now];
	dp[now][1] = w[now];
	for (int i = head[now]; i != 0; i = nex[i]) {
		if (to[i] != fa) {
			DFS(now, to[i]);
			if (dp_log[to[i]][0] > dp_log[to[i]][1]) {
				dp_log[now][0] += dp_log[to[i]][0];
				dp[now][0] = dp[now][0] * dp[to[i]][0] % mod;
			}
			else {
				dp_log[now][0] += dp_log[to[i]][1];
				dp[now][0] = dp[now][0] * dp[to[i]][1] % mod;
			}
			dp_log[now][1] += dp_log[to[i]][0];
			dp[now][1] = dp[now][1] * dp[to[i]][0] % mod;
		}
	}
	//dp式子好推，就不多BB了 
	return;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; ++ i) {
		dp[i][0] = 1;
	}
	for (long long i = 1; i <= n; ++ i) {
		cin >> w[i];
		val[i] = log(w[i]);
		//一定要记住啊啊啊啊啊啊啊啊，乘法就转换成log的加 
	}
	for (long long i = 1; i <= n - 1; ++ i) {
		long long u, v;
		cin >> u >> v;
		AddPoi(u, v), AddPoi(v, u);
	}
	DFS(1, 1);
	//记得判断QAQ 
	if (dp_log[1][0] > dp_log[1][1]) {
		cout << dp[1][0] << endl;
	}
	else {
		cout << dp[1][1] << endl;
	}
	return 0;
}

T2 简单题

确实够简单奥。。。。。

将每个是双倍的点连边，判断链长，处理，咕

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define mod 10000019

using namespace std;
typedef long long ll;

ll base[67], n ,q, basic, m, fac[5211314 << 1], inv[5211314 << 1];
ll sum1, sum2;

inline ll QuickPower(ll a, ll k) {
	ll base = a, ans = 1;
	while (k != 0) {
		if (k & 1 == 1) {
			ans = ans * base % mod;
		}
		base = base * base % mod;
		k >>= 1;
	}
	return ans;
}

inline ll GetInv(ll x) {
	if (x == 1 || x == 0) return 1;
	return (mod - mod / x) * (GetInv(mod % x)) % mod;
}

inline ll GetC(ll a, ll b) {
	if (a < b) return 0;
	else return (fac[a] * GetInv(fac[a - b])) % mod * GetInv(fac[b]) % mod;
}

ll Lucas(ll a, ll b) {
	if (b == 0)  {
		return 1;
	}
	return Lucas(a / mod, b / mod) * GetC(a % mod, b % mod) % mod;
}

int main() {
	scanf("%lld%lld", &n, &q);
	fac[0] = 1;
	for (ll i = 1; i <= mod; ++ i) {
		fac[i] = fac[i - 1] * i % mod;
	}
	base[0] = 1;
	for (ll i = 1; i <= 60; ++ i) {
		base[i] = base[i - 1] * 2 % (int)4e18;
	}
	double k = log(n)/log(2);
	for (ll i = 0 ; i <= k; ++ i) {
		ll l = n / base[i + 1], r = n / base[i], temp;
		l += 1;
		if (l % 2 == 1) {
			temp = (r - l) / 2 + 1;
		}
		else if (l % 2 == 0) {
			if (r % 2 == 1) temp = (r - l) / 2 + 1;
			else temp = (r - l) / 2;
		}
		basic += (i + 1) / 2 * temp;
		if ((i + 1) % 2 == 0) {
			sum1 += temp;
		}
		else {
			sum2 += temp;
		}
	}
	while (q --) {
		scanf("%lld", &m);
		if (m < basic) cout << 0 << endl;
		else {
			cout << QuickPower(2, sum1) % mod * Lucas(sum2, m - basic) % mod << endl;
		}
	}
	return 0;
} 

T3 粉丝

在取的数中，每次可做的操作有两种：

1. 插入\(\sqrt{n}\)
2. 将所有选的数都加一

这样就保证了每种选择方式都能出现，如我们要找 \(\sqrt{n}\) 和 \(\sqrt{n}+3\) 的排列，则可以先插入 \(\sqrt{n}\) 再加两次 \(1\) 然后插一次 \(\sqrt{n}\) 就行

逆天根号分治，总之就是不太会就对了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define mod 10000019

using namespace std;
typedef long long ll;

ll base[67], n ,q, basic, m, fac[5211314 << 1], inv[5211314 << 1];
ll sum1, sum2;

inline ll QuickPower(ll a, ll k) {
	ll base = a, ans = 1;
	while (k != 0) {
		if (k & 1 == 1) {
			ans = ans * base % mod;
		}
		base = base * base % mod;
		k >>= 1;
	}
	return ans;
}

inline ll GetInv(ll x) {
	if (x == 1 || x == 0) return 1;
	return (mod - mod / x) * (GetInv(mod % x)) % mod;
}

inline ll GetC(ll a, ll b) {
	if (a < b) return 0;
	else return (fac[a] * GetInv(fac[a - b])) % mod * GetInv(fac[b]) % mod;
}

ll Lucas(ll a, ll b) {
	if (b == 0)  {
		return 1;
	}
	return Lucas(a / mod, b / mod) * GetC(a % mod, b % mod) % mod;
}

int main() {
	scanf("%lld%lld", &n, &q);
	fac[0] = 1;
	for (ll i = 1; i <= mod; ++ i) {
		fac[i] = fac[i - 1] * i % mod;
	}
	base[0] = 1;
	for (ll i = 1; i <= 60; ++ i) {
		base[i] = base[i - 1] * 2 % (int)4e18;
	}
	double k = log(n)/log(2);
	for (ll i = 0 ; i <= k; ++ i) {
		ll l = n / base[i + 1], r = n / base[i], temp;
		l += 1;
		if (l % 2 == 1) {
			temp = (r - l) / 2 + 1;
		}
		else if (l % 2 == 0) {
			if (r % 2 == 1) temp = (r - l) / 2 + 1;
			else temp = (r - l) / 2;
		}
		basic += (i + 1) / 2 * temp;
		if ((i + 1) % 2 == 0) {
			sum1 += temp;
		}
		else {
			sum2 += temp;
		}
	}
	while (q --) {
		scanf("%lld", &m);
		if (m < basic) cout << 0 << endl;
		else {
			cout << QuickPower(2, sum1) % mod * Lucas(sum2, m - basic) % mod << endl;
		}
	}
	return 0;
} 

总结

T1从第一次到现在就没读过懂题，但暴力总能骗一骗，总是出现能有正解思路但不知道接下来怎么做的情况。