zcmimi's blog

categories/刷题记录/共653篇文章

avatar
zc
2020-05-03 01:04:00
查看原题

点击跳转

暴力枚举即可

avatar
zc
2020-05-02 23:47:00
查看原题

点击跳转

可以发现110\leftrightarrow 011相当于0前/后移动了2格,那么每个0位置的奇偶性是不变的

而且每个0无法移动到下一个0的后面

把这些0记录到一个序列里,然后通过哈希判断两个子串在序列中对应的部分是否相同

因为子序列的起点奇偶性不同,分别表示以起点为奇数和偶数为标准时哈希得的前缀0序列数组。

avatar
zc
2020-05-02 11:52:00
查看原题

点击跳转

ans={n\choose w_1}\cdot {n-w_1\choose w_2}\cdot {n-w_1-w_2\choose w_3}\cdots {n-w_1-w_2-\dots -w_{m-1}\choose w_m}

套扩展卢卡斯即可

avatar
zc
2020-05-02 11:42:00
查看原题

点击跳转

p=p_1^{k_1}p_2^{k_2}\dots p_n^{k_n}

求出每个{n\choose m} \equiv a_i \pmod {p_i^{k_i}}

得到同余方程组

\begin{cases} {n\choose m} \equiv a_1 \pmod {p_1^{k_1}} \\ {n\choose m} \equiv a_2 \pmod {p_2^{k_2}} \\ \vdots \\ {n\choose m} \equiv a_n \pmod {p_n^{k_n}} \end{cases}

使用crt即可求出n\choose m的值

p^t不是质数,那么如何求{n\choose m} \mod p^t呢?

可以计算{n\choose m}=\frac{n!}{m!(n-m)!},分别计算出n!,m!,(n-m)!在模p^t意义下的值

假设p=3,t=2,n=19,

n!=1\cdot 2\cdot 3\cdots 19 \\ =(1\cdot 2\cdot 4\cdot 5\cdot 7\cdot 8\cdot 10\cdot 11\cdot 13\cdot 14\cdot 16\cdot 17\cdot 19)\cdot (3\cdot 6\cdot 9\cdot 12\cdot 15\cdot 18) \\ =(1\cdot 2\cdot 4\cdot 5\cdot 7\cdot 8\cdot 10\cdot 11\cdot 13\cdot 14\cdot 16\cdot 17\cdot 19)\cdot 3^6\cdot(1\cdot2\cdot3\cdot4\cdot5\cdot6)

可以发现后面的部分相当于\left\lfloor \frac np \right\rfloor!,递归计算即可

前半部分以p^t为周期,即

1\cdot 2\cdot 4\cdot 5\cdot 7\cdot 8 \equiv 10\cdot 11\cdot 13\cdot 14\cdot 16\cdot 17 \pmod {3^2}

只需要计算不满足周期的数19就可以了

avatar
zc
2020-04-28 17:21:00
查看原题

点击跳转

可以发现答案是递减的

每个q_i相当于破坏掉[1,q_i]的最大值

那么我们把[1,q_i]区间-1

将最大值变为p_k的时候,相当于[1,k]的最大值都变成了p_k

那么把[1,k]区间+1

每次询问的时候,一直将当前最大值-1,应用变化,直到区间最大值大于0,输出答案

具体看代码

avatar
zc
2020-04-28 00:27:00
查看原题

点击跳转

首先把连接所有i\rightarrow p_i,可以得到若干个环

kp_i=p_{p_i}后会让i指向环上从i数起的k+1个点

只需要让一个环满足条件既可以,我们可以对每个环分别处理,然后答案取\min

可以发现假设一个环长度为l,若k可行,那么\gcd(k,l)也是可行的

我们判断是否存在0\le t < \gcd(k,l),使环上所有模\gcd(k,l)等于t的点的颜色都相同就可以了

avatar
zc
2020-04-27 17:49:00
查看原题

点击跳转

可以发现,这条链必然经过每个给定点的父亲

把每个给定点都变成它的父亲

按深度排序

依次判断接下来的节点是否在上一个的子树中即可

avatar
zc
2020-04-27 12:37:00
查看原题

点击跳转

很妙的构造题

首先,可以发现异或和明显不大于总和

第二,如果异或和与总和的奇偶不同,那么无解(二进制下最低位不同,没法用进位来填充)

剩下的就都可以构造了

u=v的时候,输出u就可以了,当u=0的时候记得特判

x=\frac{u+v}2

那么\left\{x,x,u\right\}就一定可以满足

如果x \And u=0的时候\left\{x,u\right\}等价于\left\{x+u\right\}

那么\left\{x,x+u\right\}可以满足

avatar
zc
2020-04-26 21:16:00
查看原题

点击跳转

首先我们可以只保留每个数奇数次幂的因子

第二,根据约数个数定理,因为每个数的约数不超过7,所以最多只有两个质因子

可以把选择一个数看成在这两个质因子之间的连边

如果只有一个,那么把1作为另一个质因子

于是我们得到一张图

乘积为完全平方,也就是每个质因子都是偶数次幂,那么再最终的图中它的入度为偶数

那就是说我们要找这个无向图中的最小环

avatar
zc
2020-04-26 16:20:00
查看原题

点击跳转

f_{i,j}表示前i个点,第i个点的覆盖状态为j(j8位二进制数)

12/66
Search
search