Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 简介快速幂是能快速计算一个幂的方案，他可以作用于所有满足结合律、封闭性的二元运算，即半群 定义不妨假设这个二元运算为$\circ$,两个元素进行运算为$x\circ y$,当$xy$同为$x$时，不妨设$x^2=x\circ x$, 同样的$x^1=x$, 当然$x^0=e$, 还有$x^k=x^{k-1}\circ x$ 快速幂核心思想在半群中，只要$k=u+v$一定有$x^k=x^u\circ x^v$. 所以我们可以把k看作一个二进制数，把$x^k$分解为$x^{2^{p_1}}\circ x^{2^{p_2}}\circ x^{2^{p_3}}\circ \circ \circ x^{2^{p_n}}$ 这里最多分解为$\log_2(k)$个元素，而且每个元素可以由前k个元素获取，所以只需要进行$log_2(k)$次二元计算即可的到最终答案。 阅读全文…

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 比赛链接https://ac.nowcoder.com/acm/contest/15167 A. A Warm Welcome题意输出Shenzhen Institute of Computing ... 阅读全文…

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 链接https://ac.nowcoder.com/acm/contest/15801?&headNav=www B Graph题意n个点的带权树，你可以删边，但要保证删边后图联通，可以加边，但要保证加边后所有简单环的异或和为0。 现在你可以随便操作，需要操作后的树的边权和最小。 题解题目中的两个操作都不会影响两个顶点之间路径的异或和。所以实际上相当于给了一个完全图，两个点之间的边权就是原始树上这两个点之间的路径的异或和，你要求一个最小生成树。 很多人都知道最小生成树有Kruskal算法和Prim算法，但是很少有人知道第三个算法：Boruvka算法，因为这个算法不常用。 阅读全文…

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 链接https://ac.nowcoder.com/acm/contest/15789 B Basic Gcd Problem题意定义$$f_c(x)=\begin{cases}max_{i=1}^n c\cdot f_c(\gcd(i,x)) &x\gt1\1&x=1\end{cases}$$ 输入c和x 题解f函数迭代次数越多，则值越大，也就是x取gcd的次数越多越好，所以每次选择x的最大因子即可。最终使用快速幂解决。 阅读全文…

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 比赛链接https://ac.nowcoder.com/acm/contest/15688?&headNav=www A All with Pairs题意给你字符串n个字符串$s_1$，$s_2$，$s_3$，… $s_n$给你函数$f(s,t)$，其值为最大的长度w，使得s的长度为w的前缀和t的长度为w的后缀相同完全。 你要计算$$\sum_{i=1}^{n}\sum_{i=1}^{n}f(s_i,s_j)^2 \mod 998244353$$ 数据范围$n<10^5$, 字符串总长度小于$10^6$ 阅读全文…

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 前言这几天训练的太频繁了，一天一场比赛，简直不要太👹。从四月25号到5月3号9天开了7场。 比赛地址https://ac.nowcoder.com/acm/contest/9925 阅读全文…

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 比赛链接http://codeforces.com/gym/102798 A. Golden Spirit有一个桥，桥两边都有n个老人，你桥的一边，你可以花时间x把一个老人带到对面，然后你可以接着把那边的老人带回来，你也可以原地等待，所有老人移动一次以后需要休息t分钟，问你至少花费多少时间，能让所有老人都互相跑到对面，然后又回到原本的位置。 123456789101112131415#include<bits/stdc++.h>using namespace std;#define ll long longint main(){ int T; scanf("%d", &T); while(T--) { ll n, x, t; scanf("%lld %lld %lld", &n, &x, &t); ll y1 = max(x + 2 * t - 2 * n * t, 0ll); ll y2 = max(x - 2 * n * t, 0ll); ll ans1 = y1 + 4 * n * t, ans2 = y2 + (4 * n + 1) * t; printf("%lld\n", min(ans1, ans2)); }} 阅读全文…

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 比赛链接http://codeforces.com/gym/102822 D. Defuse the Bombs题意有一些炸弹，给你一个数组$a$，他们$a_i$秒后会爆炸，你是一个拆弹专家，你可以... 阅读全文…

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 比赛链接https://ac.nowcoder.com/acm/contest/15880?&headNav=www B Binary Vector题意随机n个n维01向量，询问这个n个向量线性无关的概率 题解考虑第一个向量，可以有$2^n-1$选择，你不可以选择全为0的向量 然后考虑与第一个向量线性无关的向量，可以有$2^n-2^1$个，因为第一个向量的0倍和1倍不能选。 然后考虑与第一个和第二个向量线性无关的向量，可以有$2^n-2^2$个 于是最终的方案数为$\begin{aligned}\prod_{i=0}^{n}2^n-2^i\end{aligned}$ ， 考虑分母为$2^{n\cdot n}$$$\begin{aligned}&\frac{\begin{aligned}\prod_{i=0}^{n-1}2^n-2^i\end{aligned}}{2^{n\cdot n}}\&=\begin{aligned}\prod_{i=0}^{n-1}1-\frac{2^i}{2^n}\end{aligned}\&=\begin{aligned}\prod_{i=1}^{n}1-2^{-i}\end{aligned}\end{aligned}$$ 阅读全文…

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 核心思想蒙哥马利运算是一种新的运算，他把乘模简化为对进制数的除法，以及简单加法，这就使得乘模避开了大量的取模试除。 蒙哥马利表示法例如$a%mod$的蒙哥马利表示法为$f(a) = a\times p% mod$，$p$是一个进制数， 我们储存$f(a)$的值，而不是a的值。 复原于是我们很容易发现，对于蒙哥马利表示法变回普通表示法时只需要乘p对mod的逆元即可。 p的取值蒙哥马利表示法会找一个进制数使得普通数字转化为蒙哥马利表示法，一般来说这是一个刚好大于模数的进制数。 阅读全文…