【组合计数杂谈】三道 Bingo 游戏题（备份）
本文涉及的知识点：组合数公式，古典概型，Min-Max 反演及推广，卷积优化思想，状态压缩思想与状态压缩 DP，快速数论变换 NTT，快速数论变换 NTT，快速沃尔什变换 FWT。 本系列教程「以题带讲」，以典型题目为载体，着重讲解知识点的适用条件和使用方法，而规避复杂的理论推导。 我不擅长数学，对 CF 和区域赛的数学题，从简单计算到数论组合都望而却步。「tag 是数学吗那不做了。」 可能是因为网上的教程大多是罗列定理，给出大段证明，最后放几个例题链接。我没有耐心和能力读完整篇文章。 2024 ICPC World Finals Astana B. Bingo for the Win! Bingo 游戏，nnn 个人每人要抢 kkk 个数，主持人按随机顺序依次报数，报到每个数 [1,109][1,10^{9}][1,109] 的概率相同。已知如果有多名选手要抢某个数字，那么编号小的选手总是优先抢到。问每个人成为最后一名（其他人都抢完了但自己还没抢完）的概率。 ...
【算法杂谈 + 好题分享】图论中的懒标记 LazyTag 思想
本系列教程「以题带讲」，以典型题目为载体，着重讲解知识点的适用条件和使用方法，而规避复杂的理论推导。 我不擅长数学，对 CF 和区域赛的数学题，从简单计算到数论组合都望而却步。「tag 是数学吗那不做了。」 可能是因为网上的教程大多是罗列定理，给出大段证明，最后放几个例题链接。我没有耐心和能力读完整篇文章。
〔主机註記〕第 60 周主机註記 (Mar.31 - Apr.6)
第 60 周主机註記 月曜日 (Mar.31) 火曜日 (Apr.1) 水曜日 (Apr.2) 二十 主机はたち了。我什麽時候送生日禮物呢？ 神經 好想發瘋，但包會被罵神經病的（暴躁）（毀滅）。主机表示會被罵就別說。 萬事 我們有邀請賽三選一的機會。其實想在 final 之前打一場，西安大上分，長春沒去過也可以考慮。不過去哪裏都是連續三周，可惜，要是能把南昌踢了真是萬事大吉。最終決定長春（閃亮）。 有老師群裏一人一句話，顯得我們很民主。 被訪 主机說長的特漂亮的不適合做訪談員，做訪談的最好長得老實巴交的。訪談就是找你聊天，跟你說的目的未必是真實目的。我之前還想過這問題，特別想被訪談，被新院的漂亮姐姐訪談。呃長的漂亮不是重點，主要是這種形式。他們在講話方面都很有招，和他們聊天很舒服。真的特別想被訪談。 監考 校賽監考。 牛客沒有給我線上管理權限，好氣，我能不能登你們號，不理我，好氣。我想看榜，我想看神人代碼，我還好想喝果茶，好氣。 主机部長挺牛的，看上去是那種，前一分鐘還在打球，後一分鐘就 void...
〔主机註記〕第 59 周主机註記 (Mar.24 - Mar.30)
第 59 周主机註記 月曜日 (Mar.24) 火曜日 (Mar.25) 水曜日 (Mar.26) 木曜日 (Mar.27) 金曜日 (Mar.28) 土曜日 (Mar.29) 日曜日 (Mar.30)
Codeforces Round 1012 (Div. 1) A B1 C1
2089A - Simple Permutation 从小往大顺着选，如果不是素数就选个稍微大一点的让结果是素数。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include <bits/stdc++.h>using namespace std;using ll = long long;constexpr int N = 5e5 + 5;vector<int> prime;int mint[N]; // 最小素因子 bool is_prime(int x) { return mint[x] == x;}signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); for...
〔补题〕2025 钉耙编程春季联赛（3）
（赛中 + 补题记录） 不是题解，更多是做题心得与评价。 1001 数列计数 组合数 (nm)\dbinom{n}{m}(mn) 是奇数 ⟺ n&m=m\iff n\&m=m⟺n&m=m。如果某一位 nnn 是 0，那 mmm 只能是 0 没得选，否则有 1 0 两种选择。 和上次 1001 类似，枚举 ℓ\ellℓ 的前缀，把其中一位 1 变成 0 之后，这一位后面的 1 就可以任意选择变成 0。 123456789101112131415161718Z res = 1;for (int i = 0; i < n; i++) { int L = 0; // 前缀 int sum = 0; for (int bit = 30; bit >= 0; bit--) { if (l[i] >> bit & 1) { // 这一位是 1 才能把 1 变成 0 if (((a[i] & L) == L)) { // 前缀要满足约束 sum +=...
〔主机註記〕第 58 周主机註記 (Mar.17 - Mar.23)
第 58 周主机註記 月曜日 (Mar.17) 火曜日 (Mar.18) 水曜日 (Mar.19) 木曜日 (Mar.20) 金曜日 (Mar.21) 土曜日 (Mar.22) 激发 港科广本科生区域赛拿奖一人十五万人民币奖学金，我感觉这个比不报销，更能激发人类潜能。 日曜日 (Mar.23)
Educational Codeforces Round 174 A - F
（一个月前的比赛） 2069A - Was there an Array? 12345678910111213141516171819202122232425262728293031#include <bits/stdc++.h>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; n -= 2; vector<int> b(n); for (int i = 0; i < n; i++) { cin >> b[i]; } bool flag = 1; for (int i =...
〔补题〕2025 钉耙编程春季联赛（2）
（赛中 + 补题记录） 不是题解，更多是做题心得与评价。 时间卡的也太紧了，STD 两倍时限，STD 用数组我用 std::map 就 T 了。。 PI 节没出个关于 PI 的题 1001 学位运算导致的 和同学聊天时口胡的思路，可能有点混乱 所求的 yyy，直接看是若干个数 or and and or 这样从左至右算出来的，当然这些数可能重复。or and 运算满足分配律，所以表达式总是可以化简为若干个东西 or 起来再 and，或者若干个东西 and 起来再 or。选后者，比较符合直觉。 可以先从极端想，若干个东西 and 出来只有一位。枚举每一位，把 and 起来还有这一位的东西都 and 起来，尽量让其它位都变 0。当然如果没办法都变成 0，就形成了要有这一位，另一位就必须存在这种关系（注意这关系没有传递性）。比如原来是 10 和 11（二进制），包含最低位的那只能是 11。这些数有个特点，要么独立要么包含，两两 and 不可能更小，不会有 110 和 011 同时出现。这样处理将得到 64 个大数。 现在的问题就是，64...
Codeforces Round 1008 (Div. 1) A - C
2077A/2078C - Breach of Faith 取较大的 n2+1\cfrac{n}{2}+12n+1 个放在奇数位，较小的放在偶数位。 12345678910111213141516171819202122232425262728293031323334353637#include <bits/stdc++.h>using namespace std;using ll = long long;int main() { int J; cin >> J; while (J--) { int n; cin >> n; vector<int> a(n * 2); for (int i = 0; i < n * 2; i++) { cin >> a[i]; } sort(a.begin(), a.end()); ...
