TLE - Time Limit Exceeded
题意翻译
给定$n$和n个数$c[i]$,要求构造出一串序
列$a[i]$,要求
1.$a[i] \in [0,2^m)$
2.$a[i] \%c[i]!=0$
3.$a[i]$&$a[i+1]=0$
求方案数
感谢@龙神哈迪斯 提供的翻译
题目描述
Given integers N (1 ≤ N ≤ 50) and M (1 ≤ M ≤ 15), compute the number of sequences a $ _{1} $ , ..., a $ _{N} $ such that:
- 0 ≤ a $ _{i} $ < 2 $ ^{M} $
- a $ _{i} $ is not divisible by c $ _{i} $ (0 < c $ _{i} $ ≤ 2 $ ^{M} $ )
- a $ _{i} $ & a $ _{i+1} $ = 0 (that is, a $ _{i} $ and a $ _{i+1} $ have no common bits in their binary representation)
输入输出格式
输入格式
The first line contains the number of test cases, T (1 ≤ T ≤ 10). For each test case, the first line contains the integers N and M, and the second line contains the integers c $ _{1} $ , ..., c $ _{N} $ .
输出格式
For each test case, output a single integer: the number of sequences described above, modulo 1,000,000,000.
输入输出样例
输入样例 #1
1
2 2
3 2
输出样例 #1
1