20171030 考试总结

考试策略

T1和异或有关......异或的东西我都不是很懂,估计做不出来,打个20分暴力。

T2是数学题......数学我完全学不懂啊,估计做不出来,打个暴力......woc为什么模数这么小,取逆元都不好搞。

T3是什么鬼啦,不过50分暴力还是会的......为什么死活调不出来啊喂!

今天考试体验极差.....姑且不论机房好冷和键盘特别反人类,出题人也很反人类而且jyf和boshi还会在做出题后敲键盘欢呼是什么鬼啦。

反正就是炸了......

T1

题目分析

首先假设所有数在二进制下有num(i)个数第i位是1,那么这一位造成的异或和贡献是$2\times (n-num(i))\times num(i)$嘛。所以用一个map来搞所有数,还是不难的.....

可是出题人太反人类了,模数给得特别大,所以必须用快速乘......

可是如果用log复杂度的快速乘会被卡成暴力分......

所以只能用O(1)玄学快速乘,并且取模还要玄学一发.....

代码:

T2

题目分析:

p=2333

设$S_n^k=\sum^k_{i=0} C_n^i \bmod p$

则利用卢卡斯定理

$S_n^k=\sum^k _ {i=0}(C^{n \bmod p} _ {n \bmod p}\times C^{i/p} _ {n/p})$

然后通过考虑$i/p$的取值来提取公因数(注意最后一项要单独考虑......)

$= \sum_{i=0}^{k/p-1}(C_{n/p}^i * \sum_{j=0}^{p-1} C_{n \bmod p}^j)+ C_{n/p}^{k/p}*\sum_{i=0}^{k \bmod p} C^i_{n \bmod p}$

然后前面的式子提取一下公因式,用S的定义化简一下:

$=S_{n/p}^{k/p-1}\times S_{n \bmod p}^{p-1}+C_{n/p}^{k/p}\times S_{n \bmod p}^{k \bmod p}$

于是我们可以打表出n与k小于p的所有S和C,然后运用递归和卢卡斯定理的手法来求解。

代码:

T3

题目分析:

考虑枚举剩余血量,那么不能用了的攻击可以强制用掉,然后玩多重背包。

那么我们可以根据攻击伤害来枚举剩余血量。

其实还可以排序后一边算多重背包一边计算答案。

然后用队列优化(计数问题无需单调队列)一下多重背包即可。

注意假如从大到小排序后,剩余血量应大于等于w(i),那么要强制用掉前i-1个技能,并且第i个技能要留下一个,跑多重背包。

代码: