在https://www.luogu.com.cn/problem/P4141
题中,第二篇题解的状态转移方程if(j−v[i]>=0)f[j][1]=(f[j][0]−f[j−v[i]][1]+10)
但是在转移中可能会出现负数,但由于题目让求个位数的值,加上10再%10,这样解释我还可以接受
我去问AI为什么会出现负数,AI告诉我
在用“差分”或“容斥”这类技巧做动态规划的时候,出现负数的中间状态并不意味着「真的有负的方案数」,它只是一个**“调整量”**,用来剔除重复计数或修正过多计入的部分。只要最终你把这些中间状态正确地“拼”回来(比如再加上被减掉的部分、或者在模意义下取余),结果一定是非负的真实方案数。
但是在这个式子中,f[j][1]只被计算了一次,就是说他最终的方案数可能是负数
我又想如果我不只求体积为j,删去x的方案数的个位数,我要求体积为j,删去x的方案数,如果这样的话怎么办?
我现在可以想明白为什么有负数,就是根据
使用i体积j的方案数=不用i体积j的方案数+使用i体积j−i的体积的方案数
但是我想不明白为什么有负数他的方案数也是正确的,并且为什么+10%10他就是正确的。还有就是如果要求方案数而不是方案数的个位怎么办
希望有大佬可以解答一下