目录
写在前面
比赛地址：https://codeforces.com/contest/1957。
大病场妈的
A
签到。
尽可能凑三角形。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
int n; std::cin >> n;
int cnt[110] = {0};
for (int i = 1; i <= n; ++ i) {
int a; std::cin >> a;
++ cnt[a];
}
int ans = 0;
for (int i = 1; i <= 100; ++ i) {
if (cnt[i] >= 3) ans += cnt[i] / 3;
}
std::cout << ans << "\n";
}
return 0;
}
B
构造。
首先特判 \(n=1\)。
对于 \(n\ge 2\)，仅需构造：
\[\begin{cases} a_1 &= 2^{\left\lfloor\log_2 k\right\rfloor} - 1\\ a_2 &= k - a_1\\ a_i &= 0 (3\le i\le n) \end{cases}\]此时 \(a_1 | a_2 | \cdots | a_n\) 中 1 的个数取到上界 \(\log_2 k\)。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int ans[kN];
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
int n, k; std::cin >> n >> k;
if (n == 1) std::cout << k << "\n";
else {
int l = log2(k);
std::cout << (1 << l) - 1 << " " << k - (1 << l) + 1 << " ";
for (int i = 3; i <= n; ++ i) std::cout << 0 << " ";
std::cout << "\n";
}
}
return 0;
}
C
组合数学。
妈的 DP 假了。
放棋子等价于删去矩阵中棋子所在的一行一列。于是根据读入的 \(k\) 步先预处理出矩阵还剩下几行几列可填。然后考虑如何求得 \(n\times n\) 的空矩阵的方案数 \(f_n\)。
直觉是考虑每步白棋放在什么位置，然后通过 \(f_{n - 1}\) 与 \(f_{n - 2}\) 递推求解。然而发现方案数与放置顺序无关，若直接 DP 会难以处理重复的局面。但是发现仅有白棋可能会出现在 \(r=c\) 的位置，考虑白棋每步放置的位置，则最终局面可看做选出 \(x\) 个 \(r=c\) 的位置，再选出 \(\frac{n-x}{2}(2 | n-x)\) 个位置来放置白棋的方案数。于是考虑组合意义：
对于 \(0\le x\le n, 2 | n - x\)，可看做先从矩阵中选出 \(x\) 个 \(r=c\) 的位置，然后依次从 \((n-x)\times (n - x), (n - x -2)\times (n - x - 2), \cdots, 2\times 2\) 的矩阵中选出一个 \(r\not=c\) 的位置，操作之间是无序的，则其对答案的贡献为：
\[{{n}\choose{x}}\times \frac{(n - x)(n-x-1)\times (n - x-2)(n-x-3)\times \cdots }{\left(\frac{n-x}{2}\right)!} \]递推求上式右侧即可。
又本题钦定了 \(\sum n\le 3\times 10^5\)，于是对每组数据都直接套用上述组合意义式大力枚举求解 \(f_n\) 即可。
总时间复杂度 \(O(\sum (n + k))\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 3e5 + 10;
const int lim = 3e5;
const LL p = 1e9 + 7;
//=============================================================
LL fac[kN];
//=============================================================
void Init() {
fac[0] = fac[1] = 1;
for (int i = 2; i <= lim; ++ i) {
fac[i] = fac[i - 1] * i % p;
}
}
LL qpow(LL x_, LL y_) {
LL ret = 1;
while (y_) {
if (y_ & 1) ret = ret * x_ % p;
x_ = x_ * x_ % p, y_ >>= 1ll;
}
return ret;
}
LL C(LL n_, LL m_) {
if (m_ > n_) return 0;
return fac[n_] * qpow(fac[m_], p - 2) % p * qpow(fac[n_ - m_], p - 2) % p;
}
LL Solve(int n_) {
LL ret = 1, s = 1;
for (int i = 2; i <= n_; i += 2) {
s = 1ll * (1ll * i * i - i) % p * s % p;
LL delta = C(n_, n_ - i) * s % p * qpow(fac[i / 2], p - 2) % p;
ret += delta, ret %= p;
}
return ret;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
Init();
int T; std::cin >> T;
while (T --) {
int n, k; std::cin >> n >> k;
for (int i = 1; i <= k; ++ i) {
int x, y; std::cin >> x >> y;
if (x != y) n -= 2;
else n -= 1;
}
std::cout << Solve(n) << "\n";
}
return 0;
}
D
位运算。
感觉比 C 简单呃呃，可能太套路了。
拆一下这个式子，等价于求三元组 \((x, y, z)(x\le y\le z)\) 满足：
\[\left(\bigoplus_{x\le i\le z} a_i \right)\oplus a_y > \left(\bigoplus_{x\le i\le z} a_i \right) \]异或等价于选择一些位置将它们翻转，则上式成立等价于 \(a_y\) 二进制中最高位的 1（即 \(\left\lfloor \log_2 a_y \right\rfloor\) 位）在 \(\left(\bigoplus_{x\le i\le z} a_i \right)\) 中为 0，则只需检查 \(a_x\sim a_z\) 所有数二进制该位为 1 的数的数量是否为偶数。考虑枚举位置 \(y\)，求合法三元组的数量即求满足条件的区间 \([x, z]\) 的数量。考虑将区间转化为整个数列删去一个前缀删去一个后缀，则仅需考虑整个数列，以及选择的前后缀中该位为 1 的数的奇偶性即可。
考虑预处理 \(\operatorname{pre}_{i, j, 0/1}\) 表示前缀 \(0 \sim 0, 0\sim 1, 0\sim 2, \cdots 0\sim i\) 中，它们的第 \(j\) 位中 1 的个数为偶数/奇数的前缀的个数，同理可预处理 \(\operatorname{suf}_{i, j, 0/1}\) 表示后缀 \(n + 1\sim n + 1, n\sim n + 1, \cdots i\sim n + 1\) 中，它们的第 \(j\) 位中 1 的个数为偶数/奇数的后缀的个数。则有：
- 若整个数列第 \(k = \left\lfloor \log_2 a_y \right\rfloor\) 位为 1 的数量为奇数，则贡献为 \(\operatorname{pre}_{y - 1, k, 0}\times \operatorname{suf}_{y + 1, k, 1} + \operatorname{pre}_{y - 1, k, 1}\times \operatorname{suf}_{y + 1, k, 0}\)。
- 若整个数列第 \(k = \left\lfloor \log_2 a_y \right\rfloor\) 位为 1 的数量为偶数，则贡献为 \(\operatorname{pre}_{y - 1, k, 0}\times \operatorname{suf}_{y + 1, k, 0} + \operatorname{pre}_{y - 1, k, 1}\times \operatorname{suf}_{y + 1, k, 1}\)。
枚举每位预处理 \(\operatorname{pre}\) 与 \(\operatorname{suf}\)，然后枚举 \(1\le y\le n\) 通过上式计算贡献即可。
总时间复杂度 \(O\left(\sum n\log v\right)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, a[kN];
int cntpre[40][kN];
int pre[40][kN][2], suf[40][kN][2];
LL ans;
//=============================================================
void Init() {
for (int i = 0; i <= 30; ++ i) {
int s = (1 << i);
pre[i][0][0] = suf[i][n + 1][0] = 1;
pre[i][0][1] = suf[i][n + 1][1] = 0;
for (int j = 1, c = 0; j <= n; ++ j) {
c += ((a[j] & s) != 0);
cntpre[i][j] = c;
pre[i][j][0] = pre[i][j - 1][0] + (c % 2 == 0);
pre[i][j][1] = pre[i][j - 1][1] + (c % 2 == 1);
}
for (int j = n, c = 0; j >= 1; -- j) {
c += ((a[j] & s) != 0);
suf[i][j][0] = suf[i][j + 1][0] + (c % 2 == 0);
suf[i][j][1] = suf[i][j + 1][1] + (c % 2 == 1);
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n;
for (int i = 1; i <= n; ++ i) std::cin >> a[i];
Init();
ans = 0;
for (int y = 1; y <= n; ++ y) {
int bit = log2(a[y]);
int c = cntpre[bit][n];
int cpre[2] = {pre[bit][y - 1][0], pre[bit][y - 1][1]};
int csuf[2] = {suf[bit][y + 1][0], suf[bit][y + 1][1]};
if (c % 2 == 0) {
ans += 1ll * cpre[0] * csuf[0];
ans += 1ll * cpre[1] * csuf[1];
} else {
ans += 1ll * cpre[0] * csuf[1];
ans += 1ll * cpre[1] * csuf[0];
}
}
std::cout << ans << "\n";
}
return 0;
}
E
数论。
赛时查到了威尔逊定理但是不会求化简后的式子，输！
写在最后
学到了什么：
- C：方案数不好 DP 考虑组合意义。
- D：考虑异或的性质，异或后变大变小，仅需考虑最高位 1。