小明の雜貨鋪

斐波那契数列的 20 种求法 矩阵快速幂 题意 设 an={an−1+an−2,n⩾31,n=1∨n=2a_{n}=\begin{cases}a_{n-1}+a_{n-2},&n \geqslant 3\\1,&n=1\lor n=2\end{cases}an​={an−1​+an−2​,1,​n⩾3n=1∨n=2​，求 an mod ma_n\bmod man​modm。 解 设 M=[0111]\mathbf{M}=\begin{bmatrix}0 &1\\ 1 & 1\end{bmatrix}M=[01​11​]​，则 [Fn0Fn+10]=Mn−1[1010]\begin{bmatrix}F_n & 0 \\ F_{n+1} & 0\end{bmatrix} =\mathbf{M}^{n-1}\begin{bmatrix}1 & 0 \\ 1 & 0 \end{bmatrix} [Fn​Fn+1​​00​]=Mn−1[11​00​] 于是...

博弈论 是经济学的一个分支； 主要研究具有竞争或对抗性质的对象在一定规则下的行为； 考虑个体中的预测行为和实际行为，并研究其优化策略； 通俗地讲，主要研究的是在一个游戏中进行游戏的多位玩家的策略。 公平组合游戏（ICG） 二人参与，轮流决策，每次可以在有限的合法决策集合中选择一种进行操作，双方均知道游戏的完整信息； 在某一确定状态做出的决策集合只与状态有关，与玩家、之前的操作等任何因素都无关； 如果轮到某位玩家的回合时合法决策集合为空（即无法进行操作），该名玩家负。游戏一定会在有限步数之后以非平局结束； 大部分棋类游戏都是非公平组合游戏：国际象棋，五子棋等，因为双方都无法使用对方的棋子。 博弈图 给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。 任何一个 ICG 游戏都可以转化为有向图游戏：把每个状态视为一个节点，向它的后继状态连边，转化为有向图游戏，也称绘制了它的博弈状态图（简称博弈图或者游戏图）。 ...

裂项 ∑i=1n(ai−ai+k)=∑i=1kai−∑i=n+1n+kai\sum_{i=1}^{n}(a_{i}-a_{i+k})=\sum_{i=1}^{k}a_{i}-\sum_{i=n+1}^{n+k}a_{i} i=1∑n​(ai​−ai+k​)=i=1∑k​ai​−i=n+1∑n+k​ai​ 约瑟夫环问题 约瑟夫环问题 设 Jn,mJ_{n, m}Jn,m​ 表示规模分别为 n,mn, mn,m 的约瑟夫问题的答案。我们有如下递归式 Jn,m=(Jn−1,m+m) mod nJ_{n, m}=\left(J_{n-1, m}+m\right) \bmod n Jn,m​=(Jn−1,m​+m)modn 这个也很好推。从 0 开始数 mmm 个，让第 m−1m-1m−1 个人出局后剩下 n−1n-1n−1 个人，计算出在 n−1n-1n−1 个人中选的答案后，再加一个相对位移 mmm 得到真正的答案。 题目说是从 kkk 开始报数，所以答案再加上 kkk。 时间复杂度 Θ(n)\Theta(n)Θ(n)： 12345int res = 0;for (int i =...

![[…/data/img/e5e92bc7d32828b005d6b7f73694da57_720.jpg]] 素数筛 （欧拉筛） 1234567891011121314vector<int> prime;int mint[N]; // 最小素因子 void init() { for (int i = 2; i < N; i++) { if (!mint[i]) mint[i] = i, prime.push_back(i); for (auto& p : prime) { if (1ll * i * p >= N) break; mint[i * p] = p; if (p == mint[i]) break; } } mint[1] = 1;} 时间复杂度 Θ(n)\Theta(n)Θ(n) VJwin6D - 又见 GCD 题意 已知...

逆元 模为素数 123456789101112131415constexpr int mod = 998244353;ll qpow(ll a, ll n) { ll res = 1; while (n) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res;}int inv(int n) { return qpow(n, mod - 2);} // 1/a (p 是素数) 非固定模数 123456789101112131415161718192021222324252627282930ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}ll exgcd(ll a, ll b, ll& x, ll& y) { if (b ==...

DSU01 - Find by Optimized Path Compression 路径压缩优化 12345678910111213141516171819202122232425262728struct DSU { vector<int> p, siz; DSU(int n) : p(n + 1), siz(n + 1, 1) { iota(p.begin(), p.end(), 0); } int find(int x) { while (x != p[x]) x = p[x] = p[p[x]]; // 路径压缩 return x; } bool same(int x, int y) { return find(x) == find(y); } bool uno(int x, int y) { x = find(x), y =...

multiset 的 maintain 法 枚举左端点，使用大小根堆 maintain 求出所有右端点的答案。时间复杂度 Θ(n2log⁡n)\Theta(n^{2}\log n)Θ(n2logn)。 例 1 求 {a}\lbrace a \rbrace{a} 的所有子序列的中位数，数据范围：n⩽2000, 0⩽ai⩽109n \leqslant 2000,\ 0 \leqslant a_{i} \leqslant 10^{9}n⩽2000, 0⩽ai​⩽109。 12345678910111213141516171819202122int n = read();for (int i = 1; i <= n; i++) a[i] = read();for (int i = 1; i <= n; i++) { priority_queue<int, vector<int>> L; priority_queue<int, vector<int>, greater<>> R; int mid =...

效率更高的 __builtin_popcount() 函数，即 123456789template <typename T>  unsigned int __builtin_popcount(T u) {      u = (u & 0x55555555) + ((u >> 1) & 0x55555555);      u = (u & 0x33333333) + ((u >> 2) & 0x33333333);      u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);      u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);      u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);      return u;  } 二分转化为 01...

三分法求凸函数最值 求类似开口朝上的二次函数的最小值： 1234567891011121314auto check = [&](int mid) { // 计算... return /* f(mid) */;};int lt = /* 下界 */, rt = /* 上界 */ + 1; // 切记 +1while (lt < rt) { int lm = lt + (rt - lt) / 3, rm = lt + (rt - lt) * 2 / 3; if (check(lm) < check(rm)) lt = lm + 1; else rt = rm;}// now lt = rtcout << "The function reaches its minimum value of " << check(lt) << " at " << lt <<...

和 ⩾s\geqslant s⩾s 的最短子区间 12345678910111213141516171819void eachT() { int n = read(), s = read(); vector<ll> pre(n + 1); for (int i = 1; i <= n; ++i) { pre[i] = pre[i - 1] + read(); } int ans = inf; for (int l = 1, r = 1; l <= n; l++) { while (r < n && pre[r] - pre[l - 1] < s) { // 当前不满足 r++; } if (pre[r] - pre[l - 1] >= s) { ans = min(ans, r - l + 1); ...