寂静的角落 星空在前,路在脚下
2021-04-02 模拟赛
发布于: 2021-04-03 更新于: 2021-04-11 分类于: 模拟赛

莫名其妙 $\color{Yellow}CE$ 了

$\color{Yellow}CE$ 太难受了。

题目 & 简易介绍

(占...

阅读更多
NOIO2021 #1
发布于: 2021-03-27 更新于: 2021-04-05 分类于: 游记

感受

裂开,太难了,这次比赛深刻的让我认识到了我菜的本质。

题目 & 简易介绍

(占位行,不然 Hexo 渲染下面会 Bug)

(占位行)

(占位行)

(占位行)

(占位行)

(占位...

阅读更多
2021-03-22 模拟赛
发布于: 2021-03-24 更新于: 2021-04-05 分类于: 模拟赛

emmmm~

T1 是区间DP,很容易就看出来了,然而题目出的却不知道如何合并……于是爆零。

T2是原题 [NOIP2014 提高组] 飞扬的小鸟,但是貌似特判写挂了卡掉了25pts。

T3是树形DP + 二次扫描换根,然而没复习到想写暴力发现图论忘光 dfs 都写挂了。

(占位行,不然 H...

阅读更多
2021-03-22 更新
发布于: 2021-03-22 更新于: 2021-04-05 分类于: 维护

Gitalk 评论功能已开启

阅读更多
扩展中国剩余定理 Extended Chinese remainder theorem, extcrt
发布于: 2021-03-14 更新于: 2021-04-05 分类于: 算法

$\color{Green}code$

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T>
inline T extcrt(T n, T *b, T *a) {
T ans = a[1], M = b[1], x, y;
for (register T i = 2; i <= n; ++i) {
T B = ((a[i] - ans) % b[i] + b[i]) % b[i];
T GCD = extgcd<T>(M, b[i], x, y);
x = qmul<T>(x, B / GCD, b[i]);
ans += M * x;
M *= b[i] / GCD;
ans = (ans + M) % M;
}
return ans;
}
阅读更多
中国剩余定理 Chinese remainder theorem, crt
发布于: 2021-03-14 更新于: 2021-04-05 分类于: 算法

$\color{Green}code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
template <typename T>
inline T crt(T n, T *ai, T *mi);
求解中国剩余定理
T 必须为整型类
*/
template <typename T>
inline T crt(T n, T *ai, T *mi) {
T m = 1, ans = 0;
T *M = new T[n + 5];
T *invM = new T[n + 5];
T *c = new T[n + 5];
for (register T i = 1; i <= n; ++i) m *= mi[i];
for (register T i = 1; i <= n; ++i) M[i] = m / mi[i];
for (register T i = 1; i <= n; ++i) invM[i] = inverse_extgcd(M[i], mi[i]);
for (register T i = 1; i <= n; ++i) c[i] = M[i] * invM[i];
for (register T i = 1; i <= n; ++i) ans = (ans + ai[i] * c[i] % m) % m;
delete[] M;
delete[] invM;
delete[] c;
return ans;
}
阅读更多
质因数分解 prime factorization
发布于: 2021-03-10 更新于: 2021-04-05 分类于: 算法

$\color{Green}code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
template <typename T>
inline T divide(T n, T *p, T *c);
对 n 分解质因数
T 必须为整型类
*/
template <typename T>
inline T divide(T n, T *p, T *c) {
int cnt = 0;
for (T i = 2; i * i <= n; ++i) {
if (n % i == 0) {
p[++cnt] = i, c[cnt] = 0;
while (n % i == 0) n /= i, c[i]++;
}
}
if (n > 1) p[++cnt] = n, c[cnt] = 1;
return cnt;
}
阅读更多
欧拉筛 sieve of Euler
发布于: 2021-03-05 更新于: 2021-04-11 分类于: 算法

$\color{Green}code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
template <typename T>
inline T get_prime_euler(T n, bool *isprime, T *prime_table);
求 n 以下的质数表
T 必须为整形类
*/
template <typename T>
inline T get_prime_euler(T n, bool *isprime, T *prime_table) {
T p = 0;
for (T i = 2; i <= n; ++i) isprime[i] = true;
for (T i = 2; i <= n; ++i) {
if (isprime[i]) prime_table[++p] = i;
for (T j = 1, t; j < p && (t = i * prime_table[j]) <= n; ++j) {
isprime[j] = false;
if (i % prime_table[j] == 0) break;
}
}
}
阅读更多
线性求乘法逆元
发布于: 2021-03-04 更新于: 2021-04-05 分类于: 算法

方法一

$\color{Green}code$

1
2
3
4
5
6
7
8
9
10
11
12
/*
template <typename T>
inline void get_inverse1(T n, T p, T *inverse);
线性求 n 以下关于模 p 的逆元
T 必须为整型类
*/
template <typename T>
inline void get_inverse1(T n, T p, T *inverse) {
inverse[1] = 1;
for(int i = 1; i <= n; ++i)
inverse[i] = p - p / i * inverse[p % i] % p;
}
阅读更多
乘法逆元 Multiplicative Inverse
发布于: 2021-03-03 更新于: 2021-04-05 分类于: 算法

方法一

使用费马小定理,这种方法要求 $p$ 是质数。

$$a \times a^{p - 2} \equiv 1 \pmod{p}$$

可得

$$a^{-1} = a^{p - 2}$$

然后就可以使用快速幂求逆元。

(占位行,不然 Hexo 渲染下面会 Bug)

(占位行)

(占位行)

(占位行)

如下:...

阅读更多