[SPOJ TLE]Time Limit Exceeded(数位DP,计数DP,高维前缀和)

发布于 2018-02-22  10 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[SPOJ TLE]Time Limit Exceeded(数位DP,计数DP,高维前缀和)

Description

Given integers N (1 ≤ N ≤ 50) and M (1 ≤ M ≤ 15), compute the number of sequences a1, ..., aN such that:
0 ≤ ai < 2M
ai is not divisible by ci (0 < ci ≤ 2M)
ai & ai+1 = 0 (that is, ai and ai+1 have no common bits in their binary representation)

Http

SPOJ

Tag

动态规划,高维前缀和

题目大意

给出一列数,要求求出满足条件的数列的方案数。

解决思路

由数据范围容易想到,设\(F[i][j]\)表示前\(i\)个数,第\(i\)个数是\(j\)的方案数,那么有转移方程
\[ F[i][j]=\sum_{k\&j==0} F[i-1][k]\]
不难发现,这里要求的\(k\)就是\(j\)的补集的子集,为了方便计算,我们可以记\(Sum[S]\)表示\(S\)及\(S\)子集的方案数总和,需要的时候直接赋值进去就好。
怎么求这个呢?这里用到一种叫做高维前缀和的科技,可以在\(O(n*2^n)\)时间范围内求得子集之和。具体来说,是这样

正确性暂不会证明。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[SPOJ TLE]Time Limit Exceeded(数位DP,计数DP,高维前缀和)


HNCJ OIer 一枚