# [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)

SPOJ

## 解决思路

$F[i][j]=\sum_{k\&j==0} F[i-1][k]$

HNCJ OIer