hdu 4602 Partition
数学推公式 or 矩阵快速幂
[2013多校联合训练第一场]
题意:比较易懂的题意,给出一个n,可以由多种方式分解它
4=1+1+1+1
4=1+1+2
4=1+3
然后给定一个数字m,问在这里分解中m这个数字出现了几次
多校的第一场,看到这题,觉得答案肯定很大,没想法,但是觉得这么的数据,肯定是数学题,第一反应是,找规律,所以写了一个dfs的暴力程序,把1<=n<=20,对于每个n的每个因子出现了几次都打印出来,然后发现了规律
下面给出n<=10的时候打出来的表
1[144]
很明显看到是一个数列,但是这个数列有什么规律呢?我们这样定义项数,对于n,因子x=n为第1项,x=n-