DarknessCatcher

数论分块可以快速计算一些含有除法向下取整的和式（即形如 $\sum_{i=1}^nf(i)g(\left\lfloor\dfrac ni\right\rfloor)$ 的和式）我们可以观察一下$\left\lfloor\dfrac ni\right\rfloor$的值是如何变化的，举个例子$\left\lfloor\dfrac {10}i\right\rfloor$，当$i$从1到10，$\left\lfloor\dfrac {10}i\right\rfloor$的值为 $10,5,3,2,2,1,1,1,1,1$，我们发现，当$i \in [5, 10]$ 时，其值均为 $1$。也就是这一段区间$\left\lfloor\dfrac ni\right\rfloor$ 的值都是相同的。当我们O(n)从 $1$ 到$n$ 枚举 $i$ 时，会发现有很多像上述所说的相同值，能不能将相同的部分一起计算呢？ 整除分块可以做到将值相同的区间右端点快速算出，这样对于每一段都能O(1)的算出这一段整体的值。我们从 $1$ 到 $n$ 枚举 $i$，值为 $\left\lfloor\dfrac ni\ ...

矩阵乘法前提条件：只有当第一个矩阵的列数与第二个矩阵的行数相同时，才能进行乘法运算运算规则：矩阵 a $\times$ 矩阵 b = 矩阵 ans，$ans{ij} = \sum{k=1} a{ik} \times b{kj}$题目链接123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <bits/stdc++.h>using namespace std;const int N = 110, mod = 1e9 + 7;struct node { int a[N][N], r, c; node () {memset(a, 0, sizeof a);} node operator * (const node &w) const { node res; for (int i = 1; i <= r; i++) { for (int j = 1; j <= w.c; ...

O(N^2) 求组合数 $C^m_n$根据$C_n^m = C_{n-1}^m + C_{n-1}^{m-1}$初始化$C_i^0 = 1$，然后开始递推即可 1234for (int i = 0; i < N; i ++ ) for (int j = 0; j <= i; j ++ ) if (!j) c[i][j] = 1; else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; $O(N)$求组合数根据$C_n^m = \frac{n!}{m! \times (n - m)!}$O(n)预处理出阶乘以及阶乘的逆元，每次求 $C_n^m$ 均为O(1) 1234567891011fact[0] = infact[0] = 1;// 快速幂求逆元infact[N - 1] = qmi(infact[N - 1], mod - 2);for (int i = 1; i < N; i ++ ) { fact[i] = fact[i - 1] ...

约数个数定理：一个数分解质因数为：$p_1^{c_1} \times p_2^{c_2} \times p_3^{c_3} \times … \times p_k^{c_k}$，那么该数的约数个数等于 $(c_1 + 1) \times (c_2 + 1) \times (c_3 + 1) \times … \times (c_k + 1)$ 证明：对于该数的约数，一定是 $p_1^{d_1} \times p_2^{d_2} \times p_3^{d_3} \times … \times p_k^{d_k}$, $1 \le d_i \le c_i$，那么对于 $d_i$，共有 $c_i + 1$种方案，再根据乘法原理，共有 $(c_1 + 1) \times (c_2 + 1) \times (c_3 + 1) \times … \times (c_k + 1)$ 个约数 约数之和定理：一个数分解质因数为：$p_1^{c_1} \times p_2^{c_2} \times p_3^{c_3} \times … \times p_k^{c_k}$，那么该数的约数之和等于 $ ...

试除法时间复杂度O($\sqrt x$), x 是数的大小 123456789101112131415signed main() { int x; // 对 x 进行质因数分解 cin >> x; for (int i = 2; i <= sqrt(x); i++) { if (x % i == 0) { int cnt = 0; while(x % i == 0) { x /= i; cnt++; } cout << i << " " << cnt << endl; } } if (x > 1) cout << x << " " << 1 << en ...

dfs版本倒着做1234567891011int dfs(int sta, int now) { // sta是当前的状态(二进制)，now是当前的位置 if (~dp[sta][now]) return dp[sta][now]; int res = 0x3f3f3f3f; for (int i = 0; i < n; i++) { if (sta >> i & 1) { res = min(res, dfs(sta ^ (1 << i), i) + (价值)); } } return dp[sta][now] = res;} 正着做1234567for (int i = 1; i < (1 << n); i++) { for (int j = 0; j < n; j++) { if (i >> j & 1) { ...

12345678910111213141516171819202122int dfs(int pos, int pre, int lead, int limit) { if (!pos) { 边界条件 } if (!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre]; int res = 0, up = limit ? a[pos] : 无限制位; for (int i = 0; i <= up; i ++) { if (不合法条件) continue; res += dfs(pos - 1, 未定参数, lead && !i, limit && i == up); } return limit ? res : (lead ? res : dp[pos][sum] = res);}int cal(int x)  ...

01背包每个物品要么拿要么不拿12345678910111213141516171819#include<iostream>#include<cstring>using namespace std;const int N = 1010;int f[N], v[N], w[N];int n, V;int main(){ scanf("%d%d", &n, &V); for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]); for(int i = 1; i <= n; i++) for(int j = V; j >= v[i] ; j--) f[j] = max(f[j], f[j - v[i]] + w[i]); cout << f[V];} 完全背包每个物品能拿无限个123456789101112131415161718 ...

关于使用bitset优化背包

jiangly 的算法模板

算法竞赛，染色法判段是否是二分图、二分图匹配模板