Happy Matt Friends
Happy Matt Friends
Time Limit: 6000/6000 MS (Java/Others) Memory Limit: 510000/510000 K (Java/Others)
together.
Each of Matt’s friends has a magic number. In the game, Matt
selects some (could be zero) of his friends. If the xor (exclusive-or) sum of
the selected friends’magic numbers is no less than M , Matt wins.
Matt
wants to know the number of ways to win.
indicates the number of test cases.
For each test case, the first line
contains two integers N, M (1 ≤ N ≤ 40, 0 ≤ M ≤ 106).
In the
second line, there are N integers ki (0 ≤ ki ≤ 106),
indicating the i-th friend’s magic number.
where x is the case number (starting from 1) and y indicates the number of ways
where Matt can win.
3 2
1 2 3
3 3
1 2 3
Case #2: 2
In the first sample, Matt can win by selecting:
friend with number 1 and friend with number 2. The xor sum is 3.
friend with number 1 and friend with number 3. The xor sum is 2.
friend with number 2. The xor sum is 2.
friend with number 3. The xor sum is 3. Hence, the answer is 4.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, ls[rt]
#define Rson mid+1, R, rs[rt]
const int maxn=2e6+;
using namespace std;
ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}
inline ll read()
{
ll x=;int f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,k,t,cas;
ll dp[][maxn],ans;
int main()
{
int i,j;
scanf("%d",&t);
while(t--)
{
memset(dp,,sizeof(dp));
ans=;
dp[][]=;
scanf("%d%d",&n,&m);
rep(i,,n)
{
scanf("%d",&k);
for(j=;j<=1e6;j++)dp[i%][j]=dp[(i-)%][j]+dp[(i-)%][j^k];
}
rep(i,m,1e6)ans+=dp[n%][i];
printf("Case #%d: %lld\n",++cas,ans);
}
//system("Pause");
return ;
}
最新文章
- java.sql.SQLException: ORA-01000: 超出打开游标的最大数
- 2017技术核心——Spring
- Java入门记(一):折腾HelloWorld
- eclipse的安装环境及eclipse下maven的配置安装
- git push错误解决方案
- SQL 跨服务器数据库增、删、改、查(一)
- 【转载】setjmp和longjmp函数使用详解
- maven工程-eclipse红叹号
- SQL Server 创建作业系列问题
- Design Thinking BrainWalk
- XMPP学习及使用1
- Linux上删除大量文件几种方式对比
- 基于 TensorFlow 在手机端实现文档检测
- linux1
- 感觉还是要学点c才牛逼
- WebApi 增加身份验证 (OAuth 2.0方式)
- WPF实现主题更换的简单DEMO
- Logstash 解析Json字符串,删除json嵌套字段
- Solidworks机构运动仿真
- Dapper实用教程