【模板】输入输出挂

做hdu 6396被卡输出输出了,关键是用输入输出优化都超时,用上了这套输入输出挂,就直接398ms过了

后来了解到做 hdu 5392 速度可能是:输入挂>不优化>输入优化

从这抄来的模板

 

这个地方有浮点数的输入优化,没尝试过,放在这。

 

另外一个板子

 

【模板】AC自动机

 

Eratosthenes筛选法欧拉函数打表

第二种写法更优。

maxn=1e7 第一种写法 0.6s, 第二种写法 0.5s

maxn=1e8 第一种写法 6s,第二种写法5s

Eratosthenes筛法

 

欧拉函数

 

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

原问题:

可重复选择的组合。有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还没有仔细看,放在这。

对拍.bat