牛客竞赛ID突然就变红了，好想给CF也上个红啊。。。

n = 5，样例输出是 5e8+6 即 5/2 但是自己手玩可以发现答案等于 37 / 15： 步骤如下（如果错了当我没说） Case 1 第一步 : 10000 (1/5) 第二步 : 10100 10010 10001 (1/3) 第二步过后 10010 动不了，而 10100 和 10001 必会变成 10101 对答案贡献为  第一步为 00001 同理 Case 2 第一步 : 01000 (1/5) 第二步 : 01010 01001 (1/2) 对答案贡献为  第一步为 00010 同理 Case 3 第一步 : 00100 最后必会变成 10101 对答案贡献为  所以算出来答...

卷积  题目描述 给定序列 的递推公式 。 令 为序列 的生成函数，求 的第 项对 取模。 正解 最终答案 是一个等比数列求和的形式，等价于 。 现在直接多项式求逆就可以做到 了，感觉卡卡就能过。 比赛的时候不会生成函数真的自闭了啊，然后想起了 rqy 博客里求通项 / 递推公式的方法，尝试自己推了一下。 先对 求出其封闭形式，然后如果 也能表示成一个类似于生成函数封闭形式的玩意，就能求出 的递推式。 先对 求其封闭形式。 然后求 。 发现 与 的封闭形式类似，应该可以求出其递推公式。 那么很显然数列 的递推公式是 ，特别的：有 。 直接递推可以做到 ，或者用矩阵优化到 。 代码 #inclu...

宝石装箱  题目描述 有 个带标号盒子和球，每个球都有一个盒子 不能放进去（ 不一定是排列）。 问每一个盒子里都有一个球的方案数。 正解 每一个球都有一个限制（一个盒子不能放）。 这个问题类似于错排，而错排有一种容斥的解法。 设 表示至少有 条限制不满足的方案数, 表示恰好有 条限制不满足的方案数。（一种方案必须放满所有盒子） 先钦定 个盒子一定不合法，然后其他盒子随便摆，这就是至少 个盒子不合法的方案数 。 那么有 ：  特别的，。  现在问题变成了如何求 。 可能有多个 相同，但是只能有一个球放进这个 这个盒子，设 为有多少个球不能放进第 个盒子里。 对于每一个 分开考虑，于是每一个 可以...

小V和字符串  题目描述 直接点开题目看描述吧。 正解 数位 dp。 设 表示考虑前 位，两串 的差值为 的方案数（后面两个 表示两个串分别是否顶上界）。 再设一个辅助数组 表示考虑前 位，两串 的差值为 ，的所有方案下，需要移动的步数（后面两个 与上面定义相同）。 发现如果当前两个串 的个数相差为 （ 可能为负），到下一位就会要产生 的贡献（移动 步）。 转移好像挺复杂的，我是自己画了个转移的图然后才写出来的。 note 由于题目中 串字典序要严格小于 串字典序，答案算出来还要除个 。 代码 这代码真不是给人看的 #include <bits/stdc++.h> using na...

小V和gcd树  题目描述 给定一棵树，树带点权，树的边权等于边两端点权的 。 有两种操作 ：  更改一个点的点权，同时与之相连的边权也跟着改变。 询问两个点的链上边权小于等于 的个数。  正解 先将一下复杂度吧 ，挺暴力的。 考虑根号分治。 修改 ： 对于一个度数大于 的点，修改时只修改点权，忽视其边权的贡献（查询时再暴力求 计算贡献） 。 对于一个度数小于 的点，暴力修改其连出去的边权。 修改时复杂度瓶颈在度数小于 的点，时间复杂度为 。 查询 : 查询的时候暴力跳 统计答案，然后对于度数大于 的点，还要求 。 但是度数大于 的点不会超过 个，查询总复杂度为 。 代码 #include &...

小V和方程  题目描述 给定 , 。 求 的本质不同解（可重集合）的个数。 正解 考虑把 表示成 的形式，其中 再也不能再进行拆分（没有平方因子）了。 那么 一定要是 的倍数。 现在题目就是一个划分数问题了（把 个相同的球放在 个相同的盒子内）， 递推即可。 代码 #include <bits/stdc++.h> using namespace std; const int mod = 998244353; const int N = 1005; int n, m, x, y; int f[N][N]; int main() { scanf("%d %d", &n, &am...

https://blog.nowcoder.net/n/6650ed32a8d64f649dd0b370eb22edaahttps://blog.nowcoder.net/n/149aefbd71f74545ab73c71f3f8454fc抄了我的博客还不点赞，差评😣

牛牛的树行棋  题目描述 给定一棵树，树上每一个节点都有一枚棋子。 Alice 和 Bob 在这棵树上玩一个这样子的游戏 ： Alice 和 Bob 轮流操作，每次把一枚棋子移动到其子树内的节点（显然一枚棋子在叶子节点就不能移动了），不能移动的人算输。 问 Alice 先手是否有必胜策略，若先手必胜，则求出第一步移动棋子的方案有多少种。 正解 这里先介绍一下 SG 函数（其实只需要知道结论就行）。 一个状态的 SG 函数值（后面简称 SG 值）是其所有后继状态（进行一次操作后所到达的状态） ---手动换行--- SG值 集合的 （最小不属于这个集合的非负整数，比如说 ）。 形式化的来说 。 结...

小L扔垃圾  题目描述 给定一个序列，每次在其左端点或者右端点加入一个元素。 求这个序列的最长子段满足这个子段的 'W' 元素的个数等于 'D' 元素的个数。 正解 把 'W' 看成 1，把 'D' 看成 -1，若一个子段满足条件，则这个子段的和为 0。 记录前缀和，然后 要满足条件的话，。 离线预处理出前缀和数组，用哈希表维护一个前缀和的出现位置就行。 时间复杂度 。 （貌似在线也能做 代码 #include <bits/stdc++.h> #define N 2000005 using namespace std; int n; int arr[N + N], ltax[N +...

最小鸽  题目描述 给定一个序列，每次询问包含一个位置的最小区间，满足这个区间元素的或（or）大于这个区间元素的最大值。 正解 在线肯定不太可行，想离线做法。 对于每一个数作为区间的最大值（不一定唯一），求它对这个区间产生的影响。 然后这个位置作为最大值的区间要合法的话，需要包含一个数二进制位与它不同。 其实就对每个位置，预处理出两个左端点，两个右端点。（作为最大值的左右端点，和遇到第一个数二进制位与它不同的左右端点） 然后合法不合法就和容易判断了，更新答案用线段树简单维护即可。 可能之后会补充判断是否合法，以及线段树更新区间的细节吧。 时间复杂度 。 补充  upd : 如何统计答案  先规...

牛牛的繁星  题目描述 给定一个长度为 的序列，有 次询问。 每次询问一个区间内，"元素出现次数" 的第 大的 "出现次数"。 强制在线。 正解 如果可以离线，有一个经典的莫队 + 值域分块做法可以做到严格 。（而且常数很小 就直接暴力移动左右端点，移动端点的修改复杂度是 的，然后单次查询是 的。 考虑在线怎么用莫队做。 预处理一些 的桶和分块数组，然后查寻就从最近的 开始移动，查寻完后还原桶和分块数组。 其实可以预处理很多 的，但由于空间原因，最多就只能预处理 个。 然后一次询问就需要移动大约 3000 次，总的复杂度有 ，实现精细一点应该可以通过。 代码 #pragma GCC optim...

牛牛的呱数  题目描述 给出 个数和一个模数 。 问选若干个数（可以重复选择）拼在一起，并且整除 时，最短的长度。 正解 显然这 个数有用的信息只有长度 和模 意义下的值 ，那就先预处理这些东西。 考虑每次把新加进来的数放在已有的数的左边。 加入后的值是原来的值 加上新增的值 。 设 表示当前的数模 意义下的值为 ，下一个数加进来，还要乘上 的最短串。  在模 意义下至多只有 个不同的取值，那么状态其实只有 种。 暴力枚举每一种转移就行了，本质上就是跑一遍最短路，用 Dijkstra 实现。 时间复杂度 。 代码 #include <bits/stdc++.h> #define N...