zcmimi's blog

arrow_backlucas共5篇文章

avatar
zc
2020-10-19 16:24:55

查看原题

点击跳转

n个位置中选出m个位置后剩余n-m个位置错排

{n\choose m}\cdot D_{n-m}

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-03-11 20:34:00
查看原题

点击跳转

\sum_{i=0}^k {n \choose i} \bmod 2333

p=2333 \sum_{i=0}^k {n \choose i} \bmod p \\ =\sum_{i=0}^k {\left \lfloor \frac np \right \rfloor \choose \left \lfloor \frac ip \right \rfloor} {n \bmod p \choose i\bmod p}\bmod p \\ ={\left \lfloor \frac np \right \rfloor \choose 0}\sum_{i=0}^{p-1}{n \bmod p \choose i}+{\left \lfloor \frac np \right \rfloor \choose 1}\sum_{i=0}^{p-1}{n \bmod p \choose i}+ \cdots+ {\left \lfloor \frac np \right \rfloor \choose \left \lfloor \frac kp \right \rfloor}\sum_{i=0}^{k \bmod p}{n \bmod p \choose i}

f(n,k)=\sum_{i=0}^k {n \choose i}

原式可以转化为:

f(n \bmod p,p-1) \cdot f(\left \lfloor \frac np \right \rfloor,\left \lfloor \frac kp \right \rfloor -1)+{\left \lfloor \frac np \right \rfloor \choose \left \lfloor \frac kp \right \rfloor} f(n\bmod p,k\bmod p)

avatar
zc
2020-03-11 00:41:00
查看原题

点击跳转

给出n,m{n+m} \choose m

avatar
zc
2020-03-10 22:33:00
查看原题

点击跳转

题意:

G^{\sum d|{N\choose d}}\bmod 999911659

1 \le G \le 10^9,1 \le N \le 10^9

999911659是质数,根据欧拉定理:

G^{\sum d|{N\choose d}}\bmod 999911659 = G^{\sum d|{N\choose d} \bmod 999911658}\bmod 999911659

关键求\sum d|{N\choose d} \bmod 999911658

模数太大,直接lucas取模会炸

我们可以考虑将模数分解质因数

999911658=2\times 3 \times 4679 \times 35617

可以用lucas枚举约数算出

\begin{cases} a_1=\sum d|{N\choose d} \pmod 2 \\ a_2=\sum d|{N\choose d} \pmod 3 \\ a_3=\sum d|{N\choose d} \pmod {4679} \\ a_4=\sum d|{N\choose d} \pmod {35617} \end{cases}

然后通过crt求:

\begin{cases} x \equiv a_1 \pmod 2 \\ x \equiv a_2 \pmod 3 \\ x \equiv a_3 \pmod {4679} \\ x \equiv a_4 \pmod {35617} \end{cases}

1/1
Search
search