NOI2024省选训练赛 11 解题报告

A. 小L的栈

Description

有一个栈和 \(n\) 个元素，这 \(n\) 个元素要依次入栈，并且最终全部出栈，要求第 \(m\) 个元素入栈后，栈内恰好有 \(k\) 个元素。

求方案数，对 \(10^9+7\) 取模。

Constraints

对于 \(30\%\) 的数据，\(n,m,k\le30,T\le 100\)

对于另外 \(30\%\) 的数据，\(n,m,k\le 10^3,T\le 10\)

对于 \(100\%\) 的数据，\(1\le n,m,k \le 10^6,T\le 10000\)

Solution

这题用了一个神秘的公式，扩展卡特兰数：有 \(n\) 个左括号和 \(m\) 个右括号，组成一个串，任何一个前缀的左括号个数都不少于右括号个数，那么不同的串的个数为：\({n+m \choose m}-{n+m \choose m-1} \; (n\ge m)\) 。

当第 \(m\) 个元素入栈后，栈内恰有 \(k\) 个元素，也就是说，前面总共有 \(m\) 次入栈操作，\(m-k\) 次出栈操作。

后面要把所有元素入栈后出栈，所以有 \(n-m\) 次入栈操作，\(n-m+k\) 次出栈操作。

我们分别套用扩展卡特兰数的计算公式即可。对于后面的情况，我们修改扩展卡特兰数的计算公式：有 \(n\) 个左括号和 \(m\) 个右括号（\(n \le m\)），组成一个串，使得任何后缀的右括号个数不少于左括号个数，那么共有 \({n+m \choose n}-{n+m \choose n-1}\) 种串。（相当于对反串做这个公式）

Conclusion

赛时除了扩展卡特兰公式以外的东西都想到了，推了半天式子都没推出来，现在也证不出来这个式子，就姑且先当个结论背着。

B. interval

Description

给定一个长度为 \(n\) 的序列。

支持以下两种操作：

第一种操作输入 \(l,r,x\) ，问能否在最多修改区间 \([l,r]\) 内一个数字的情况下，使得区间 \([l,r]\) 的 gcd 为 \(x\) 。
第二种操作输入 \(x,c\) ，表示将第 \(x\) 个值变为 \(c\)

总共有 \(q\) 次操作。

Constraints

对于 \(100\%\) 的数据，\(n,m \le 50000,a_i \le 10^9\)

Solution

第一种操作相当于问区间里面是否有多于 1 个数不是 \(x\) 的倍数。

用线段树维护区间 gcd，每次问询考虑当前区间：

如果区间 gcd 是 \(x\) 的倍数，那么直接返回
否则分别递归两个子区间计算。

递归处理问询的时候维护一个全局的计数器 \(cnt\)，表示当前已经有多少个节点所维护的区间的 gcd 不是 \(x\) 的倍数，当 \(cnt\) 的值大于 1 的时候，就可以直接结束递归。

Conclusion

鉴定为，莫队莫傻了，直接往莫队的方向想，写了一个带修莫队，然后发现思路假了。主要是第一步（也就是把问询转化为统计非 \(x\) 的倍数的数的个数）让我往莫队那个方向去想了，这种多个区间统计，而且可以离线的东西太容易让人想到莫队了。

但是，如果只关注区间 gcd 这个点的话，就可以很直接的想到线段树。

C. Digit Sum

Description

对于任意非负整数 \(x\) 和 \(m(2\le m)\) ，定义 \(f_m(x)\) 为 \(x\) 在 \(m\) 进制下的各位数字之和。例如 \(f_{10}(87654)=8+7+6+5+4=30,f_{100}(87654)=8+76+54=138\)。

给定两个整数 \(x\) 和 \(n\)，你需要计算是否存在某个 \(m\ge 2\) 使得 \(f_m(x)=n\) 。如果存在，输出最小的满足条件的 \(m\) ；如果不存在，输出 \(-1\)。

Constraints

对于 \(30\%\) 的数据，\(1\le x,n \le 10^6\)

对于 \(100\%\) 的数据，\(1\le x,n\le 10^{11}\)

Solution

考虑一个根号分治：

如果进制数 \(m\le \sqrt x\) ，那么我们可以枚举 \(m\)，然后计算是否合法。复杂度为 \(O(\sqrt x \log x)\)

否则，\(x\) 在 \(m\) 进制下只有两位，我们枚举高位，然后计算低位，并且以此判断是否存在对应的基数即可。由于在这种情况下，基数是大于 \(\sqrt x\) 的，所以高位最多是 \(\sqrt x\) ，因此复杂度是 \(O(\sqrt x)\)

所以，单次问询的复杂度是 \(O(\sqrt x \log x)\)

Conclusion

这种和进制以及数位和相关联的题目，一般而言是考虑数位 dp 或者同余最短路，但是这题并不是。这题用到了这样的一个思考：\(m\) 只能取 \([2,x+1]\) 之间的整数，当 \(m\) 比较大的时候，\(x\) 在 \(m\) 进制下对应的数位数不会很多，可以考虑直接枚举。而在 \(m > \sqrt x\) 的时候，\(x\) 在 \(m\) 进制下就只有两位了，因此对于较大的情况，我们枚举两位数；对于较小的情况，我们直接枚举 \(m\) 。