大家好！我是一只蒟蒻初二数竞选手

在一次数学课上，老师给我们留了一道题，我做了出来

我发现它可以出成OI题，于是开心地放到了校内UOJ上

直到WC讲课前，我发现这就是Stilwell的讲课内容ULAM游戏

是不是很有趣呀！

以上就是我写这篇博客的背景(其实真实原因是我给UOJ投题被大神退了)

以下是题面：

在ulam游戏中，考虑至多撒谎一次的情况。

告诉你至多撒谎一次的子集大小n, 不能撒谎的子集大小m，求出在两人都足够聪明的情况下，猜测者至少猜几次才能确认想数者所想的数。

数据范围：n, m <= 10^5000

这道题有明显的(nm)^2 dp解法

利用单调性，可以做到n(m^2)或(n^2)m*logm

再搞一搞，也许能搞到n^2

但是数据这么大，除非使用-wangyisong编译这种复杂度是显然过不了的

那么正解是什么呢？

对于一种特殊的二维DP，满足

1.对大小级别为n的x,y，dp[x][y]级别为f(n); 对级别为logn的dp[x][y], 一定有x,y的级别为f(n)

2.对相同的x，dp[x][y]随y上升单调不减

3.对dp[x1][y1], dp[x2][y2], 其能松弛的dp[x][y]中的x仅与x1,x2相关

那么我们令max[a][b]表示使dp[b][q]为a的最大q值，而后用DP方法维护max。于是我们就把复杂度优化到了 原复杂度*(f(n) / n)的级别

在这道题中，可以证明f(n) = logn + loglogn + k (其中abs(k) <= 2), 且满足以上的三条要求

于是我们就把复杂度优化到了n(m^2)logm啦！

是不是很厉害呢？

然而，我们悲伤地发现，上法还没有单调性dp快

考虑如何优化

在上述的特殊DP中，再加上几个条件

1.考虑max[x1][y1]=z1, max[x2][y2]=z2, 若松弛值q = h(z1, z2)， 且h满足对a + b >= c + d, a >= b, c >= d, b >= d， 有h(a, b) >= h(c, d) (若干阶导数满足似乎亦可)

那么称h是"Slime"的（其实是一种类似于凸性的东西）

不难发现，原问题中的dp方程满足这一性质

而对于一个"Slime"的转移方程，其所被松弛的项的x下标是确定的

故此，我们可以将复杂度优化到nmlogm

虽然它仍跑不过，但已经很好了

兹兹不兹兹呀

接下来的优化方式，就比较简单了

可以利用数学方法证明，答案的取值范围介于log(n+m) + loglog(n+m) 正负常数(大概是2,3的范围) 的区间里

计算出与答案松弛相关的max坐标,总数的级别为logn

依次枚举每个答案，判断是否可行即可(其实可以不用枚举，但反正是常数，懒得算那么精确)

总复杂度为logn

其中高精度的运算过程并没有什么用，可以全部优化掉

但是...

我懒得优化了QwQ

于是出了log^2的范围

上课时曾和大神讨论过此问题，他告诉我计算熵的方法在至多撒谎一次的判断上是正确的

想了想，发现并不是...比如3,1就是反例

另外，这种dp能推广到撒谎更多次的情形（证明同理），复杂度为2^klogn 或 (2logn)^k

此类方法显然可以用到更多题上...不过由于我不是专业的OI选手，并未看过类似题目

UPD：我做麻烦了QwQ

但这种dp也许是有用的

我好菜呀O(∩_∩)O~