zcmimi's blog

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

avatar
zc
2020-07-18 11:27:00
查看原题

点击跳转

avatar
zc
2020-07-18 11:27:00
查看原题

点击跳转

avatar
zc
2020-07-18 11:27:00
查看原题

点击跳转

这题可以算是回滚莫队板子题

S为前缀和

假设区间[l,r]区间和为0,那么S_r-S_{1-1}=0

如果使用莫队算法的话,容易想到:

用桶记录某个前缀和出现的最大/最小位置,加点操作就很容易维护答案

但这样的话删点操作就有点难实现了

可以使用回滚莫队

回滚莫队是一种只添加不删除的莫队,实现如下:

首先对原序列进行分块,并对询问按照如下的方式排序:以左端点所在的块升序为第一关键字,以右端点升序为第二关键字

枚举当前要处理的块,处理所有左端点在该块内的询问,

设当前块右端为R,左指针移动到R+1,右指针移动到R.

若询问两端在同一块内,那么暴力枚举统计即可

  1. 由于左端点在同一块内,右端点单调递增

    不断右移右指针到当前询问右端点,并加点更新总答案

    (每个块右端点总位移不超过n)

  2. 不断左移左指针到当前询问左端点,并加点更新当前询问答案

    然后将左端点回滚到R+1,撤销加点操作对桶的影响

    (每次回滚左端点位移不超过\sqrt n)

继续处理下一个询问

总复杂度O(n\sqrt n),实测跑的飞快

请配合代码理解,注意细节

avatar
zc
2020-07-18 11:27:00
查看原题

点击跳转

avatar
zc
2020-07-09 21:41:00
查看原题

点击跳转

拆分为m项时,生成函数为F^m (x)

那么答案的生成函数为\displaystyle G(x)=\sum_{i=0}^{\infin} F^i(x)

F为斐波那契数列生成函数,\displaystyle F(x)=\frac x{1-x-x^2}

\begin{aligned} G(x) &=\sum_{i=0}^{\infty} F^i(x)\\ &=\frac 1{1-F(x)}\\ &=\frac {1-x-x^2}{1-2x-x^2}\\ &=1+\frac x{1-2x-x^2}\\ &=1+\frac x{[1-(1+\sqrt 2)x][1-(1-\sqrt2)x]}\\ &=1+\frac 1{2\sqrt 2}\left( \frac 1{1-(1+\sqrt 2)x} - \frac 1{1-(1-\sqrt 2)x} \right)\\ &=1+\sum_{i=1}^{\infin} \frac{(1+\sqrt 2)^i-(1-\sqrt 2)^i}{2\sqrt 2} x^i \end{aligned}

那么:

\displaystyle ans_n=\frac{(1+\sqrt 2)^n-(1-\sqrt 2)^n}{2\sqrt 2}

其中\sqrt 2 \equiv 59713600 \pmod{10^9+7}(二次剩余)

这样的话:

\displaystyle \begin{aligned} ans_n &=\frac {\sqrt 2}4\left[(1+\sqrt 2)^n-(1-\sqrt 2)^n\right]\\ &\equiv 59713600\times 250000002\times [(1+59713600)^n-(1-59713600)^n] \pmod{10^9+7} \end{aligned}

使用快速幂复杂度O(\log n)

考虑费马小定理: ans_n \equiv ans_{n \mod 10^9+6}

这样就可以把n压到10^9+6以内了,再快速幂即可

avatar
zc
2020-07-07 17:25:00
查看原题

点击跳转

首先了解原根

这里利用到原根的一个性质:

gm的一个原根
g^0,g^1,g^2,\dots,g^{\varphi(m)-1}构成模m的简化剩余系

这样我们可以把序列中所有数变成原根的次幂,

那么序列中所有数的乘积就可以转化为他们的和

设这个和为sum

设生成函数:\displaystyle f(x)=\sum_{i=0}^m [i\in S]x^i

可以发现f(x)^n次数为sum的那一项的系数就是答案

使用快速幂+快速数论变换

avatar
zc
2020-07-05 13:10:00
查看原题

点击跳转

首先找位置对称的回文子序列个数(多项式求)

由于不能连续,所以减去对称回文子串个数(manacher求)

设字符串为S,|S|=n

假设S_i作为一个子序列的对称中心,x=\sum_{j=1\le j\le i-1}[S_{i-j}=S_{i+j}]

那么以i为中心位置的方案数为2^{x+1}-1

A_i=[S_i=a],B_i=[S_i=b]

那么\displaystyle (A*A)_i=A_i*A_i=\sum_{j=0}^nA_jA_{i-j}就是对称中心为位置\frac i2的两端为a的数量

同理(B*B)_i就是对称中心为位置\frac i2的两端为b的数量

那么上述(A*A)_i+(B*B)_i就是对称中心为位置\frac i2x+1

如果i为偶数,x+1要减去1(对称中心是否在同个字符上)

avatar
zc
2020-07-05 13:10:00
查看原题

点击跳转

此题要求的是S(n,m) \mod 2(第二类斯特林数)

  1. m为偶数,S(n,m) \equiv S(n-1,m-1)

  2. m为奇数,S(n,m) \equiv S(n-1,m-1)+s(n-1,m)

这样的话,相当于:

  1. (x,y)y为奇数时,可以走到(x+1,y+1)(a变换)

  2. 否则可以走到(x+1,y+1)(a变换),或(x+1,y)(b变换)

求从(0,0)走到(n,m)的方案数\pmod 2

这个过程必然走了ma变换,走了n-mb变换

b变换只能在偶数位置出现,那么变换的序列必然是如下形式:

a,b\times ?,a,a,b\times ?,a,a,...,a

也就是在\frac {m+1}2个间隔中插入n-mb,即隔板法

方案数:C(n-m+\frac{m+1}2-1,\frac{m+1}2 -1) \mod 2

还有一个结论:仅当n\&m=m时,C(n,m) \equiv 1 \bmod 2(lucas定理代入即可推出)

avatar
zc
2020-06-15 21:47:00
查看原题

点击跳转

首先奇偶黑白染色,源点连黑点,白点连汇点,边权为点权

接着所有黑点向相邻的白点连边,边权为\infty

答案就是 点权和-最小割

avatar
zc
2020-06-14 13:07:00
查看原题

点击跳转

可以看出这是多颗基环树

分三种情况:

  1. x,y在不同的两颗树上

  2. x,y还没到达环就相遇了

  3. x,y的祖先在环上不同位置

8/66
Search
search