zcmimi's blog

arrow_back数论共124篇文章

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-11 16:49:00
查看原题

点击跳转

f_i表示所有数\gcdi还要加入的数的期望数量

ans=1+\frac{\sum_{i=1}^mf_i}m

可以知道f_1=0

f_i=1+\frac{\sum_{j=1}^m f_{\gcd(i,j)}}m(i>1)

继续推式子:

\begin{aligned} f_i &=1+\frac{\sum_{j=1}^m f_{\gcd(i,j)}}m\\ &=1+\frac{\sum_{d|i} f_d\sum_{j=1}^m [\gcd(i,j)=d]}m \end{aligned}

把分子拿出来

\begin{aligned} &\quad\sum_{d|i} f_d\sum_{j=1}^m [\gcd(i,j)=d]\\ &=\sum_{d|i} f_d\sum_{j=1}^{m/d} [\gcd(\frac id,j)=1]\\ &=\sum_{d|i} f_d\sum_{j=1}^{m/d} \sum_{x|\frac id,x|j}\mu(x)\\ &=\sum_{d|i} f_d \sum_{x|\frac id}\sum_{j=1}^{m/dx}\mu(x)\\ &=\sum_{d|i} f_d \sum_{x|\frac id}\mu(x)\left \lfloor \frac m{dx}\right\rfloor\\ \end{aligned}\\

T=dx

=\sum_{T|i}\sum_{d|T} f_d \mu(\frac Td)\left \lfloor \frac mT\right\rfloor

带入原来的式子

f_i=1+\frac{\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)}m

F_T=\sum_{d|T} f_d \mu(\frac Td)

d\not = i时可以每算出一个f_i就更新所有F_x(i|x)

d=i时没法直接更新,这时T=d=i,\mu(\frac Td)=\mu(1)=1

f_i=1+\frac{\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m+\frac{f_i\left\lfloor \frac mi \right\rfloor}m \\ f_i-\frac{f_i\left\lfloor \frac mi \right\rfloor}m=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m \\ f_i\frac{m-\left\lfloor\frac mi \right\rfloor}m=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m \\ f_i=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}{m-\left\lfloor\frac mi \right\rfloor}

这样就可以先算f_i,再算F_i

[d\not=i]这个条件只在T=i的时候才有限制

枚举到T=i,计算f_i时,F_x(x<i)都已经计算好了

F_i还少了f[i] \times \mu(1)

这正好是要剪掉的部分

avatar
zc
2020-06-09 16:10:00
查看原题

点击跳转

a_i=\sum\limits_{j=1}^N[A_j=i],n=10^6

\sum_{i=1}^n\sum_{j=i+1}^n \operatorname{lcm}(A_i,A_j)\\ =\sum_{i=1}^n\sum_{j=i+1}^n a_ia_j\frac{ij}{\gcd(i,j)}\\ =\sum_{d=1}^n\frac 1d\sum_{i=1}^n\sum_{j=i+1}^n a_ia_j ij [\gcd(i,j)=d]\\ =\sum_{d=1}^n\frac 1d\sum_{i=1}^{n/d}\sum_{j=i+1}^{n/d} a_{id}a_{jd} idjd [\gcd(i,j)=1]\\ =\sum_{d=1}^n d \sum_{i=1}^{n/d}\sum_{j=i+1}^{n/d} a_{id}a_{jd} ij [\gcd(i,j)=1]\\ =\sum_{d=1}^n d \sum_{i=1}^{n/d}\sum_{j=i+1}^{n/d} a_{id}a_{jd} ij \sum_{x|i,x|j}\mu(x)\\ =\sum_{d=1}^n d \sum_{x=1}^n\mu(x)\sum_{i=1}^{n/dx}\sum_{j=i+1}^{n/dx} a_{idx}a_{jdx} ixjx\\ =\sum_{d=1}^n d \sum_{x=1}^n\mu(x)x^2 \sum_{i=1}^{n/dx}\sum_{j=i+1}^{n/dx} a_{idx}a_{jdx} ij\\ T=dx =\sum_{T=1}^n T \sum_{x|T}\mu(x)x \sum_{i=1}^{n/T}\sum_{j=i+1}^{n/T} a_{iT}a_{jT} ij

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-26 21:16:00
查看原题

点击跳转

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

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

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

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

于是我们得到一张图

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

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

6/13
Search
search