p3744. 打扑克
直接递推了。
p3745. combination
使用卢卡斯定理切掉。
long long c(long long n,long long m)
{
return f[n]*g[m]*g[n-m]%mod;
}
long long lcs(long long n,long long m)
{
if(m==0)
return 1;
return lcs(n/mod,m/mod)*c(n%mod,m%mod)%mod;
}
3342. 【模板】卢卡斯定理/Lucas 定理
同上，只用改取模和输入。
P118. 「一本通 6.1 练习 3」越狱
结论：一共有 \(m^n\) 种可能，不可以越狱的可能，一共有 \(m*(m-1)^{n-1}\) 种。所以答案是二者相减。
原本需要扩展欧拉定理去算幂取模，但是对于这道题，快速幂解决即可。
p3749. Rooks LightOJ - 1005
对于 \(n\) 列，有 \(k\) 个需要摆放；对于 \(n\) 行，也需要摆放 \(k\) 个.
所以最终答案数是
\[\large C_{n}^{k}*A_{n}^{k} \]要开 \(\text{long long}\) 。
P2280. 牡牛和牝牛
据说有 DP 做法，但是我不会。。
所以我选择组合数学推结论（洛谷上说不用卢卡斯定理，但是我还是用了）
结论:
\[ans=\sum_{i=0}^{n}\large C_{n-(i-1)\times k}^{ i} \]对于 \(C\) ，卢卡斯秒了。但是好像不用。。。
3328. [ABC156E] Roaming
有点小难。。。
考虑 \(k\) 次移动后的空房子的最大值，显然是 \(k\) ，但是 \(k\) 有可能大于 \(n\)，所以是\(\min(k,n-1)\) 个，对于每个 \(i \in [0,\min(k,n-1) \ ]\)，答案个数是 \(\large C_{n}^{ \ i}\)（感性理解一下）
考虑 \(k\) 次移动后有人的房子，即是对于每个\(i \in [0,\min(k,n-1) \ ],n-1\) 个人会插在 \(n-i-1\) 个地方,答案个数是 \(\large C_{ \ n-1}^{ \ n-i-1}\) ，注意这里是 \(n-1\) 而不是 \(n-i\) 。。。
最终结果即是
\[\sum_{i=0}^{\min(n-1,k)} \large {(C_{n}^{i}\times C_{n-1}^{n-i-1}) }\text{ mod } p \]p3751. X-factor Chain
结论题。
——msb大佬
输出的长度就是 \(n\) 的质因数个数（有重复）。
而第二个序列的个数就有一点难搞了：
从容斥的角度去想，这 \(k\) 个质因数想要排满，第一位有 \(1\) 种，第二位有 \(2\) 种，第 \(n\) 位就有 \(n\) 种，总共有 $k! $ 种。
那么考虑以下情况：如果最后一位是 \(k_i\) ，那么前面的每一位都要有这个 \(k_i\) ，那么对于每一个 \(k_i\) ，就有 \(k_i!\) 种不合法的结果。（\(k_i\) 代表第 \(k\) 个质因数出现的个数）
即最终答案是：
\[\frac{k!}{\prod_{1}^{k}k_i!} \]中间的细节，我没有记录每一个阶乘，都是现算的，但是能过。
P526. [HNOI2012]排队
纸张高精，抄的结论。
P2022. [Sdoi2016]排列计数
和上面的难度一样，都是绿题，但是这道题我一节课就推出来了。
首先，考虑先排在原位的数，即 \(a[i]=i\) 的那 \(m\) 个，显然，有 \(\large C_{ \ n}^{ \ m}\) 种。
接下来，考虑排剩下的不在原位的 \(n-m\) 个数，这里要求在剩下的位置里， $ a[i]!=i$ ，可以考虑错排法，结论：
\[D(i)= \begin{cases} 0&,i=1 \\ 1&,i=2 \\ (i-1)\times (D(i-1)+D(i-2))&,otherwise \end{cases} \]证明可参考课件。
我们在处理 \(D(i)\) 的时候，需要用数组记忆化，处理 \(C\) 的时候，要用费马小定理求逆元。
最终答案即为：
\[C_{n}^{m}\times D(n-m) \mod (1e9+7) \]P515. [ZJOI2010]Perm 排列计数
很有意思。题目的叙述转换成图论模型就是：求大小为 \(n\) 的小根堆有多少个。
需要树上 \(dfs\) ，用 \(lucas\) 算答案。
P2281. BZOJ 4403序列统计
依然是组合数。但是 \(lucas\) 的时候要有边界。。
3327. [ABC172E] NEQ
排列+错排。
考虑序列 \(A\) 的个数，显然是 \(A_{m}^{n}\) 种。
那么题目上说要求 \(\forall A_i \neq B_i,A_j \neq A_i,B_i\neq B_j\)
显然，B 序列是 A 的错排。在通常的定义中，错排 \(D(n)=(n-1)\times (D(n-1)+D(n-2))\) 是针对于有 \(n\) 个可选数、且序列长度为 \(n\) 的。
但是这里是有 \(m\) 个可选数、且序列长度为 \(n\)，并有 \(m\ge n\)。
可以考虑加法原理，即 \(B\) 序列的选择数一定是 \(D(n)+f(n)\) 的形式，这里可以找个例子来理解一下：
若 \(n=3,m=4\)，则 \(A\) 序列的个数为 \(A_{m}^{n}=A_{4}^{3}=24\)。
对于一个 \(A=1,2,3\)，\(B\) 的全部合法序列为：
\[\begin{aligned} 2,3,4 \\ 2,4,1 \\ 2,3,1 \\ 3,4,1 \\ 3,2,4 \\ 3,4,2 \\ 3,1,2 \\ 3,1,4 \\ 4,3,1 \\ 4,1,2 \\ 4,3,2 \\ \end{aligned} \]总共 \(11\) 种。可以看出，除过与 \(A\) 序列元素相同的排法，在第 \(N\) 位上，会有 \(m-n\) 个 \(A\) 序列中没有的元素，在本例中即是数字 \(4\)。而对于剩下 \(n-1\) 位，有 \(D(n-1)\) 种排法。
所以这道题的答案是错排公式是改编版( \(M,N\) 代表题中给出数据 ) ：
\[D(n)= \begin{cases} 1 &,n=0\\ M-N&,n=1 \\ (M-N)\times D(n-1)+(n-1)\times(D(n-2)+D(n-1))&,otherwise \end{cases} \]P514. [SDOI2010] 古代猪文
小数论全家桶。但是比较简单。
答案显然是
\[\large G^{\sum_{d=1,d|n}^{n}C_{n}^{d}} \mod 999911659 \]但是直接使用逆元求 \(C\) 会炸时空。我们考虑扩展欧拉定理：
\[a^b \equiv a^{b \mod φ(m)} \pmod m,\gcd(a,m)=1 \]且由于 \(m=999911659\) 是个质数，所以 \(φ(m)=m-1=999911658\)
所以上式等价于：
\[\large G^{(\sum_{d=1,d|n}^{n}C_{n}^{d} )\mod 999911658} \mod 999911659 \]但 \(999911658\) 是个合数，所以我们把它进行质因数分解，这样就可以用 lucas 去求 \(C\)，然后用中国剩余定理合并答案即可。
标签：组合,个数,long,times,large,数学,笔记,序列,mod From： https://www.cnblogs.com/ccjjxx/p/18023936