//唔,这次被虐的有点惨啊/(ㄒoㄒ)/~~

T1 pf

听说可以动归做?
真神奇,这不是数论题么。。。

我考场搞了两个半小时搞了个容斥原理做出来了。(心好累,人家kb随便乱搞了一下就93分。。。)

首先要明白,斐波那契完全用不上,就是来装逼吓人的。。。
直接用$i$代替$fib[i]$就行了。。。

首先,如果不需要你每个元素都至少用一次的话:序列的第一位有$n$种选择,第二位有$n-1$种选择,第三位有$n-2$中选择...第$m+1$位有$n-m$种选择,第$m+2$位依然是有$n-m$种选择,后面的也都是这样的,所以方案数是:
$n\times (n-1)\times (n-2)\times ... \times (n-m) \times {(n-m)}^{p-m-1}$
也就是
$n!\div {(n-m)}!\times {(n-m)}^{p-m}$

但是这样子,可能某种元素没用。。。
所以我们要排除有的元素没用的方案。

如果是有1个元素没用的话:序列的第一位有$n-1$种选择,第二位有$n-2$种选择,第三位有$n-3$种选择,第$m+1$位有$n-m-1$种选择,第$m+2$位依然是有$n-m-1$种选择,后面的也都是这样的,所以方案数是:
$(n-1)\times (n-2)\times ... \times (n-m-1) \times {(n-m-1)}^{p-m-1}$
也就是
$(n-1)!\div {(n-m-1)}!\times {(n-m-1)}^{p-m}$
然后有$n$种元素,选择其中的一个不选,有$n$种选法,所以方案数一共有:
$n!\div {(n-m-1)}!\times {(n-m-1)}^{p-m}$

这样拿上面那个$n!\div {(n-m)}!\times {(n-m)}^{p-m}$再减去这个$n!\div {(n-m-1)}!\times {(n-m-1)}^{p-m}$。。。

你就发现得到的结果比答案小了。。。

这是为什么呢?
因为你减掉了的这个1个元素不选的方案中,还包含了2个元素不选的啊!
所以我们得把2个元素不选的加上去。。。
然而这样你又把3个元素不选的多加了(本来要减去的)。。。
所以我们又要把3个元素不选的减去。。。
然后4个不选的又多减了。。。
一直这样下去,还有完吗?
当然有完——一共就n个元素啊!

所以我们就给出答案了。。。

$i$个元素不选的方案数显然是:
${C_n^i}\times (n-i)!\times (n-m-i)^{p-m}\div (n-m-i)!$
当$i$为奇数时,答案减去$i$对应的方案数;
当$i$为偶数时,答案加上$i$对应的方案数。

$\{i|0\leq i< n\}$

用杨辉三角算组合数,记得取模,而且取模记得处理负数(加上模数再取模)

代码:



T2 guard

唔,概率dp。。。
考场原地蒙圈。。。

设$f(i,j,x)$为当前比了$i$场,背包容量为$j$,赢了$x$场的概率。
$f(i,j,x)=f(i-1,j,x)\times (1.0-p[i])+f(i-1,j-a[i],x-1)\times p[i]$

因为一共只有200场,所以背包容量>200是没有意义的,每次容量对200min/max一下就行了。
还有$0\leqslant j\leqslant 400$,当$j>=200$时表示背包还有$400-j$的空余容量,当$j< 200$时表示有$200-j$个残片没装。

代码:



T3 hamilton

考场打了个5维floyd。。。
要交的时候改成了输出0。。。
得10分。。。
后来发现五维floyd可以拿30。。。

思路:状压dp
设$f(i,s)$为从节点$i$出发,访问状态为$s$时的简单环个数。
状态:二进制下,$s$的第$k$位为1表示节点$k$被访问过了,为0表示没访问过。
为防止重复计算,我们让$i$为状态$s$中编号最小的节点。
然后因为从一个节点扩展,环的双向都走过了,所以答案要除以二输出。

时间1s,最后一个点5s。。。下面提供两个优化方法(优化后第9个点0.2s,第10个点1.2s,原本是第9个点1.2秒,第10个点5.7秒)。

  1. 用low_bit函数计算状态$s$中编号最小的节点——先预处理处$log2(2^i)$的值,每次获得最小节点编号则:$log2(low\_ bit(s))$。

  2. 预处理出状态$s$中被访问的节点个数($s$二进制下数字1的个数),递推实现即可

代码:



T4 cg

唔,动态规划的单调队列优化。。。
设$f(i)$为前$i$头牛的最小价值。
$f(i)=max\{f(j)|i-k\leqslant j\leqslant i-1\}$
用单调队列维护:$max\{f(j)|i-k\leqslant j\leqslant i-1\}$

代码: