模拟34 题解

A. 次芝麻

显然答案是$min(n*2^k$%$(n+m),(n+m)-n*2^k$%$(n+m))$

因为每一次乘2，在取模意义下，选大选小是等价的。

B. 喝喝喝

$a_x$%$a_y=k$

$a_x-k=a_y*m$

所以直接对$a_x-k$质因数分解，两个单调指针乱扫就完了。

C. 长寿花

暴力状压：直接考虑集合。

然而并没有必要：因为每种颜色是等价的，只关注集合选取了几种颜色。

所以改变dp的定义，求出一个f数组作为转移系数，顺便乘个组合数就可以了。

关于转移系数：

$f(i,j)$表示将i种颜色放进j个格子里，要求同种颜色不相邻的方案数。

初态$f(0,0)=1$

$f(i,j)=f(i,j-1)*(i-1)+f(i-1,j-1)*i$

原因比较好解释，前j-1个格子用了i种颜色，最后一个除了第j-1个格子用的颜色都能用。

前j-1个格子用了i-1种颜色，枚举没用的是哪个颜色，补上就可以了。

因为模数不是质数，直接分解质因数，或者用组合数的原始式子推就行。