zcmimi's blog
avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

设通配符的数值为0,定义匹配函数C(x,y)=[A(x)-B(y)]^2A(x)B(y),那么\displaystyle P(x)=\sum_{i=0}^{m-1}[A(i)-B(x-m+i+1)]^2A(i)B(x-m+i+1)

按照套路,翻转A串得到S串:

\displaystyle \begin{aligned} P(x) &=\sum_{i=0}^{m-1}[A(i)-B(x-m+i+1)]^2A(i)B(x-m+i+1)\\ &=\sum_{i=0}^{m-1}[S(m-i+1)-B(x-m+i+1)]^2S(m-i+1)B(x-m+i+1)\\ &=\sum_{i=0}^{m-1}S(m-i+1)^3B(x-m+i+1)+\\ &\quad\sum_{i=0}^{m-1}B(x-m+i+1)^3S(m-i+1)-\\ &\quad2\sum_{i=0}^{m-1}S(m-i+1)^2B(x-m+i+1)^2 \end{aligned}

写为卷积形式:

\displaystyle P(x)=\sum_{i+j=x}S(i)^3B(j)+S(i)B(j)^3-2S(i)^2B(j)^2

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

点击跳转

f(n)=\sum_{i=0}^n \sum_{j=0}^i \begin{Bmatrix}i\\j\end{Bmatrix} 2^j j!

考虑到i<j\begin{Bmatrix}i\\j\end{Bmatrix}=0 :

f(n)=\sum_{j=0}^n 2^j j! \sum_{i=0}^n \begin{Bmatrix}i\\j\end{Bmatrix}\\ =\sum_{j=0}^n 2^j j! \sum_{i=0}^n \sum_{k=0}^j \frac{(-1)^k}{k!} \frac{(j-k)^i}{(j-k)!}\\ =\sum_{j=0}^n 2^j j! \sum_{k=0}^j \frac{(-1)^k}{k!} \frac{\sum_{i=0}^n (j-k)^i}{(j-k)!}

\displaystyle g(k)=\frac{(-1)^k}{k!}, h(k)=\frac{\sum_{i=0}^n k^i}{k!}=\frac{k^{n+1}-1}{(k-1)k!} ,

特别的: h(0)=1,h(1)=n+1

那么

f(n)=\sum_{j=0}^n 2^j j! (g\times h)(j)

卷积后即可计算

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

点击跳转

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

点击跳转

sa的前缀和,Ss的前缀和

\begin{aligned} ans &=\sum_{i=l}^r \sum_{j=i}^n s_j-s_{j-i}\\ &=\sum_{i=l}^r\left(\sum_{j=i}^n s_j-\sum_{j=i}^ns_{j-i}\right)\\ &=\sum_{i=l}^r\left(\sum_{j=1}^n s_j - \sum_{j=1}^{i-1} s_j -\sum_{j=0}^{n-i}s_j\right)\\ &=\sum_{i=l}^r ( S_n-S_{i-1}-S_{n-i})\\ \end{aligned}

线段树维护S即可,如何维护S?

假设[l,r]区间加v,

g_i=1+2+3+\dots+i=\frac{i(i+1)}2

假设i\in[l,r],那么S_i加上v\times g_{r-i+1}

假设i\in[r+1,n],那么S_i加上v\times g_{r-l+1} + v\times(i-r)(r-l+1)

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的那一项的系数就是答案

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

15/73
Search
search