TLE - Time Limit Exceeded
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)
Input
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 c1, ... cN.
Output
For each test case, output a single integer: the number of sequences described above, modulo 1,000,000,000.
Example
Input: 1 2 2 3 2 Output: 1
The only possible sequence is 2, 1.
hide comments
end1es5ummer:
2023-03-23 14:17:37
Can somebody give any test datas for me? Last edit: 2023-03-23 14:24:55 |
|
airsplay:
2013-08-14 14:12:22
what the **** optimazation? |
|
wzc1995:
2013-05-05 15:11:10
a little optimize is expected!!!! |
Added by: | Bin Jin |
Date: | 2008-07-04 |
Time limit: | 1s-1.848s |
Source limit: | 5000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: CPP |
Resource: | co-author: Neal Wu |