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
链接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
F Fireworks链接https://ac.nowcoder.com/acm/contest/10272/F
题意你想要放一个的烟花，你可以花费时间n来制作一个烟花，花费时间m点燃所有的烟花，烟花被点燃以后就释放了，但是他只有$\frac{p}{10^4}$的概率完美释放，你想完美释放至少一个烟花，那么需要的最少时间的期望是多少？
T组输入
阅读全文
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
A Matrix Equation链接https://ac.nowcoder.com/acm/contest/10662/A
题意给你两个01方阵AB，你要找到一个01矩阵C，使得在2的模群中$A\times C=B\cdot C$ ,其中 $\times$ 为一般矩阵乘积， 符号 $\cdot$ 为哈达马积（Hadamard product）
问你C有多少个解
阅读全文
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
L Simone and graph coloring链接https://ac.nowcoder.com/acm/contest/12548/L?&headNav=acm
题意给你一个排列，排列的长度不超过$10^6$。你要对他的每一个元素进行染色，要求染色后不存在任何一个逆序对的两个元素颜色相同。你需要输出染色的数组。
阅读全文