这是我在这次 LG 月赛中领悟到的。
关于 T4
T4 让我们构造一个东西,在 \(\mod 998244353\) 的情况下。
然后你就很像把 \(0\) 给搞进去,发现不合理。
这时候怎么办?
可以把 \(0\) 变成 \(998244353\) !这样就行了。
很厉害,给我上了一课。
关于 T5
这启示我们往一类问题思考。
主要问题是这样的:长度为 \(n\) 的序列,一直不下降,可以相等,最后一个元素是 \(m\) ,问方案数。
考虑 dp
很快就能写出转移式。再加上前缀和优化,时间复杂度是平方级别。
可惜,笔者太菜了,后面往组合数学方向思考,没有任何结果。
最后一小时,发现 dp
可以优化成这个式子:
你可以从两个方向思考:
Trick 1
这个式子其实是路径问题。
转化一下,就是从 \((1,1)\) 到 \((n,m)\) 只能向下、向右走,到终点方案数。
我们把路径行走记下来,向右就是 \(1\) ,向下就是 \(0\) 。
然后 \(1\) , \(0\) 数量固定。
所以捏,这相当于,把 \(n\) 个 \(1\) , \(m\) 个 \(0\) 排列后不同的排列数。
经典问题,式子出来:\(C_{n+m}^n=C_{n+m}^m\)
Trick 2
这就是一个杨辉三角,我们把它转 \(45°\)。
然后递推式不就出来了吗。
根据组合数的理解,你能很快求出某列、某行,甚至某一斜对角线的值。
真是公公又式式!
后话
笔者太菜,最终也是冲刺了一波才到了 rk47.
标签:太菜,几个,T4,trick,dp,998244353,式子 From: https://www.cnblogs.com/g1ove/p/18117750