Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 介绍球盒模型指的是把球放入盒子里的题目模型（强行解释） 分为盒子同或不同，球同或不同，盒子允许空或不空，所以一共八种问题 结论不妨假设n个球，m个盒子 盒异，球同，盒子允许空 $C_{m+n-1}^{m-1}$ 盒异，球同，盒不允许空$C_{n-1}^{m-1}$ 盒同，球同，盒子允许空$\begin{aligned}\prod _{j=1}^{m}\frac{1}{1-x^{j}}\end{aligned}$中的$x^n$系数 盒同，球同，盒不允许空$\begin{aligned}x^m\prod _{j=1}^{m}\frac{1}{1-x^{j}}\end{aligned}$中$x^n$的系数 盒异，球异，盒子允许空 $m^n$ 盒异，球异，盒不允许空$\begin{aligned}\sum _{k=0}^{m}(C_m^k(-1)^{m-k} ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 比赛链接http://codeforces.com/gym/102832 A. Krypton题意充游戏币，首充可以获得优惠，之后充值就没有优惠了，问你x元最多能拿到多少游戏币。$$\begin{array}{|c|c|c|}\hline\text{Price (RMB yuan)}& \text{Normal amount (coupons)}& \text{First recharge reward (coupons)}\ \hline 1 & 10 & 8\ \hline 6 & 60 & 18\ \hline 28 & 280 & 28\ \hline 88 & 880 & 58\ \hline 198 & 1980 & 128\ \hline 328 & 3280 & ...

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 Sciences B. Mr.Maxwell and attractions题意你可以上午工作下午玩，也可以上午玩下午工作。 玩可以获得快乐，玩的时候有两类地方，一类是室内，一类是室外，室外下午玩会降低快乐值为$80%$，重复玩一个地方会导致快乐值降低$60%$, 可叠加。 你需要至少k个早上都在工作，问你最多获得多少快乐值。 题解枚举玩多少次室内即可。用前缀和加速。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#inc ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 链接https://ac.nowcoder.com/acm/contest/15801?&headNav=www B Graph题意n个点的带权树，你可以删边，但要保证删边后图联通，可以加边，但要保证加边后所有简单环的异或和为0。 现在你可以随便操作，需要操作后的树的边权和最小。 题解题目中的两个操作都不会影响两个顶点之间路径的异或和。所以实际上相当于给了一个完全图，两个点之间的边权就是原始树上这两个点之间的路径的异或和，你要求一个最小生成树。 很多人都知道最小生成树有Kruskal算法和Prim算法，但是很少有人知道第三个算法：Boruvka算法，因为这个算法不常用。 大体来说就是首先我们有n个顶点，他们现在是n个联通块，我们使用某种算法（暴力啊贪心啊排序啊什么的瞎搞搞）得到了每个联通块到离他最近的联通块的边，然后一次性把这些边全部连起来。最终我们得到了少于$\frac{n} ...

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的最大因子即可。最终使用快速幂解决。 C Count New String题意给你一个字符串S，定义f(s,x,y)是一个字符串，长度为y-x+1，他的第k个字符串为$max_{i=x,x+1…x+k}S_i$ 你要计算$A=\lbrace f(f(s,x_1,y_1),x_2-x_1+1,y_2-x_1+1)| 1\le x_1\le 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$ 题解我们枚举i，把前i个字符串对每一个后缀都hash，然后放入map，最后枚举$s_i$的前缀，在map中寻找此前缀的hash，然后即可对$f(s_i,s_j)$实现计数，最后把增加到值添加到答案中。复杂度$O(len\cdot\log(len))$。le ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 前言这几天训练的太频繁了，一天一场比赛，简直不要太👹。从四月25号到5月3号9天开了7场。 比赛地址https://ac.nowcoder.com/acm/contest/9925 B Mine Sweeper II题意扫雷，给你一个n*m的矩阵，没有炸弹的地方会有数字，其值为周围的炸弹的个数。 给你两个矩阵，第一个为A，第二个为B，你需要对矩阵A做一些改变，修改最多一半的格子（即把炸弹变成没有炸弹或者把没有炸弹变成有炸弹），使得矩阵A修改后，没有炸弹的格子的数值之和与矩阵B相等。 数据范围$n\cdot m<10^6$ 题解考虑矩阵$B$，以及他的翻转$B_2$（炸弹变为非炸弹，非炸弹变为炸弹） 他们中没有炸弹的格子的数值之和是相等的，证明过程也很简单。 然后我们考虑,把A变为其中一个，显然如果变为$B$需要修改超过一半的格子，则变为$B_2$需要修改的格子数量少于一半。 C ...

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 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 比赛链接http://codeforces.com/gym/102822 D. Defuse the Bombs题意有一些炸弹，给你一个数组$a$，他们$a_i$秒后会爆炸，你是一个拆弹专家，你可以在炸弹爆炸前，让其爆炸时间延长一秒，问你最多能坚持多少秒 题解二分答案，直接算是错误的，只能二分。 G. Game of Cards题意有四个卡片，他们的数值分别是0，1，2，3，两个人轮流操作，操作是可以选择两张和小于等于3的卡片，将他们合并成一张新的卡片，卡片的值是和。谁不能操作谁就输了。 题解考虑3的数量为0的情况，手推sg函数有循环节， 紧接着考虑三维sg函数，上程序打表发现三维也有循环节。 J. Joy of Handcraft题意n个灯泡，每个灯泡都是周期性发光和熄灭,在时间$2kt_i+1$到时间$2kt_i+t_i$发光，在时间$2kt_i+t_i+1$到时间$2kt_i+2t_i$ ...