Yukicoder 20260826 每日
1- No.2708 Jewel holder 1.5$
No.2708 Jewel holder - yukicoder
问题描述
有一个纵向 $H$ 行、横向 $W$ 列的网格。用 $(i,j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。
到达写有 o 的格子时，会获得 1 颗宝石；到达写有 x 的格子时，会被没收 1 颗宝石，# 格子无法通过。
对于每个 $i,j (1 \leq i \leq H, 1\leq j \leq W)$，格子 $(i,j)$ 的信息由字符 $A_{i,j}$ 给出。
如果 $A_{i,j}$ 是 o，则到达该格子时必定获得 1 颗宝石；如果 $A_{i,j}$ 是 x，则到达该格子时必定被没收 1 颗宝石。
保证格子 $(1,1)$ 一定是能获得宝石的 o 格子。
另外，保证格子 $(1,1)$ 和格子 $(H,W)$ 一定不是 # 格子。
Nafmo 君在持有 0 颗宝石的状态下，到达格子 $(1,1)$ 并获得了 1 颗宝石。
Nafmo 君希望通过重复向右和向下移动，从格子 $(1,1)$ 以最短路径到达格子 $(H,W)$。但是，如果在被没收宝石时出现“一颗宝石都没有”的情况，则该路径视为无效。
请计算满足上述条件的路径有多少种。
H W
A_{1,1}A_{1,2}...A_{1,W}
：
A_{H,1}A_{H,2}...A_{H,W}
- $2 \leq H,W \leq 10$
- $H,W$ 是整数
-
$A_{i,j}$ 是
o、x、#中的任意一个 - $A_{1,1} = $
o - $A_{H,W} \neq $
#
题解
比较显然的一个想法是搜索，每一次搜下一个点的时候，计算当前宝石数量，所以你搜索过程中要传递两个权值：当前坐标、当前宝石数量。
直接写就可以：
const int dx[] = {0, 1};
const int dy[] = {1, 0};
int H, W;
char A[12][12]{};
ll ans = 0;
void dfs(int x, int y, int val) {
if(A[x][y] == 'o') val += 1;
else if(A[x][y] == 'x') val -= 1;
if(x == H - 1 && y == W - 1 && val >= 0) ans += 1, return;
if(val >= 0) {
rep(i, 2) {
int nx = x + dx[i], ny = y + dy[i];
if(nx >= 0 && nx < H && ny >= 0 && ny < W && A[nx][ny] != '#') dfs(nx, ny, val);
}
}
}
{
rd(H, W, A(H)(W));
dfs(0, 0, 0);
wt(ans);
}当然也有一些很厉害的写法，可以用 分层图 DP，来写：
$$
dp[i][j][val] = 到达(i,j)点且宝石数刚好是val个的路径数
$$
那么答案就是 $\sum_{val\ge 0} dp[H-1][W-1]$，初始值就是 $dp[0][0][1] = 1$
当然还要考虑一下 val 层要开多大，不难发现，最多采集 20 个宝石，于是 val 是 20最大
const int dx[] = {0, 1};
const int dy[] = {1, 0};
ll f[11][11][21]{0};
char A[11][11]{};
int @H,@W;
rd(A(H)(W));
f[0][0][1] = 1;
rep(i, H) rep(j, W) {
if(A[i][j] == '#') continue;
rep(val, 21) {
if(f[i][j][val] == 0) continue;
rep(k, 2) {
int nx = i + dx[k], ny = j + dy[k];
if(nx >= 0 && nx < H && ny >= 0 && ny < W && A[nx][ny] != '#') {
int nval = val + (A[nx][ny] == 'o' ? 1 : -1);
if(nval < 0) continue;
f[nx][ny][nval] += f[i][j][val];
}
}
}
}
ll ans = 0;
rep(val, 21) ans += f[H - 1][W - 1][val];
wt(ans);2 - No.132 点到平面距离 3.0$
问题描述
给定三维空间中的一个点 (P)，以及 (N) 个点 (Q_1,Q_2,\ldots,Q_N)。
用 ({\rm dist}(i,j,k)) 表示点 (P) 与由点 (Q_i,Q_j,Q_k) 所确定的平面之间的距离。
请编写一个程序，求点 (P) 与所有由 (Q_i,Q_j,Q_k) 确定的平面之间的距离之和。
即，求 (\displaystyle \sum_{1 \leq i < j < k \leq N} {\rm dist}(i,j,k)) 的值。
点 (x) 与平面 (y) 的距离，是指点 (x) 到从点 (x) 向平面 (y) 所作垂线的垂足之间的距离。
N
P_x P_y P_z
X_1 Y_1 Z_1
X_2 Y_2 Z_2
:
X_N Y_N Z_N
- (N \in {100, 200, 300})
- (-1000 \leq P_x, P_y, P_z \leq 1000)：点 (P) 的坐标
- (-1000 \leq X_k, Y_k, Z_k \leq 1000)：点 (Q_k) 的坐标
很模板的题目，但是如果第一次写，不是特别好写（
点到直线的距离公式是众所周知的，直线 $ax+by+c=0$ 与点 $(p,q)$ 的距离是：$\frac{|ap+bq+c|}{\sqrt{p^2+q^2}}$
于是我们也可以写出三维空间的对应式子，直线 $ax+by+cz+d=0$ 与点 $(p, q, r)$：
$$
\frac{|ap+bq+cr+d|}{\sqrt{p^2+q^2+r^2}}
$$
还有一个式子：当给定空间内两个点的时候，这两个点与原点所构成的平面 $ax+by+cz=0$的 (a,b,c) 实际上刚好有：
$$
(a,b,c) = (x_1,y_1,z_1) \times (x_2,y_2,z_2)
$$
这时候刚好有 $(a,b,c)$ 是这个平面的法向量，这是叉乘的定义
于是可以写出代码
int n;
double x[310], y[310], z[310];
{
rd(n);
rd((x, y, z)(n + 1));
double s;
rep(i, 1, n + 1) rep(j, i + 1, n + 1) rep(k, j + 1, n + 1) {
double p=(y[j]-y[i])*(z[k]-z[i])-(z[j]-z[i])*(y[k]-y[i]);
double q=(z[j]-z[i])*(x[k]-x[i])-(x[j]-x[i])*(z[k]-z[i]);
double r=(x[j]-x[i])*(y[k]-y[i])-(y[j]-y[i])*(x[k]-x[i]);
s+=fabs(p*(x[0]-x[i])+q*(y[0]-y[i])+r*(z[0]-z[i]))/sqrt(p*p+q*q+r*r);
}
wt(s);
}3 - No.1760 集合互质 4.0$
No.1760 集合互质 - yukicoder --- No.1760 Setwise Coprime - yukicoder
题目描述
给定 $N$，题目要求统计有序对 $(A,B)$ 的数量，满足：
- $A,B\neq \varnothing$
- $A\cap B=\varnothing$
- $\gcd(A)=1$
- $\gcd(B)=1$
其中 $A,B\subseteq {1,2,\dots,N}$，答案取模 $998244353$。
- $2 \le N \le 2 \times 10^5$
好难的题，感觉根本不是4星（
先分析一下吧，可以先求一下 $\set{1,2,3,\dots,N}$ 中有多少个非空子集合 $S$ ，其 $\gcd(S) = 1$
我们设 $C = |\set{S \subseteq \set{1,\ldots,N} : S \neq \emptyset, gcd(S) = 1}|$
而还有一个式子可以表示 $C$：
$$
C = \sum_{\emptyset \neq S \subseteq[1,N]} [gcd(S) = 1]
$$
根据莫反我们有 $[x = 1] = \sum_{d | x} \mu(d)$
我们令 $x = gcd(S)$，于是 $C$ 就被写成了 ：
$$
C =\sum_{\emptyset \neq S \subseteq[1,N]} \sum_{d | gcd(S)} \mu(d)
$$
这里涉及一个交换求和次序，需要解释一下，这里实际上是对一个二元组 $(S, d)$ 求和，本身其是：
$$
C = \sum_{S \neq \emptyset} \sum_{d | gcd(S)} \mu(d)
$$
意思是：先枚举一个非空集合 $S$，再枚举其所有满足 $d | gcd(S)$ 的 $d$
而我们可以把它换成先枚举 $d$，后枚举 $S$
于是写成：
$$
\sum_{d = 1} ^N \sum_{S \neq \emptyset \and d|gcd(S)} \mu(d)
$$
对于一个固定的 $d$，$\mu(d)$ 与 $S$ 无关，于是提出来：
$$
\sum_{d=1}^N \mu(d) \sum_{S \neq \emptyset \and d | gcd(S)} 1
$$
现在我们就可以求出第一步 $C$ 了，但是原题还有一个约束 $A \cap B = \emptyset$，也就是两个集合无交，答案其实可以写出来：
$$
Ans = \sum_{A \neq \emptyset ; B \neq \emptyset ; A \cap B \neq \emptyset} [gcd(A) = 1][gcd(B) = 1]
$$
分别应用莫反： $[gcd(A) = 1] = \sum_{d | gcd(A)} \mu(d)$ 与 $[gcd(B) = 1] = \sum_{e | gcd(B)} \mu(e)$
于是有：
$$
Ans = \sum_{A,B \neq \emptyset; A \cap B \neq \emptyset} \sum_{d | gcd(A)}\sum_{e | gcd(B)} \mu(d) \mu(e)
$$
我们设 $F(d, e) = \sum [A,B \neq \emptyset][A\cap B \neq \emptyset][d | gcd(A)] [e | gcd(B)]$
上面式子和刚刚一样交换求和次序之后就有：
$$
Ans = \sum_{d=1}^N \sum_{e=1}^N \mu(d)\mu(e) F(d,e)
$$
现在问题变成了，固定 $d, e$ 之后， $F(d,e)$ 如何计算？
让我们首先考虑 $A$ 的取值：因为 $d | gcd(A)$，于是 $[1,N]$ 中 $d$ 的倍数有： $x = \lfloor N/d \rfloor$ 个。
同理 $B$ 只能选 $e$ 的倍数，一共有 $y = \lfloor N /e \rfloor$ 个数字。
如果允许相交的话，能选择的集合数量就是 $2^x \cdot 2 ^y$ 种集合组
所以这里要考虑能被同时选的数字：
如果一个数字 $v$ 既可以被 $A$ 也可以被 $B$ 选，那么就是：$d |v \and e|v \Rightarrow lcm(d,e) | v$
就是一共 $z = \lfloor \frac{N}{lcm(d,e)} \rfloor$ 个元素个数
这样一来 $[1,N]$ 中的数就被分成了三种
- 只能给 A 的：
- 有 $x - z$ 个，每个元素只有两种状态：进入或不进入A，贡献就是 $2 ^ {x -z}$
- 只能给 B 的：
- 有 $y - z$ 个，贡献就是 $2^{y-z}$
- A，B 都可以选择的：
- 有 $z$ 个，每个元素有四个状态：都不进，只进 A 或 B，同时进入 A 和 B。但是最后一种不合法，于是只有三种状态，贡献就是 $3 ^ z$
所以当允许空集合的时候，方案数就是 $2^{x-z}2^{y-z}3^{z} = 2^{x+y-2z} 3^z$ 个。
而这里有个关键的问题，题目中要求 A 与 B 非空！
刚刚的统计中没有去掉 A 和 B 是空集的情况，于是我们要容斥掉这些情况：
当 $A = \emptyset$ 的时候，B 的选法有 $2^y$ 个，反过来也是 $2^x$ 种，但是两个都是空的被多减了一次，于是加回来 $1$
于是我们有了:
$$
F(d,e) = 2^{x+y-2z}3^z - 2^x - 2 ^y + 1; x = \lfloor \frac{N}{d}\rfloor;y = \lfloor\frac{N}{e}\rfloor; z = \lfloor\frac{N}{lcm(d,e)}\rfloor
$$
我们就有了最终答案完全的一个式子！
$$
Ans = \sum_{d=1}^N\sum_{e=1}^N \mu(d)\mu(d)(2^{x+y-2z}3^z - 2^x - 2^y + 1)
$$
于是你看了一下数据范围，$N = 2 \times 10^5$，$O(N^2)$ 并不可以通过。
怎么办呢？这里是一个经典 trick，正难则反！
还记得我们之前算的 $C$ 么，如果不管相交的话，A 有 C 种， B 也有 C 种，并且 A, B 有序；
所以 $C^2$ 统计的是 A, B 非空，且 $gcd(A) = gcd(B) = 1$，但是其中允许了 $A \cap B \neq \emptyset$
于是我们只需要把允许相交改成不允许相交。
我们知道，固定 $d, e$ 之后，如果允许相交，那么有 $2^{x+y}$ 种集合组；如果不允许相交，那么有 $2^{x+y-2z}3^z$ 种集合组。
其变化量 $\Delta(d,e) = 2^{x+y-2z}3^z - 2^{x+y}$ 种，而这里不考虑空集的原因是，空集不会受到不相交这个限制影响
于是我们就求出来了新的答案式子：
$$
Ans = C^2 + \sum_{d=1}^N \sum_{e=1}^N \mu(d)\mu(e) \Delta(d,e) = C^2 + \sum_{d=1}^N \sum_{e=1}^N \mu(d)\mu(e)(2^{x+y-2z}3^z - 2^{x+y})
$$
有人说，这不是还是 $N^2$ 的么。
但是注意到 $z$ 当 $lcm(d,e) \gt N$ 的时候一定是 $0$，此时 $\Delta(d,e) = 0$，也就是对于 $lcm(d,e) \gt N$ 的 $(d, e)$ 对不用计算
问题就又变成了：
快速枚举所有满足 $lcm(d,e) \le N$ 的 $(d,e)$
因为 $\mu(d)\mu(e) \neq 0$，所以对于 $lcm(d,e)$ 的每个质因子只有三种可能 ：只给 $d$，只给 $e$，同时给 $d, e$
复杂度就是 $O(3^{\omega(L)})$ 的。
#define MD 998244353
using mm = Mint;
const int MAXN = 2d5 + 5;
int mu[MAXN], lp[MAXN], p[MAXN], pc;
mm pw2[MAXN * 2], pw3[MAXN];
{
int @N;
mu[1] = 1;
rep(i, 2, N + 1) {
if(!lp[i]) lp[i] = i, p[pc ++] = i, mu[i] = -1;
rep(j, pc) {
int q = p[j];
if(i * q > N) break;
lp[i * q] = q;
if(i % q == 0) {mu[i * q] = 0; break;}
mu[i * q] = -mu[i];
}
}
pw2[0] = 1;
rep(i, 1, 2 * N + 1) pw2[i] = pw2[i - 1] * 2;
pw3[0] = 1;
rep(i, 1, N + 1) pw3[i] = pw3[i - 1] * 3;
mm C = 0;
rep(d, 1 , N + 1) C += mu[d] * (pw2[N / d] - 1);
mm ans = C * C;
rep(L, 1, N + 1) {
if(mu[L] == 0) continue;
int fac[10], k = 0, x = L;
while(x > 1) fac[k ++] = lp[x], x /= lp[x];
int limit = 1; rep(i, k) limit *= 3;
int z = N / L;
rep(bit, limit) { // 三进制枚举
int d = 1, e = 1, t = bit;
rep(i, k) {
int s = t % 3; t /= 3;
if(s == 0) d *= fac[i];
else if(s == 1) e *= fac[i];
else d *= fac[i], e *= fac[i];
}
int a = N / d, b = N / e;
mm delta = pw2[a + b - 2 * z] * pw3[z] - pw2[a + b];
ans += mu[d] * mu[e] * delta;
}
}
wt(ans);
}