这么爱计数
A. 图 / HDU4903 The only survival
https://vjudge.net/problem/HDU-4903#author=DeepSeek_zh
很容易想到基于按 dis 从小到大枚举的做法
但是发现算方案就必须要知道每个点的具体 dis，就导致难以 DP，只能搜索，这样复杂度就不太好看。
一个显然的观察：并不关心 \(1,n\) 以外点的标号，所以可以把 \(O(n^k)\) 的暴搜优化到 \(O(\binom{n+k}k\cdot (n+k))\)，然后做多重集排列即可。
模数非质时的多重集排列：link
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("graph.in", "r", stdin);
std::freopen("graph.out", "w", stdout);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, k, L, mod;
std::cin >> n >> k >> L >> mod;
if (L < k) {
std::cout << 0 << '\n';
return 0;
}
std::vector<std::vector<long long> > C(n + 1, std::vector<long long> (n + 1));
C[0][0] = 1ll;
for (int i = 1; i <= n; ++i) {
C[i][0] = 1ll;
for (int j = 1; j <= i; ++j)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
std::vector<int> dis(n + 1), s;
int res = 0;
std::function<void(int, int, long long)> DFS = [&](int x, int d, long long now) {
if (x == n) {
auto s0 = now, s1 = now;
for (int i = 1; i < n; ++i)
if (dis[i] >= k)
(s0 *= L) %= mod, (s1 *= L) %= mod;
else if (L - (k - dis[i] - 1)) {
(s0 *= L - (k - dis[i] - 1)) %= mod;
(s1 *= L - (k - dis[i] - 1) - 1) %= mod;
}
else {
s0 = s1 = 0ll;
break;
}
dis[x] = k;
auto u = 1ll;
int cnt = n - 2;
for (auto i : s)
(u *= C[cnt][i]) %= mod, cnt -= i;
(res += u * (s0 + mod - s1) % mod) %= mod;
return;
}
for (int i = d; i <= k + 1; ++i) {
auto s0 = now, s1 = now;
for (int j = 1; j < x; ++j)
if (dis[j] >= i)
(s0 *= L) %= mod, (s1 *= L) %= mod;
else if (L - (i - dis[j] - 1)) {
(s0 *= L - (i - dis[j] - 1)) %= mod;
(s1 *= L - (i - dis[j] - 1) - 1) %= mod;
}
else {
s0 = s1 = 0ll;
break;
}
dis[x] = i;
if (dis[x] != dis[x - 1])
s.push_back(1);
else
++s.back();
if (i == k + 1)
s1 = 0ll;
DFS(x + 1, i, (s0 + mod - s1) % mod);
if (dis[x] != dis[x - 1])
s.pop_back();
else
--s.back();
}
return;
};
DFS(2, 1, 1);
std::cout << res % mod << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}B. 路线 / ARC136E Non-coprime DAG
https://www.luogu.com.cn/problem/AT_arc136_e
做过 CF870F Paths 可以很快反应过来：\(x\) 和 \(y\) 是否可以同时被选，取决于它们各自的最小质因子是否能在 \(x,y\) 之间交汇（或用 \(2\) 作跳板）。
接着就发现由于 \(2\) 间隔出现，此时再分奇偶性就会显得非常合理。
两个偶数总是不能同时被选；对于奇数 \(x\) 和偶数 \(y\)，要求 \(y\in [x-f(x)+1,x+f(x)-1]\)。
考察奇数的选取。容易发现，钦定用 \(2\) 作跳板，则两个奇数 \(x,y(x<y)\) 能同时被选，当且仅当：
- 记 \(f(i)\) 为 \(i\) 的最小质因子，则 \(x+f(x)> y-f(y)\)。
发现实际上可以认为 \(x\) 代表区间 \([x-f(x),x+f(x)-1]\)。那么两个点可以同时被选当且仅当它们代表的区间有交（这样就去掉了 \(x,y\) 之间的偏序条件）
这样发现对『代表区间』的定义，在奇数视角和偶数视角下是冲突的，可以发现偶数视角的区间更紧；事实上，应该采用 \([x-f(x)+1,x+f(x)-1]\) 这个看似充分不必要的定义，因为端点总是奇数，导致 \(x+f(x)> y-f(y)\) 和 \(x+f(x)-1<y-f(y)+1\) 不能同时成立。
进一步推广结论，容易发现多个奇数可以同时被选，当且仅当它们代表的区间有交。故可以枚举值域中的点，找加权覆盖次数最大值。
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n;
std::cin >> n;
std::vector<int> fac(n + 1), l(n + 1), r(n + 1);
for (int i = 2; i <= n; ++i) {
if (!fac[i]) {
fac[i] = i;
for (int j = 2 * i; j <= n; j += i)
if (!fac[j])
fac[j] = i;
}
l[i] = std::max(1, i - fac[i] + 1);
r[i] = std::min(i + fac[i] - 1, n);
}
std::vector<int> a(n + 1);
std::vector<long long> dif(n + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
if (i == 1 || i % 2 == 0)
continue;
dif[l[i]] += a[i];
if (r[i] != n)
dif[r[i] + 1] -= a[i];
}
auto res = 0ll;
std::partial_sum(dif.begin(), dif.end(), dif.begin());
for (int i = 1; i <= n; ++i) {
auto now = a[1] + dif[i];
if (i % 2 == 0)
now += a[i];
res = std::max(res, now);
}
std::cout << res << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}A. 列车扫除
https://www.becoder.com.cn/contest/6708/problem/1
绝对聪明的 A, B, C 在一起玩 Nim，有三堆石子 \(c_{1,2,3}\)，每次可以任选一堆拿走正整数个，不能拿的人扣一分，他的上一个人加一分。
给定 \(q\) 次询问，形如：
- 现在知道 \(\forall \, i=1,2,3,c_i\in[l_i,r_i]\)。对于这 \(\prod_{i=1,2,3}r_i-l_i+1\) 种可能的情况，对于每个人，求出分数之和。
\(q\le 10^6,V=10^9\)。
容易发现，胜，平，负三个状态会被分给三个人，且一共只有三种分配方式。
当只剩一堆石头时，操作者胜；石头状态为 \((0,1,1)\) 时，操作者负。
B. 换来换去
https://www.becoder.com.cn/contest/6708/problem/2
对 \(n\) 个有标号的球任意分成任意组，组是无顺序的，且要求每组球个数 \(\ge 2\)，求方案数，对质数取模。
\(n\le 10^7\)。
发现这是一个类斯特林数的问题，二项式反演得到答案式为：
\[ \sum_{i=0}^n (-1)^{n-i}\binom ni \sum_{j=0}^i \begin{Bmatrix} i\\ j\end{Bmatrix} \]
用斯特林数通项展开：
\[ \sum_{i=0}^n (-1)^{n-i}\binom ni \sum_{j=0}^i \sum_{k=0}^j(-1)^{j-k}\dfrac {k^i}{(j-k)!\cdot k!} \]
很容易注意到一个二项式定理的结构，故交换求和顺序：
\[ \sum_{j=0}^n \sum_{k=0}^j \dfrac {(-1)^{j-k}}{(j-k)!\cdot k!}\cdot \sum_{i=j}^n \binom ni (-1)^{n-i}k^i \]
发现一个很严重的问题在于 \(i\) 的起始范围是 \(j\) 而不是 \(0\)，但如果我们把一开始的式子改写成这样：
\[ \sum_{i=0}^n (-1)^{n-i}\binom ni \sum_{j=0}^n \begin{Bmatrix} i\\ j\end{Bmatrix} \]
容易发现当 \(j>i\) 时 \(\begin{Bmatrix} i\\ j\end{Bmatrix}=0\)，和原式的值相同，且斯特林数通项对于 \(j>i\) 也是成立的，故原式等价于
\[ \begin{aligned} &\sum_{j=0}^n \sum_{k=0}^j \dfrac {(-1)^{j-k}}{(j-k)!\cdot k!}\cdot \sum_{i=0}^n \binom ni (-1)^{n-i}k^i\\ =&\sum_{j=0}^n \sum_{k=0}^j \dfrac {(-1)^{j-k}}{(j-k)!\cdot k!}\cdot (k-1)^n\\ =&\sum_{k=0}^n \dfrac {(k-1)^n}{k!}\cdot \sum_{j=0}^{n-k} \dfrac {(-1)^j}{j!}\\ \end{aligned} \]
后者内部与 \(k\) 无关，是可前缀和计算的，只需要考虑在 \(O(1)\) 内求出 \((k-1)^n\) 的值，筛一下，对于质数（约 \(\dfrac n{\ln n}\) 个）快速幂，合数用积性函数之类即可。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("card.in", "r", stdin);
std::freopen("card.out", "w", stdout);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
for (std::cin >> T; T--; ) {
int n, mod;
std::cin >> n >> mod;
std::vector<int> tag(n + 1), p, pw(n + 1);
auto qkp = [&](long long x, int y) {
auto res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
pw[1] = 1ll;
for (int i = 2; i <= n; ++i) {
if (!tag[i]) {
pw[i] = qkp(i, n);
p.push_back(i);
}
for (auto j : p) {
if (i > n / j)
break;
tag[i * j] = 1;
pw[i * j] = (long long)pw[i] * pw[j] % mod;
if (i % j == 0)
break;
}
}
std::vector<int> inv(n + 1), s(n + 1);
inv[0] = 1ll;
for (int j = 1; j <= n; ++j)
inv[j] = (long long)inv[j - 1] * j % mod;
inv[n] = qkp(inv[n], mod - 2);
for (int j = n - 1; j; --j)
inv[j] = (long long)inv[j + 1] * (j + 1) % mod;
s[0] = inv[0];
for (int j = 1; j <= n; ++j) {
if (j & 1)
s[j] = s[j - 1] + mod - inv[j];
else
s[j] = s[j - 1] + inv[j];
if (s[j] >= mod)
s[j] -= mod;
}
auto res = (long long)s[n] * ((n & 1) ? mod - 1 : 1);
for (int k = 1; k <= n; ++k)
res += (long long)pw[k - 1] * inv[k] % mod * s[n - k] % mod;
std::cout << res % mod << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}C. 画家
https://www.becoder.com.cn/contest/6714/problem/3
ARC 特供删十字，故时光倒流，转化成在图上删相同颜色的十字 / 行 / 列。
令 \(f_{i,j}\) 表示合法的 \(i\) 行 \(j\) 列地图。发现同颜色的删行 + 删列会和直接删十字算重，
B. 灯光秀 / CF1545C AquaMoon and Permutations
https://www.luogu.com.cn/problem/CF1545C
第一步需要想到，如果某一列的某个数，只有一个排列有，那么这个排列必须被选入拉丁方；
用这个必选的排列，可以排除掉一些与之冲突、不能选入拉丁方的排列。
A. bot 的能量堆
https://www.becoder.com.cn/contest/6731/problem/1
⚡超越一切震慑凡人⚡
给定正整数 \(x,y\)，你可以执行下面三种操作：
- 将 \(x,y\) 同时加 1；
- 将 \(x,y\) 同时减一；
- 对于 \(\gcd(x,y)\) 的一个质因子 \(p\)，将 \(x,y\) 同时除以 \(p\)。
问最少花费多少次操作使得 \(\min(x,y)=1\)。多测。
\(T\le 300,1\le x,y\le 10^9\)。
不妨先考虑 \(x\ne y\) 的情况，发现三种操作都不会使 \(x,y\) 的相对大小关系改变。故令 \(x<y\)，考虑让 \(x\) 变为 1。
记 \(d=y-x\)， 很容易注意到 \(d\) 的值不会在前两种操作中改变，由辗转相减，\(\gcd(x,y)=\gcd(d, x)\)，即操作三每次选取的 \(p\) 总是 \(d\) 的质因子，且总能通过若干次操作 1/2 让 \(p\) 能够执行。
每次执行操作 3 后，\(d\gets d\div p\)，每次只需让 \(x\) 变为 \(\lfloor \frac xp\rfloor\) 或 \(\lceil \frac xp\rceil\)。
直接记搜的话，容易发现状态总数是 V 因数总数。
对于 \(x=y\) 的情况，答案至多为 \(x\) 的质因子数量。暴搜 + 剪枝非常可过。
有一种神秘的处理方式…
if (x == y) { auto calc = [&](int x) { int cnt = 0; for (int i = 2; i * i <= x; ++i) for (; x % i == 0; ++cnt, x /= i); return cnt + (x != 1); }; int to = calc(x), res = to; for (int i = std::max(x - to, 1); i <= x + to; ++i) res = std::min(res, calc(i) + std::abs(i - x)); std::cout << x << '\n'; continue; }容易发现这东西没什么道理，反例大概率存在但在小范围内确实难以构造。总之数据没卡到。
B. bot 的矩阵
https://www.becoder.com.cn/contest/6731/problem/2
⚡带来终结机械降神⚡
有一个 \(n\times n\) 的二维数组，初始只知道 \(m\) 个位置的数 \(a_{x,y}\)，以及每行、每列的元素和 \(sx_{1\cdots n},sy_{1\cdots n}\)。
构造出一个合法的解，每个数在 \([-2^63,2^63)\) 内。
\(n\le 2000\),\(a_{x,y},sx_i,sy_i\in [-10^9,10^9]\)，\(m\le n^2\)。
听说很容易想到二分图，但实在反应不过来。但在乱填的时候发现，如果出现了『必填』的情况，是一个行列交错的链式反应，这样就很容易想到二分图了
原理是同时影响行 \(i\) 列 \(j\) 的元素只有 \((i, j)\)
相当于给一个 \(2n\) 个点 \(n^2\) 条边的二分图，其中一些边权是已知的，那么不妨认为这些边被删除了
同时也是一个 \(n^2\) 个元，\(2n-1\) 个方程的方程组（\(sx=sy\) 会消掉一条方程）；故很多元其实可以直接赋 \(0\)，只拿 \(2n-1\) 个元出来解方程。
在挖掉已知边的二分图上任意找生成树（森林）就可以满足 \(2n-1\) 的限制，结合树上高斯消元，从叶子开始解方程即可。
#include <bits/stdc++.h>
#define int long long
#define nec getchar
void read(int &x) {
x = 0;
char ch = nec();
bool flag = false;
for (; ch < '0' || ch > '9'; ch = nec())
if (ch == '-')
flag = true;
for (; ch >= '0' && ch <= '9'; ch = nec())
x = x * 10 + ch - '0';
if (flag)
x = -x;
return;
}
signed main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen("matrix3.in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
for (read(T); T--; ) {
int n, m;
read(n), read(m);
std::vector<int> sx(n + 1), sy(n + 1);
for (int i = 1; i <= n; ++i)
read(sx[i]);
for (int i = 1; i <= n; ++i)
read(sy[i]);
std::vector<std::vector<int> > vis(n + 1, std::vector<int> (n + 1));
std::vector<std::vector<long long> > a(n + 1, std::vector<long long> (n + 1));
std::vector<int> tx(n + 1), ty(n + 1);
auto work = [&](int i, int j, int c) {
vis[i][j] = 1;
++tx[i], ++ty[j];
sx[i] -= c, sy[j] -= c, a[i][j] = c;
return;
};
for (int x, y, c; m--; ) {
read(x), read(y), read(c);
work(x, y, c);
}
if (std::accumulate(sx.begin() + 1, sx.end(), 0ll) != std::accumulate(sy.begin() + 1, sy.end(), 0ll)) {
std::cout << "NoSolution!" << '\n';
continue;
}
std::vector<int> fx(n + 1), fy(n + 1);
std::function<bool(void)> check = [&](void) {
for (int x = 1; x <= n; ++x)
if (!fx[x]) {
if (tx[x] == n) {
if (sx[x] != 0)
return false;
fx[x] = 1;
if (!check())
return false;
}
else if (tx[x] == n - 1) {
for (int y = 1; y <= n; ++y)
if (!vis[x][y]) {
work(x, y, sx[x]);
fx[x] = 1;
if (!check())
return false;
}
}
}
for (int y = 1; y <= n; ++y)
if (!fy[y]) {
if (ty[y] == n) {
if (sy[y] != 0)
return false;
fy[y] = 1;
if (!check())
return false;
}
else if (ty[y] == n - 1) {
for (int x = 1; x <= n; ++x)
if (!vis[x][y]) {
work(x, y, sy[y]);
fy[y] = 1;
if (!check())
return false;
}
}
}
return true;
};
if (!check()) {
std::cout << "NoSolution!" << '\n';
continue;
}
std::function<void(int, int)> DFS = [&](int x, int op) {
if (op == 0) {
fx[x] = 1;
for (int i = 1; i <= n; ++i)
if (!vis[x][i] && !fy[i]) {
DFS(i, 1);
work(x, i, sy[i]);
}
}
else {
fy[x] = 1;
for (int i = 1; i <= n; ++i)
if (!vis[i][x] && !fx[i]) {
DFS(i, 0);
work(i, x, sx[i]);
}
}
return;
};
for (int i = 1; i <= n; ++i)
if (!fx[i])
DFS(i, 0);
for (int i = 1; i <= n; ++i)
if (!fy[i])
DFS(i, 1);
std::cout << "Botany!" << '\n';
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
std::cout << a[i][j] << ' ';
std::cout << '\n';
}
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}A. 数码串
https://www.becoder.com.cn/contest/6736/problem/1
给定一个长度为 \(n\) 的数字串，现在需要给它分为若干段，问在所有 \(2^{n-1}\) 种分段方式中，有多少种满足：
- 在任意相邻的两段中，有至少一段，其对应的十进制数是 \(D\) 的倍数。
答案对 \(10^9+7\) 取模。
多测，\(n\le 2\times 10^5,D\le 10^6,T\le 100\)。
部分分特殊性质：\(\gcd(D,10)=1\)。
发现若 \(a_{l\cdots r}\) 是 \(D\) 的倍数，记 \(s_i=s_{i+1}+a_i\times 10^{n-i}\)，那么 \(\dfrac{s_l-s_{r+1}}{10^{n-r}}\bmod D=0\)
题目要求，这个转移点和上个转移点，至少有一个满足该式。显然可以类 DP 地做。
对于 \(D\) 与 \(10\) 互质的情况，原条件等价于 \(s_l\equiv s_{r+1}\pmod D\)，用一个桶记录 DP 值即可
记 \(D=2^*\times 5^?\times m\)，发现 \(m\) 与 \(10\) 互质，或许可以套用上方的做法
由于 \(D\le 10^6 < 2^{20}\)，对于一个固定的 \(r\)，所有 \(l\le r-20\) 项的 \(a_l\) 对 \(a_{l\cdots r}\bmod (2^*\times 5^?)\) 的贡献总是 \(0\)，故在只考虑 \(2^*\times 5^?\) 时， \(l\le r-20\) 的可选性和 \(l=r-20\) 的可选性相同。只需要对于 \(\bmod m\) 沿用桶做法即可。
对于 \(l\ge r-20\)，暴力即可，复杂度 \(O(T(n+D))\)。
注意 \(s_l-s_{r+1}\) 里的 \(r+1\)，调成鸲了
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("digit.in", "r", stdin);
std::freopen("digit.out", "w", stdout);
#else
std::freopen("./test/20251113/digit/ex_digit1.in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
std::vector<std::array<long long, 2> > c(1e6);
for (std::cin >> T; T--; ) {
std::string a;
int d, n, m, p;
std::cin >> a >> d, n = (int)a.length();
a = "#" + a;
std::vector<std::vector<long long> > f(n + 1, std::vector<long long> (2));
f[0][0] = 1ll;
m = d;
for (; m % 2 == 0; m /= 2);
for (; m % 5 == 0; m /= 5);
p = d / m;
for (int i = 0; i < m; ++i)
c[i][0] = c[i][1] = 0ll;
std::vector<int> s(n + 2);
for (int i = n, k = 1; i; --i, (k *= 10) %= m)
s[i] = (s[i + 1] + (a[i] - '0') * k) % m;
auto s0 = 0ll;
for (int i = 1; i <= n; ++i) {
int now = 0;
for (int j = i, k = 1; j > i - 20 && j; --j, (k *= 10) %= d) {
(now += (a[j] - '0') * k) %= d;
if (now == 0)
(f[i][0] += f[j - 1][0] + f[j - 1][1]) %= mod;
else
(f[i][1] += f[j - 1][0]) %= mod;
}
if (i > 20) {
(c[s[i - 20]][0] += f[i - 21][0]) %= mod;
(c[s[i - 20]][1] += f[i - 21][1]) %= mod;
(s0 += f[i - 21][0]) %= mod;
int now = 0;
for (int j = i, k = 1; j >= i - 20; --j, (k *= 10) %= p)
(now += (a[j] - '0') * k) %= p;
if (now == 0) {
(f[i][0] += c[s[i + 1]][0] + c[s[i + 1]][1]) %= mod;
(f[i][1] += s0 + mod - c[s[i + 1]][0]) %= mod;
}
else
(f[i][1] += s0) %= mod;
}
}
std::cout << (f[n][0] + f[n][1]) % mod << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}B. 背包
https://www.becoder.com.cn/contest/6736/problem/2
给定 \(n\) 种物品，第 \(i(1\le i\le n)\) 种有无穷多个，体积均为 \(v_i\)、价值均为 \(w_i\)。给定 \(Q\) 次询问，形如：
给定一个背包容积 \(m\)，回答两个问题：
- 有序地选取体积和恰好为 \(m\) 的物品，所能得到的最大价值。如果不存在这样的选取方式，回答 \(-1\)。
- 在上一问的条件下，可能的方案数。两个方案不同，当且仅当选取的物品数不同，或选物序列的某个位置不同。对 \(1092515507\) 取模，不存在则回答 \(-1\)。
\(n,Q,v_i\le 100, m,w_i\le 10^9\)。
mobai ddxrS
Tip：由于选取是有序的，所以朴素的『枚举物品 + 枚举体积』的 DP 是不可行的，而需要『枚举体积 + 枚举物品』。
很容易写出朴素的 DP：令二元组 \((a, b)_{m}\) 表示总体积 \(m\) 下的两问答案，则合并答案（定义为 \(+\) 运算）的过程可以写为：
\[ (a_1,b_1)_{m}+(a_2,b_2)_{m}=\begin{cases} (a_1,b_1)_{m}&a_1>a_2\\ (a_1,b_1+b_2)_{m}&a_1=a_2\\ (a_2, b_2)_{m}&\text{otherwise} \end{cases} \]
相似地，状态转移（定义为 \(\times\) 运算）可以写为：
\[ (a_1,b_1)_{m_1}\times (a_2,b_2)_{m_2}=(a_1+a_2,b_1\times b_2)_{m_1+m_2} \]
Tips：实际上是借鉴了矩阵乘法的含义进行定义，这样就可以尝试优化。
这样就有 \((f,g)_i = \sum\limits_{j=1}^n (f,g)_{i-v_j}\times (w_j,1)_{v_j}\)。
感性理解：显然，在直接背包时，\(+\) 运算与 \(\times\) 运算具有交换律，且 \(\times\) 对 \(+\) 有分配律。
那么此时广义矩乘具有结合律，可以优化。
体积最大为 \(100\)，考虑开 \(100\times 100\) 的矩阵（元素为二元组）维护 \((f,g)_{i-99}\sim (f,g)_i\)。考虑直接快速幂，发现复杂度是非常糟糕的 \(O(qv^3\log m)\)，非常糟糕。
初始矩阵是 \(1\times 100\) 的，这里的处理方式是预处理每一个 \(2^i\) 次幂（\(O(v^3\log m)\)），每次询问时二进制拆分 \(m\)，线性地乘过去，就可以把矩阵乘法优化为矩阵乘向量，复杂度降至 \(O(qv^2\log m)\)。
#include <bits/stdc++.h>
constexpr int N = 100;
const long long inf = 1e18;
const int mod = 1092515507;
struct node {
long long f, g;
node(): f(-inf), g(0ll) {}
node(long long f1, long long g1): f(f1), g(g1) {
if (g >= mod)
g -= mod;
return;
}
node operator* (const node &q) const {
return node(f + q.f, g * q.g % mod);
}
node operator+ (const node &q) const {
if (f > q.f)
return *this;
else if (f == q.f)
return node(f, g + q.g);
return q;
}
node& operator+= (const node &q) {
return *this = *this + q;
}
};
struct mat {
std::vector<std::vector<node> > a;
mat(void): a(N, std::vector<node> (N)) {}
std::vector<node>& operator[] (const int q) {
return a[q];
}
mat operator* (mat &q) const {
mat res;
for (int i = 0; i < N; ++i)
for (int k = 0; k < N; ++k)
for (int j = 0; j < N; ++j)
res[i][j] += a[i][k] * q[k][j];
return res;
}
};
struct vec {
std::vector<node> a;
vec(void): a(N) {}
node& operator[] (const int q) {
return a[q];
}
vec operator* (mat &q) const {
vec res;
for (int k = 0; k < N; ++k)
for (int j = 0; j < N; ++j)
res[j] += a[k] * q[k][j];
return res;
}
vec& operator*= (mat &q) {
return *this = *this * q;
}
};
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("pack.in", "r", stdin);
std::freopen("pack.out", "w", stdout);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, q;
std::cin >> n >> q;
std::vector<int> v(n + 1), w(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> v[i];
for (int i = 1; i <= n; ++i)
std::cin >> w[i];
std::vector<mat> t(30);
for (int j = 0; j < N - 1; ++j)
t[0][j + 1][j] += node(0ll, 1ll);
for (int i = 1; i <= n; ++i)
t[0][N - v[i]][N - 1] += node(w[i], 1ll);
for (int i = 1; i < 30; ++i)
t[i] = t[i - 1] * t[i - 1];
vec init;
init[N - 1] = node(0ll, 1ll);
for (int m; q--; ) {
std::cin >> m;
auto res(init);
for (int i = 29; ~i; --i)
if ((m >> i) & 1)
res *= t[i];
if (res[N - 1].f <= 0)
std::cout << -1 << ' ' << -1 << '\n';
else
std::cout << res[N - 1].f << ' ' << res[N - 1].g << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}A. 关卡设计
https://www.becoder.com.cn/contest/6742/problem/1
给定 \(n\times m\) 的字符地图，其中
S为起点（有且仅有一个），R，B为红、蓝宝石（可能有多个），x为障碍、.为可通行地块。现在需要把尽可能多的
.变为x，使得一种原来可以由S出发收集到的宝石在修改后的地图中仍能被收集。输出最多可修改的.的数量。\(n\times m\le 10^6\)。
一种显然错误的做法：拆点 \((u,0/1/2/3)\) 分别表示走到 \(u\) 时的宝石收集状态，跑 01BFS。
错误的原因：路径会重复走一些边，但它们不能被重复记入代价。
结合『重复走一些边』的想法，发现路径一定有一个『分叉点』。枚举这样的分叉点，从
S、所有R、所有B出发分别跑 01BFS。
#include <bits/stdc++.h>
const int dir[][2] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("design.out", "w", stdout);
std::freopen("design.in", "r", stdin);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
for (std::cin >> T; T--; ) {
int n, m, cnt = 0;
std::cin >> n >> m;
std::vector<std::vector<char> > a(n + 1, std::vector<char> (m + 1));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
std::cin >> a[i][j];
cnt += (a[i][j] == '.');
}
const int N = n * m;
auto id = [&](int i, int j) { return (i - 1) * m + j; };
std::vector<std::vector<int> > dis(3, std::vector<int> (N + 1, N + 1));
auto work = [&](std::vector<int> &dis, char S) {
std::deque<int> q;
std::vector<int> vis(N + 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (a[i][j] == S) {
dis[id(i, j)] = 0;
q.push_back(id(i, j));
}
for (; !q.empty(); ) {
int x, y;
{
int t = q.front();
q.pop_front();
if (vis[t])
continue;
vis[t] = 1;
x = (t - 1) / m + 1, y = t - (x - 1) * m;
}
for (auto [fx, fy] : dir) {
int nx = x + fx, ny = y + fy;
if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && a[nx][ny] != 'x') {
if (a[nx][ny] != '.') {
if (dis[id(nx, ny)] > dis[id(x, y)]) {
dis[id(nx, ny)] = dis[id(x, y)];
q.push_front(id(nx, ny));
}
}
else if (dis[id(nx, ny)] > dis[id(x, y)] + 1) {
dis[id(nx, ny)] = dis[id(x, y)] + 1;
q.push_back(id(nx, ny));
}
}
}
}
};
work(dis[0], 'S'), work(dis[1], 'R'), work(dis[2], 'B');
int mn1 = N + 1, mn2 = N + 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
mn1 = std::min(mn1, dis[0][id(i, j)] + std::min(dis[1][id(i, j)], dis[2][id(i, j)]) - (a[i][j] == '.'));
mn2 = std::min(mn2, dis[0][id(i, j)] + dis[1][id(i, j)] + dis[2][id(i, j)] - (a[i][j] == '.') * 2);
}
if (mn2 != N + 1)
std::cout << cnt - mn2 << '\n';
else if (mn1 != N + 1)
std::cout << cnt - mn1 << '\n';
else
std::cout << cnt << '\n';
};
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}C. 炼金术
https://www.becoder.com.cn/contest/6742/problem/3
给定 \(A_{1\cdots n}\) 和 \(B_{1\cdots n}\)，给定 \(m\) 次操作，形如：
1 l r x，将 \(A_{l\cdots r}\) 赋为 \(x\)。2 l r，询问 \(\min\limits_{i\in [l, r]}\left\{ \text{lcm}(A_i,B_i)+\dfrac{\text{lcm}(A_i,B_i)}{\gcd(A_i,B_i)} \right\}\) 的值。\(n,m\le 5\times 10^4,V=5\times 10^4\)。
待求没什么太好的性质，考虑更暴力的解决方式。
容易想到分块做法，对于整块赋值，容易想到对于每个 \(x\) 预处理块内答案。如何快速做到这一点？
一个想法是枚举 gcd 的值 \(p\)（显然只需枚举 \(x\) 的因子），计算 \(\dfrac {b_j\times x}p+\dfrac {b_j\times x}{p^2}\) 的最小值。
Tip：枚举到的 \(p\) 可能不是 gcd，但能保证一定能找到答案。
贪心地，只需对于块内 \(p\) 的最小倍数计算答案。这一点对于每个 \(b_i\) 枚举因数即能 \(O(n\sqrt V)\) 地预处理（因为有重复元素所以不是 \(O(V\log V)\)）、花费 \(O(V\log n)\) 的空间存储。
对于每个 \(x\)，复杂度不允许暴力枚举 \(x\) 的因子；发现 \(x\) 的因子是 \(x\) 与『对于所有 \(x\) 的质因子 \(m\)，\(\dfrac xm\) 的因子』的并。
考虑一个类 DP 的过程，则 \(f_x\gets f_{x\div m}\times m\)，再计算 \(x\) 自身的答案即可。由于 \(\omega(V)\) 平均为 \(\log\log V\)，此时预处理复杂度降低至 \(O(n\sqrt V + V\log V\sqrt n)\)。
用一点科技加速 gcd 即可。可选 \(O(1)\) gcd，或小范围打表 + 大范围暴力跳至小范围。
注意待求可能会爆 unsigned int，问就是挂分了。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("alchemy.in", "r", stdin);
std::freopen("alchemy.out", "w", stdout);
#else
std::freopen("./test/20251115/alchemy/alchemy4.in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
const long long inf = 1e18;
const int M = 5000, N = 50000;
std::vector<std::vector<int> > g(M + 1, std::vector<int> (M + 1));
for (int i = 0; i <= M; ++i) {
for (int j = 0; j < i; ++j)
g[i][j] = g[j][i];
g[i][i] = i;
for (int j = i + 1; j <= M; ++j)
g[i][j] = std::__gcd(i, j);
}
std::function<int(int, int)> gcd = [&](int x, int y) {
if (x <= M && y <= M)
return g[x][y];
return y ? gcd(y, x % y) : x;
};
std::vector<std::vector<int> > fac(N + 1);
for (int i = 2; i <= N; ++i)
if (fac[i].empty())
for (int j = i; j <= N; j += i)
fac[j].push_back(i);
int n, m;
std::cin >> n >> m;
std::vector<long long> a(n + 1), b(n + 1), p(n + 1);
auto calc = [&](long long x, long long y) {
auto g = gcd(x, y);
return x * y / g + x * y / g / g;
};
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
for (int i = 1; i <= n; ++i) {
std::cin >> b[i];
p[i] = calc(a[i], b[i]);
}
int siz = sqrt(n), k = (n + siz - 1) / siz;
std::vector<long long> u(k + 1, inf);
std::vector<int> L(k + 1), R(k + 1), id(n + 1), d(k + 1, -1);
std::vector<std::vector<long long> > mn(k + 1, std::vector<long long> (N + 1, inf)), s(k + 1, std::vector<long long> (N + 1));
for (int i = 1; i <= k; ++i) {
L[i] = R[i - 1] + 1, R[i] = std::min(L[i] + siz - 1, n);
for (int j = L[i]; j <= R[i]; ++j) {
id[j] = i, u[i] = std::min(u[i], p[j]);
for (int k = 1; k * k <= b[j]; ++k)
if (b[j] % k == 0) {
mn[i][k] = std::min(mn[i][k], b[j]);
mn[i][b[j] / k] = std::min(mn[i][b[j] / k], b[j]);
}
}
s[i][1] = mn[i][1] * 2;
for (int j = 2; j <= N; ++j) {
s[i][j] = mn[i][j] + mn[i][j] / j;
for (auto k : fac[j])
s[i][j] = std::min(s[i][j], s[i][j / k] * k);
}
}
auto pushdown = [&](int id) {
if (d[id] != -1) {
for (int i = L[id]; i <= R[id]; ++i)
p[i] = calc(d[id], b[i]);
d[id] = -1;
}
return;
};
auto ADD = [&](int l, int r, int x) {
int pl = id[l], pr = id[r];
pushdown(pl);
if (pl == pr) {
for (int i = l; i <= r; ++i)
p[i] = calc(x, b[i]);
u[pl] = *std::min_element(p.begin() + L[pl], p.begin() + R[pl] + 1);
return;
}
pushdown(pr);
for (int i = l; i <= R[pl]; ++i)
p[i] = calc(x, b[i]);
u[pl] = *std::min_element(p.begin() + L[pl], p.begin() + R[pl] + 1);
for (int i = L[pr]; i <= r; ++i)
p[i] = calc(x, b[i]);
u[pr] = *std::min_element(p.begin() + L[pr], p.begin() + R[pr] + 1);
for (int i = pl + 1; i < pr; ++i)
d[i] = x, u[i] = s[i][x];
return;
};
auto ASK = [&](int l, int r) {
int pl = id[l], pr = id[r];
pushdown(pl);
if (pl == pr)
return *std::min_element(p.begin() + l, p.begin() + r + 1);
pushdown(pr);
auto res = std::min(*std::min_element(p.begin() + l, p.begin() + R[pl] + 1), *std::min_element(p.begin() + L[pr], p.begin() + r + 1));
if (pl + 1 != pr)
res = std::min(res, *std::min_element(u.begin() + pl + 1, u.begin() + pr));
return res;
};
for (int op, l, r; m--; ) {
std::cin >> op >> l >> r;
if (op == 1) {
int x;
std::cin >> x, ADD(l, r, x);
}
else
std::cout << ASK(l, r) << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}