AtCoder Beginner Contest 444 简要题解-171主机测评

难难难。

比赛网址：https://atcoder.jp/contests/abc444

A – Repdigit

模拟即可。

#include <bits/stdc++.h>
using namespace std;

string s;

int main() {
cin >> s;
if (s[0] == s[1] && s[1] == s[2]) cout << "Yes";
else cout << "No";
return 0;
}

B – Digit Sum

枚举

∈

[

]

i \\in [1, n]

$i \in [1, n]$ ，对于每个

$i$ 计算数位和即可（初学者可以学习一下 cal 函数）。

#include <bits/stdc++.h>
using namespace std;

int n, k;

int cal(int u) {
int res = 0;
while (u) {
res += u % 10; u /= 10;
}
return res;
}

int main() {
cin >> n >> k; int ans = 0;
for (int i = 1; i <= n; ++i) {
if (cal(i) == k) ++ans;
}
cout << ans;
return 0;
}

C – AtCoder Riko

首先肯定将

a_i

$a_{i}$ 从小到大排序，设

$p$ 为最小的

$p$ 满足

a_p = a_n

$a_{p} = a_{n}$ ，分两种情况：

L

=

a

n

L = a_n

$L = a_{n}$ ，此时先判断

p

−

1

p – 1

$p - 1$ 是否为偶数，然后显然是

a

x

a_x

$a_{x}$ 与

a

p

−

x

a_{p – x}

$a_{p - x}$ 拼接起来，

a

i

,

i

∈

[

p

,

n

]

a_i, i \\in [p, n]

$a_{i}, i \in [p, n]$ 单独为一根。
L

=

a

1

+

a

n

L = a_1 + a_n

$L = a_{1} + a_{n}$ ，此时先判断

n

n

$n$ 是否为偶数，然后显然是

a

x

a_x

$a_{x}$ 与

a

n

+

1

−

x

a_{n + 1 – x}

$a_{n + 1 - x}$ 拼接起来。

具体实现可以看代码。

#include <bits/stdc++.h>
using namespace std;

const int N = 300000;

int n;
long long a[N + 10];

int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
if (n == 1) {
cout << a[1]; return 0;
}
sort(a + 1, a + n + 1);
if (a[1] == a[n]) {
cout << a[1];
if (n % 2 == 0) cout << ' ' << a[1] + a[n];
return 0;
}
int flag = 0, p = n, x;
while (a[p – 1] == a[p]) —p;
if ((p – 1) % 2 == 0) {
x = 1;
for (int i = 1; i < p; ++i) {
if (a[i] + a[p – i] != a[n]) x = 0;
}
if (x) cout << a[n], flag = 1;
}
if (n % 2 == 0) {
x = 1;
for (int i = 2; i < n; ++i) {
if (a[i] + a[n – i + 1] != a[1] + a[n]) x = 0;
}
if (x) {
if (flag) cout << ' ';
cout << a[1] + a[n];
}
}
return 0;
}

D – Many Repunit Sum

先用差分处理为

∑

\\sum_i b_i 10^i

$\sum_{i} b_{i} 1 0^{i}$ 的形式，然后进位即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 200000;

int n, s[2 * N + 10];

int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int u; cin >> u; ++s[0], —s[u];
}
for (int i = 1; i <= 2 * N; ++i) s[i] += s[i – 1];
for (int i = 1; i <= 2 * N; ++i) {
s[i] += s[i – 1] / 10; s[i – 1] %= 10;
}
int flag = 0;
for (int i = 2 * N; i >= 0; —i) {
if (s[i] > 0) flag = 1;
if (flag) cout << s[i];
}
return 0;
}

E – Sparse Range

考虑双指针，那么我们就要实现以下操作：

从右边加入一个数；
从左边减去一个数；
查询目前有多少对数

x

<

y

x < y

$x < y$ 满足

∣

a

x

−

a

y

∣

<

d

|a_x – a_y| < d

$∣ a_{x} - a_{y} ∣ < d$ ，记为

s

u

m

sum

$s u m$ 。

这个很容易使用 BIT 实现。具体的（以加入数

a_p

$a_{p}$ 为例），离散化后找到最小的

$l$ 和最大的

$r$ ，使得

∣

−

∣

−

∣

|a_l – a_p|, |a_r – a_p| < d

$∣ a_{l} - a_{p} ∣, ∣ a_{r} - a_{p} ∣ < d$ 。将

sum

$s u m$ 加上

(

)

query(l, r)

$q u ery (l, r)$ ，然后将位置

$p$ 加上

$1$ 。删除同理。

#include <bits/stdc++.h>
using namespace std;

const int N = 400000;

int n, d;
int a[N + 10], lsh[N + 10], cnt = 0;
int bit[N + 10];

void add(int x, int y) {
while (x <= cnt) {
bit[x] += y; x += (x & –x);
}
}

int query(int x) {
int res = 0;
while (x) {
res += bit[x]; x -= (x & –x);
}
return res;
}

int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> d; —d;
for (int i = 1; i <= n; ++i) {
cin >> a[i]; lsh[++cnt] = a[i];
}
sort(lsh + 1, lsh + cnt + 1);
cnt = unique(lsh + 1, lsh + cnt + 1) – lsh – 1;
long long ans = 0LL; int sum = 0;
for (int i = 1, j = 1; i <= n; ++i) {
int p = lower_bound(lsh + 1, lsh + cnt + 1, a[i]) – lsh;
int l = lower_bound(lsh + 1, lsh + cnt + 1, a[i] – d) – lsh;
int r = upper_bound(lsh + 1, lsh + cnt + 1, a[i] + d) – lsh – 1;
if (l <= r) sum += query(r) – query(l – 1);
add(p, 1);
while (sum > 0) {
p = lower_bound(lsh + 1, lsh + cnt + 1, a[j]) – lsh;
l = lower_bound(lsh + 1, lsh + cnt + 1, a[j] – d) – lsh;
r = upper_bound(lsh + 1, lsh + cnt + 1, a[j] + d) – lsh – 1;
add(p, –1);
if (l <= r) sum -= query(r) – query(l – 1);
++j;
}
ans += i – j + 1;
}
cout << ans;
return 0;
}

接下来的两题都非常困难最后一题会比较困难。

F – Half and Median

感谢群友提供了一个更简单的做法。

首先肯定二分答案，考虑

$d$ 是否能实现。那么我们实际就要算这么一件事：最多分解多少次使得每次分解出的

$2$ 个数均满足

≥

\\geq d

$\geq d$ ？

定义函数

(

)

f(u, d)

$f (u, d)$ 表示只有一个数

$u$ 时的答案，那么我们只需要快速计算

(

)

f(u, d)

$f (u, d)$ 就可以了。

然后我么能发现一个重要性质：

⌈

⌉

−

⌊

⌋

⌊

⌋

−

⌊

⌋

≤

\\lceil \\frac{a + 1}{2} \\rceil – \\lfloor \\frac{a}{2} \\rfloor = \\lfloor \\frac{a}{2} + 1 \\rfloor – \\lfloor \\frac{a}{2} \\rfloor \\leq 1

$⌈ \frac{a + 1}{2} ⌉ - ⌊ \frac{a}{2} ⌋ = ⌊ \frac{a}{2} + 1 ⌋ - ⌊ \frac{a}{2} ⌋ \leq 1$ 。

有了这个性质，我们可以 bfs

(

log

⁡

)

O(\\log V)

$O (lo g V)$ 算出

(

)

f(u, d)

$f (u, d)$ （具体实现参考代码）。

同理，我们也可以计算出进行对

$u$ 进行

(

)

f(u, d)

$f (u, d)$ 次操作后，还可以计算出

(

)

g(u, d)

$g (u, d)$ 次使得分解出的数一个

$< d$ ，一个

≥

\\geq d

$\geq d$ 。

那么有了

∑

(

)

\\sum_{i = 1}^n f(a_i, d)

$\sum_{i = 1}^{n} f (a_{i}, d)$ 和

∑

(

)

\\sum_{i = 1}^n g(a_i, d)

$\sum_{i = 1}^{n} g (a_{i}, d)$ 判断

$d$ 是否合法也就简单了。

最终时间复杂度

(

log

⁡

)

O(n \\log^2 V)

$O (n lo g^{2} V)$ 。代码咕咕咕，有时间再写。

G – Kyoen

做这题之前，你需要学会 Gaussian Integer（可以去 OI-Wiki 学习）。

点

(

)

(x, y)

$(x, y)$ 在圆上当且仅当满足：

(

−

)

(

−

)

\\left(x – \\frac{A}{C}\\right)^2 + \\left(y – \\frac{B}{C}\\right)^2 = \\frac{N}{C^2}

$(x - \frac{A}{C})^{2} + (y - \frac{B}{C})^{2} = \frac{N}{C ^{2}}$ 两边同乘

C^2

$C^{2}$ 得：

(

−

)

(

−

)

(Cx – A)^2 + (Cy – B)^2 = N

$(C x - A)^{2} + (C y - B)^{2} = N$ 令

−

X = Cx – A

$X = C x - A$ 、

−

Y = Cy – B

$Y = C y - B$ ，则问题等价于统计满足以下条件的整数对

(

)

(X, Y)

$(X, Y)$ 的数量：

X^2 + Y^2 = N X2+Y2=N

\\equiv -A \\pmod C X≡−A(modC)

\\equiv -B \\pmod C Y≡−B(modC) 方程 X 2 + Y 2 = N X^2 + Y^2 = N X2+Y2=N 描述的是高斯整数 z = X + Y i ∈ Z [ i ] z = X + Yi \\in \\mathbb{Z}[i] z=X+Yi∈Z[i] 的范数（Square Norm）。我们需要找出所有满足 N ( z ) = X 2 + Y 2 = N N(z) = X^2 + Y^2 = N N(z)=X2+Y2=N 的高斯整数 z z z。 在 Z [ i ] \\mathbb{Z}[i] Z[i] 中， N N N 的质因数分解对应如下情况：

情况 $i(1-i)^2 2=i(1−i)2。因子 2 E 2^E 2E 恰好对应一个唯一的高斯整数（不计单位元）： ( 1 + i ) E (1+i)^E (1+i)E。$
情况 $\\equiv 3 \\pmod 4 P≡3(mod4)： P P P 是高斯素数。若 E E E 为奇数，则 N N N 无法表示为两个平方数之和，答案为 0 0 0；若 E E E 为偶数，则因子 P E P^E PE 贡献 P E / 2 P^{E/2} PE/2。$
情况 $\\equiv 1 \\pmod 4 P≡1(mod4)： P P P 可分解为一对共轭高斯素数 P = π ⋅ π ˉ P = \\pi \\cdot \\bar{\\pi} P=π⋅πˉ（其中 π = a + b i \\pi = a+bi π=a+bi）。因子 P E P^E PE 允许 E + 1 E+1 E+1 种不同的高斯整数组合： π k π ˉ E − k \\pi^k \\bar{\\pi}^{E-k} πkπˉE−k（ k = 0 , 1 , … , E k = 0, 1, \\dots, E k=0,1,…,E）。$

任意满足

(

)

N(z) = N

$N (z) = N$ 的

$z$ 均可表示为：

⋅

∏

z = u \\cdot \\prod z_j

$z = u \cdot \prod z_{j}$ 其中

∈

{

−

}

u \\in \\{1, i, -1, -i\\}

$u \in {1, i, - 1, - i}$ 是单位元，

z_j

$z_{j}$ 是由

P_j^{E_j}

$P_{j}^{E_{j}}$ 贡献的部分。

由于

≤

C \\le 50

$C \leq 50$ ，坐标

(

)

(X \\bmod C, Y \\bmod C)

$(X mod C, Y mod C)$ 构成的状态空间大小仅为

2500

C^2 = 2500

$C^{2} = 2500$ 。我们可以使用动态规划（DP）维护达到特定

(

)

(X, Y)

$(X, Y)$ 模

$C$ 状态的方案数。

定义 dp[r][i] 为构造出高斯整数

$z$ 使得其实部

≡

(

)

\\equiv r \\pmod C

$\equiv r (mod C)$ 、虚部

≡

(

)

\\equiv i \\pmod C

$\equiv i (mod C)$ 的方案数。

对每个质因数

P_i^{E_i}

$P_{i}^{E_{i}}$ 分类处理：

$(1+i)^E \\bmod C z=(1+i)EmodC，并更新 DP 状态： ( r , i ) → ( r , i ) ⋅ z m o d C (r, i) \\to (r, i) \\cdot z \\bmod C (r,i)→(r,i)⋅zmodC。$
$\\equiv 3 \\pmod 4 P≡3(mod4)：若 E E E 为奇数，直接返回 0 0 0；否则用 z = P E / 2 m o d C z = P^{E/2} \\bmod C z=PE/2modC 更新 DP。$
P

≡

1

(

m

o

d

4

)

P \\equiv 1 \\pmod 4

$P \equiv 1 (mod 4)$ ：找到

π

=

a

+

b

i

\\pi = a+bi

$π = a + bi$ 使得

a

2

+

b

2

=

P

a^2 + b^2 = P

$a^{2} + b^{2} = P$ 。此时有

E

+

1

E+1

$E + 1$ 个可能值：

s

k

=

π

k

π

ˉ

E

−

k

s_k = \\pi^k \\bar{\\pi}^{E-k}

$s_{k} = π^{k} \overset{π}{ˉ}^{E - k}$ 。
- 若 $\\gcd(P, C) = 1 gcd(P,C)=1，序列 s k s_k sk 构成模 C C C 下的等比数列 s k = π ˉ E ( π / π ˉ ) k m o d C s_k = \\bar{\\pi}^E (\\pi/\\bar{\\pi})^k \\bmod C sk=πˉE(π/πˉ)kmodC。由于状态空间有限，该序列必进入循环，可在 O ( 循环长度 ) O(\\text{循环长度}) O(循环长度) 或 O ( C 2 ) O(C^2) O(C2) 内统计各状态的总次数。$
- 若 $\\gcd(P, C) > 1 gcd(P,C)>1（即 P ∣ C P|C P∣C），序列最终会变为常数（通常为 0 0 0）或进入循环。鉴于 C ≤ 50 C \\le 50 C≤50，可直接模拟前若干项与末尾若干项。$

处理完所有质因数后，DP 表中存储了所有可能的高斯整数乘积

prod

z_{\\text{prod}} \\bmod C

$z_{prod} mod C$ 的方案数。最后枚举四个单位元

∈

{

−

}

u \\in \\{1, i, -1, -i\\}

$u \in {1, i, - 1, - i}$ ：对每个状态 dp[r][i]，若

(

)

≡

(

−

)

(

)

(r + r_u, i + i_u) \\equiv (-A, -B) \\pmod C

$(r + r_{u}, i + i_{u}) \equiv (- A, - B) (mod C)$ ，则将 dp[r][i] 加入答案。

时间复杂度

(

)

O(M C^4)

$O (M C^{4})$ ，由于

$C$ 比较小，所以可以通过。

#include <bits/stdc++.h>
using namespace std;

struct mint {
long long v;
mint(long long _v = 0) : v((_v % 998244353 + 998244353) % 998244353) {}
long long val() const {return v;}
mint& operator += (const mint& o) {v = (v + o.v) % 998244353; return *this;}
mint operator + (const mint& o) const {return mint(*this) += o; }
mint operator * (const mint& o) const {return mint((v * o.v) % 998244353);}
};

struct comp {
long long r, i;
bool operator < (const comp& o) const {
if (r != o.r) return r < o.r;
return i < o.i;
}
bool operator == (const comp& o) const {
return r == o.r && i == o.i;
}
};

long long A, B, C, M;
mint dp[65][65], nxt[65][65];
comp item_c[4005]; mint item_v[4005];
map<comp, int> vis; comp path[4005]; int path_cnt;
comp unit[4];

comp mul(comp a, comp b) {
long long new_r = (a.r * b.r – a.i * b.i) % C;
long long new_i = (a.r * b.i + a.i * b.r) % C;
if (new_r < 0) new_r += C;
if (new_i < 0) new_i += C;
return (comp){new_r, new_i};
}

comp q_pow(comp u, long long v) {
comp res = (comp){1LL % C, 0LL};
while (v) {
if (v & 1LL) res = mul(res, u);
u = mul(u, u), v >>= 1;
}
return res;
}

long long inv_mod(long long a, long long m) {
long long b = m, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
return (u % m + m) % m;
}

comp inv(comp u) {
long long nrm = (u.r * u.r + u.i * u.i) % C;
long long ni = inv_mod(nrm, C);
return (comp){u.r * ni % C, (C – u.i % C) * ni % C};
}

long long gcd(long long a, long long b) {
while (b) {a %= b; swap(a, b);}
return a;
}

void convolve(int cnt) {
for (int i = 0; i < C; ++i) for (int j = 0; j < C; ++j) nxt[i][j] = 0LL;
for (int idx = 1; idx <= cnt; ++idx) {
comp c = item_c[idx]; mint v = item_v[idx];
for (int r = 0; r < C; ++r) {
for (int i = 0; i < C; ++i) {
if (dp[r][i].val() == 0LL) continue;
comp ne = mul((comp){(long long)r, (long long)i}, c);
nxt[ne.r][ne.i] += dp[r][i] * v;
}
}
}
for (int i = 0; i < C; ++i) for (int j = 0; j < C; ++j) dp[i][j] = nxt[i][j];
}

int main() {
cin >> A >> B >> C >> M;
for (int i = 0; i < 65; ++i) for (int j = 0; j < 65; ++j) dp[i][j] = 0;
dp[1 % C][0] = 1;
for (int idx = 0; idx < M; ++idx) {
long long P, E; cin >> P >> E;
if (P == 2) {
item_c[1] = q_pow((comp){1 % C, 1 % C}, E); item_v[1] = 1LL;
convolve(1);
}
else if (P % 4 == 3LL) {
if (E & 1LL) { cout << 0; return 0; }
item_c[1] = q_pow((comp){P % C, 0LL}, E / 2LL); item_v[1] = 1LL;
convolve(1);
}
else {
long long a = –1, b = –1;
for (long long x = 1; x * x < P; ++x) {
long long rem = P – x * x; long long y = round(sqrt(rem));
if (y * y == rem) { a = x, b = y; break; }
}
comp pi = (comp){a % C, b % C}, pi_bar = (comp){a % C, (C – b % C) % C};
map<comp, mint> mp;
if (gcd(P, C) == 1) {
comp ratio = mul(pi, inv(pi_bar)), cur = q_pow(pi_bar, E);
vis.clear(); path_cnt = 0;
for (long long k = 0LL; k <= E; ++k) {
if (vis.count(cur)) {
int s_idx = vis[cur]; int len = path_cnt – s_idx;
long long rem = (E + 1LL – k);
long long cyc = rem / len, lst = rem % len;
for (int i = s_idx; i < path_cnt; ++i) mp[path[i]] += cyc;
for (int i = 0; i < (int)lst; ++i) mp[path[s_idx + i]] += 1LL;
break;
}
vis[cur] = path_cnt; path[path_cnt++] = cur; mp[cur] += 1LL;
cur = mul(cur, ratio);
}
}
else {
for (long long k = 0; k <= min(E, 100LL); ++k) mp[mul(q_pow(pi, k), q_pow(pi_bar, E – k))] += 1;
if (E > 200LL) {
mp[mul(q_pow(pi, 101LL), q_pow(pi_bar, E – 101LL))] += (E – 201LL + 1LL);
for (long long k = E – 99LL; k <= E; ++k) mp[mul(q_pow(pi, k), q_pow(pi_bar, E – k))] += 1;
}
else if (E > 100LL) {
for (long long k = 101LL; k <= E; ++k) mp[mul(q_pow(pi, k), q_pow(pi_bar, E – k))] += 1;
}
}
int cnt = 0;
for (auto const& t : mp) { ++cnt; item_c[cnt] = t.first, item_v[cnt] = t.second; }
convolve(cnt);
}
}
mint ans = 0LL;
unit[0] = (comp){1 % C, 0}; unit[1] = (comp){0, 1 % C};
unit[2] = (comp){(C – 1) % C, 0}; unit[3] = (comp){0, (C – 1) % C};
long long tr = (C – A % C) % C, ti = (C – B % C) % C;
for (int r = 0; r < C; ++r) {
for (int i = 0; i < C; ++i) {
if (dp[r][i].val() == 0LL) continue;
for (int _ = 0; _ < 4; ++_) {
comp p = mul((comp){(long long)r, (long long)i}, unit[_]);
if (p.r == tr && p.i == ti) ans += dp[r][i];
}
}
}
cout << ans.val();
return 0;
}

AtCoder Beginner Contest 444 简要题解

A – Repdigit

B – Digit Sum

C – AtCoder Riko

D – Many Repunit Sum

E – Sparse Range

F – Half and Median

G – Kyoen

相关推荐

评论抢沙发

热门标签

热门文章

最新文章

归档

分类

A – Repdigit

B – Digit Sum

C – AtCoder Riko

D – Many Repunit Sum

E – Sparse Range

F – Half and Median

G – Kyoen

相关推荐

评论 抢沙发

热门标签

热门文章

最新文章

归档

分类

评论抢沙发