本文共 1719 字，大约阅读时间需要 5 分钟。

J — number sequence

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 0    Accepted Submission(s): 0  

Problem Description

You are given a number sequence a[1], a[2]...a[n]，you can add some operators O[i](each one is ‘+’, ‘|’ or ‘^’) between them. Now, I give you a constant A, you should calculate how many kinds of Operators sequence O[i] satisfy :

a[1] (O[1]) a[2] (O[2]) a[3] ...... (O[n-1]) a[n] = A.  Note that there is no precedence between the operators, meaning that all kinds of operators have the same priority relationship.

 

Input

The first line of the input contain a positive integer T, which denotes the number of test cases. The description of each test case is given below.

Each test case start with two positive integers n, A. the size of the number sequence and the constant as mentioned above. The next line contains n integers a[i].

 

Output

Your output should contain T lines, each line only has an integer, which are the answer mod 1000000007.

T <= 10. 0 < N ≤ 100000. 0 ≤ ai, A ≤ 100.

 

Sample Input

2 2 2 1 3 3 3 1 2 3

 

Sample Output

1 3

 

Hint

In the first case, The legal formula is “1 ^ 3 = 2”. In the second case, The legal formula is “1 + 2 | 3 = 3”, “1 | 2 | 3 = 3”, “1 ^ 2 | 3 = 3”.

 

解题思路：dp[] 大小必须大于128。因为二进制：128 64 32 16 8 4 2 1，很有可能超过运算时已经 >=100 && <=128，但是可以通过运算又回到 100，所以不能大小定义在 100~128 之间。

 

AC 代码

#include
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a);#define INF 0x3f3f3f3fusing namespace std;typedef long long ll;const int maxn=1e5+100, mod=1000000007;int a[maxn], dp[150], tdp[150];int main(){    int T; scanf("%d",&T);    int n,m;    while(T-- && ~scanf("%d%d",&n,&m))    {        mem(dp,0); mem(tdp,0);        for(int i=0;i
    
   

 

转载地址：https://lux-sun.blog.csdn.net/article/details/81101242 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！