这么爱计数
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;
}