这题显示只有18%的AC率，题目本身不难，估计都是败在执行时间上了；我的解法如下，典型的DP思维，子问题是：如果已知长度为n-1的情况下，和或操作相等的数列，求长度为n的情况；状态index为每个满足条件的数列的和Sn-1（因为和或相等，也是该数列的或），状态值为该index对应的数列有多少种。状态转移方程为:
if Xn | Sn-1 == Xn + Sn-1: then Stat[Xn|Sn-1] += Stat[Sn-1]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class YetAnotherORProblem2: def countSequences(self, n, r): ls = {0:1} c = 0 mc = 1 while mc < r: mc <<= 1 mc -= 1 for i in range(0, n+1): if i == n: for k,v in ls.items(): c += v return c%1000000009 cs = {0:0} for k,v in ls.items(): mask = mc^k # 这里是个重要的优化，大于mask+1的值不可能满足条件 for j in range(0, mask+1): if k & j == 0: cs[k+j] = cs.get(k+j, 0) + v ls = cs.copy() |