P9838 挑战 NPC IV-526互联

数据点分治诈骗好题
先考虑 \(k=1\) 怎么做？可以发现 \(f(i)\) 值相同的数量我们可以轻易算出。怎么贪心？大的对小的一一匹配即可
开始诈骗：考虑 \(n\in [29,10^6]\)。发现 \(f(i)\) 相同的值有很多，例如 \(f(i)=1\) 的大约有 \(\frac{n}{2}\) 个，\(f(i)=2\) 的大约有 \(\frac{n}{2^2}\) 个......因此考虑能取到最小值的排列数，显然严格大于 \(\prod\limits_{i=1}^{\log_2 n} (\frac{n}{2^i})!\) 个，发现当 \(n\) 取到 \(29\) 时这个式子就 \(> 10^{18}\) 了，因此直接用 \(k=1\) 的情况算即可
那 \(n\leq 28\) 的怎么办？我们发现 \(f(1)=16,f(2)=9,f(3)=5,f(4)=3,f(5)=2,f(6)=1\)，因此考虑暴力 \(dp\)。设 \(dp_{a,b,c,d,e,f,sum}\) 表示分别取了 \(a,b,c,d,e,f\) 个，和为 \(sum\) 的方案数。