[题解]洛谷 P4930、BZOJ 4221

洛谷 P4930

考虑 \(\varphi\) 有什么性质，设 \(x\) 的质因数分解为 \(\prod_{i=1}^m p_i^{a_i}\)，那么 \(n=\varphi(x)=\prod_{i=1}^m(p_i-1)\times\prod_{i=1}^m p_i^{a_i-1}\)，显然 \(n\) 的因数 \(d\) 如果加一后是质数，那么 \(d+1\) 就可能是 \(x\) 的因数，反之亦然，又注意到答案不多，所以暴力搜索即可通过。

这道题的关键是注意到答案数量级很小，可以大胆搜索。

BZOJ 4221

首先注意到鼠和袋其实是分离的，鼠装没装进袋不影响它继续装鼠，袋装没装鼠也不影响袋主继续被装，唯一的限制是鼠只能装进一个袋，一个袋只能装一个鼠，所以想到拆成 \(2n\) 个点搞匹配。

由于鼠不会装进自己的袋，所以这个条件去掉，此时就相当于满足条件的即可乱装，众所周知排序不亏，所以鼠和袋都从大到小排序。

观察装到不能再装的条件是什么：设当前最后一个没装的鼠能装进 \([1,x]\) 袋，那么这些袋子一定都装满了。

有了这些条件考虑如何求答案，看到要求方案数且 \(n\) 比较小，可以考虑动态规划。第一步设状态，考虑当前转移和什么有关，首先肯定要记录当前匹配到第 \(i\) 只鼠，然后看袋，设 \(i\) 最多能匹配到 \(x\)，那么只需要关注 \([1,x]\) 中袋的匹配情况，需要记录 \(j\) 个袋和 \([1,i]\) 中的鼠匹配。这样就可以转移了吗？因为显然要求立方所以不行。注意到还有一个要求是如果 \(i\) 没装袋，那么 \([1,x]\) 需要装满，如果 \(j<x\) 就意味着剩下的一定和后面的鼠匹配了，所以需要多记录一个 \(k\) 表示 \([1,x]\) 中有 \(k\) 个袋装 \(i\) 后面的鼠，这样我们就可以根据 \(i\) 装不装讨论转移：

1. \(i\) 不装，那么 \([1,x]\) 要填满，\(f_{i,j,x-j}\leftarrow f_{i,j,x-j}+f_{i-1,j,k}\)；
2. \(i\) 装，且装到未定的袋，\(f_{i,j+1,k}\leftarrow f_{i,j+1,k}+(x-j-k)f_{i-1,j,k}\)；
3. \(i\) 装，且装到预订装后面鼠的袋，\(f_{i,j+1,k-1}\leftarrow f_{i,j+1,k-1}+kf_{i-1,j,k}\)。

然后输出 \(\sum_{i=0}^n f_{n,i,0}\) 即可。

这个题最重要的是转换成匹配，然后动规的状态要设计好。