T1.dnf

题意:给定n个技能,其中k个只能各使用Li次。求使用m次技能的次数组合有几种(某种技能的使用次数不同,组合就不同)。(n,m<=100000,k<=15)
分析:注意到k<=15,这很有可能是容斥的题。
如果每种技能都可以使用无限次,根据插板法,所有的组合数为:
$$
C_{n+m-1}^{n-1}
$$
接着思考,如果有一种技能超过了Li,现在将那(Li+1)次去掉,那么就相当于使用总数减少了(Li+1)次。接着就可以使用插板法求组合数:
$$
C_{n+m-1-(Li+1)}^{n-1}
$$
所以根据容斥原理:
$$
ans=\sum{\pm C_{n+m-1-\sum{(Li+1)}}^{n-1} }
$$
那么给出代码就是:



T2.euclid

题意:给定一个n,求gcd(a,b)递归层数最多的a,b(a,b<=n) (n<=1e12000)
思路:考虑到n十分巨大,这道题一定会使用高精度。
分析之后不难发现,当a,b为相邻的两个斐波那契数时,递归层数最多。且a<b比b<a时更多一层。
由于斐波那契数相邻两项之比趋近于1.618,所以我们要计算到的斐波那契数大约需要57700项。
如果高精度加法速度较快,不压位可能可以通过,但是如果压17位通过把握更大。

有关卡常技巧:

1.压位:
在x64系统内使用long long效率更高,带来的常数优化也更强,但是在32位系统,最好用unsigned int压8位。(亲测17位+O2仅需0.3秒算完最大数据,不压位0.9秒)

2.高精度模板:
为了获得更高的计算速度,我们的高精度加法函数最好写成inline的,且传入的参数都是指针,内部只有一个循环。这样效率更高。数组也应尽量开小一些。

3.避免冗余操作:
在高精度加法之前,避免使用memset而是用一些特判代替。在计算斐波那契数时,最好只开3个变量轮流使用,并且通过指针访问那三个变量,交换变量时直接交换指针,速度回更快。

4.奸诈的技巧:
强制开O2

所以总的代码就是这样的:



T3.divisor

题意:求1~N中哪个数因子最多。(N<=1e9)
分析:又是一道打表题
怎么打表呢?
注意到这里是求因子个数,所以我们可以使用O(NlnN)的筛法求每个数的因子个数。问题是1e9的数组开不下,于是我们可以开一个2e8的数组,分5次筛,每次记录上一次的最多因子数。这样可以在10分钟内全部求出。
而且由于最多因子数是递增的,而且不会超过sqrt(n)个数,所以最终打出来的表还不到1kb。