2024.12 BJ集训 (补发)

AC_Lover · 2025-02-28 16:44:14 · 个人记录

小 N 位于数轴的 x=0 处。规定数轴右端为正方向。 每个时刻，小 N 会选择随机选择向左或向右走一步。形式化地，设小 N 目前在p，小 N 会随机走 到x=p-1或x=p+1。其中，向左走的概率为\frac{a}{a+b} ，向右走的概率为\frac{b}{a+b} 。 已知小 N 走了m步，求小 N 到达过 x=n 的概率。 答案对 998244353取模。1\le n,m\le 10^7

解法：

考虑转化为走网格的问题先求出方案数，若在第m步第一次走到了n，y轴表示向右走，x轴表示向左走，那么对应图： 此时相当于从(0,0)走到红线和绿线的交点，并且在途中一直不高于蓝线，假设交点为(x,y)，可以分析发现最后一步一定是向右走，因此相当于从(0,0)出发，走到(x,y-1)，且路径中一直不高于蓝线的方案数，此时发现这可以通过类似卡塔兰数的求解方法，将所有不合法的线从第一个碰到绿线的地方关于绿线做轴对称，于是可以将所有不合法的路线转化为从(0,0)走到(x-1,y)的方案数，因此不合法的方案就是C(x+y-1,y)，总方案数为C(x+y-1,y-1)，所以合法的路径数为C(x+y-1,y-1)-C(x+y-1,y)

因此我们可以枚举走了多少步，假设走了i步，那么可以计算出向右走了\frac{n+i}{2}步，向左走了\frac{i-n}{2}步，将x=\frac{i-n}{2},y=\frac{n+i}{2}代入C(x+y-1,y-1)-C(x+y-1,y)即可计算出走i步第一次走n的方案数，乘上走x步向左y步向右的概率即可，即

求和即可得答案：

预处理幂和组合数，计算即可。

给定一个长度为n的正整数序列a，1\le a_i\le n

定义g(l,r):对于1\le i\le n，若l\le a_i\le r，则令b_i=1，否则令b_{i}=0，g(l,r)为b中1的连续段个数

要支持对a进行q次更改，每次令a_x=k，要求在每次修改后输出

解法：

考虑转移点代表b_{i-1}=0\wedge b_i=1，推柿子

对于每次更改，维护变化即可，时间复杂度:O(n+q)

(CF1658E)

现在有一个大小为n\times n的棋盘，其中不重不漏地填有1至n^2的所有整数。M 和 G 会玩以下游戏：M 先将一枚棋子放在某个初始格子中，随后从 G 开始双方会轮流移动棋子，每次将棋子移动到与当前格子曼哈顿距离大于k的格子中并获得该格子中数字的分数（一个格子可以被访问多次）。经过10^{100}轮后分数较多者获胜。对于每种 M 放初始格子的方案，求谁会获胜。

解法：

每个人选择的格子的数一定比上一个人选择的格子的数要大

反证：假设上一个人选择的数为V_1，则如果当前选择的数V_2<V_1，那上一个人一定可以不动，下一轮还选V_1，那选V_2一定不优

定义f_{x,y}表示当前选择了格子(x,y)是否能取胜。

所以可以将网格按其数从大到小排序，假设当前到第i个格子，其格子为(x_1,y_1)，则1到i-1的格子就是下一步可以选择的格子，如果1到i-1的格子中有(x_2,y_2)满足|x_1-x_2|+|y_1-y_2|>k并且f_{x_2,y_2}=1，说明另一方有方法使得他必胜，那当前的这方必败，f_{x_1,y_1}=0

可以将曼哈顿距离转化为切比雪夫距离，记录使得f_{x,y}=1的x+y和x-y的最大最小值，然后判断距离，转移即可。

(F)

给定整数n,p,r，求出一组正整数k,v，满足2\le k\le n,1\le v < k，且将1\times 2\times ... \times n中的数k替换成v，得到的结果模p余r

解法：

分类讨论：

当n\ge 2p时，n!中有p\bmod p=0和2p\bmod p=0

① r=0 随便修改一个都能满足条件

② r\ne 0 无论修改什么都有n!\bmod p=0，此时无解

当p<n<2p时，n!中有p\bmod p=0，

① r=0，修改一个k\ne p一定能满足

② r\ne 0 只能将p修改掉，此时有k=p，枚举v即可

当n=p时，

① r=0，如果n=p=2那么可以发现是无解的，否则随便修改一个k\ne p即可满足

② r\ne 0 与p<n<2p同理

当n<p时，

枚举修改的点k，考虑将k替换成什么才能满足条件，记x=n!，可以发现将k替换成v相当于将x除以k再乘上v，于是可以列出方程：

同乘k，

同时乘上x的逆元x^{-1}，发现由于p为质数所以x的逆元即为x^{p-2}

由于n<p，所以要v尽量小，取v=rkx^{p-2}\bmod p，此时判断如果1\le v<k说明满足条件，找到了解。

最后如果枚举完2\le k\le n都无解，那么无解。

(DNA Sequence)

给定n个模式串，求长度为m且不包含这些模式串的字符串的个数(字符集大小为4) 答案对100000取模

解法：

考虑AC自动机上DP，首先建立出AC自动机，并定义wrong_u表示到达u是否会经过模式串，有wrong_u=wrong_{ne_u}，若u本身是一个模式串的结尾，有wrong_u=1。

随后考虑朴素的DP，定义f_{i,u}表示构造出长度为i的字符串，且当前在AC自动机上的点u的方案数，其转移类似于\mathrm{KMP}的\mathrm{trans}函数。

有转移：f_{i,v}+=f_{i-1,u}(v为u的子节点并且wrong_u=0,wrong_v=0)

朴素DP时间复杂度不可行，考虑用矩阵加速，先建出矩阵A，若u可以转移到v，那么令A_{u,v}=1，最后用矩阵快速幂计算出A^m，答案就是从根节点开始的方案数，即\sum_{i}A_{0,i}

([NOI2017] 游戏)

先考虑d=0的情况，此时所有的车都只有两种情况，可以使用2-SAT求解，具体而言，将每个位置分为两个状态，分情况建出边：

然后用2-SAT求解

如果d\ne 0，发现有d\le 8，直接暴力枚举对于每个x，将其替换成a,b是否有解，此时没必要枚举c，因为此种情况已经在替换成a,b时计算过，枚举后用d=0的方式求解即可。