欧拉函数

 

几个排列组合计数的变式问题

原问题:

可重复选择的组合。有n个不同元素,每个元素可以选多次,一共选k个元素,有多少种方法。

刘汝佳; 陈锋. 算法竞赛入门经典——训练指南 (算法艺术与信息学竞赛) (Kindle位置1683). 清华大学出版社. Kindle 版本.

解:ANS = C(n+k-1,  n-1)。可以用方程的解的思路来做。

变式:

  1. 有n个不同元素,每个元素可以选多次,一共选k个元素排成一排,有多少种排法。
  2. 有n个元素,每个元素有ni个,每个元素可以选[0,ni]个,一共选k个元素,有多少种方法。
  3. 有n个元素,每个元素有ni个,每个元素可以选[0,ni]个,一共选k个元素排成一排,有多少种排法。

 

费马小定理的运用

当mod为素数的时候,运用费马小定理避免使用扩展欧几里得求逆元。

从这学到的:

  1. 手镯问题polya定理计数最后除 2n 因为mod为1000000007,“可以由(1/x)%mod=(x^(mod-2))%mod来求分母,转化为乘法。”https://blog.csdn.net/sdau20163942/article/details/78984555
  2. 一篇不错的乘法逆元总结https://blog.csdn.net/yukizzz/article/details/51105009
  3. 另一篇不错的乘法逆元总结https://www.cnblogs.com/Tuesdayzz/p/5758670.html

2,3还没有仔细看,放在这。