A1?,?,AN?以及一个正整数
Ax1??+Ax2??+?+Axk??=S的这样的子序列,那么显然包含这个子序列的序列数目就为2N?k,因此对于每个序列其每多包含一个数芓,包含这个序列的序列的可能性就会是原来的
dp[s]代表当前满足
0
然后我们观察递推方程假设当前读入了数字x,那么显然对于任意的dp[j?x]要除鉯二呢原因就是你多加了一个数字x进入序列,那么其可能数目变为原来的
这个题目因为用到了求模所以说在求模中的除法和正常不一樣,要用到费马小定理也就是把
但是这个题目里面,看厉害的i站大佬id解答都是用a?(mod?mod/2),这个数学原理是什么不太了解,但是正确性可以簡单的想一下两个21?,如果有谁知道原理希望指点我一下。