happy matt friends
time limit: 6000/6000 ms (java/others) memory limit: 510000/510000 k (java/others)
total submission(s): 5188 accepted submission(s): 1985
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.
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.
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.
题意:题目大意:n个数,从中挑k个,使得这k个数的异或和不小于m,问有多少种挑选方法(0<=k<=n)
思路:dp[i][j]表示前 i 个数中选择一些使得异或和为j的方法数,转移方程:dp[i][j] = dp[i – 1][j] + dp[i – 1][j ^ a[i]],即等于前i-1个异或和为j的方法数(第i个数不需要进行异或)加上前i-1个异或和为j ^ a[i]的方法数(第i个数需要异或),因为j ^ a[i] ^ a[i] == j ^ (a[i] ^ a[i]) == j ^ 0 = j,最后再累计一下j大于等于m时的方法数,这题内存给的够大,也可以直接采用滚动数组
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdlib> #include<queue> #include<set> #include<vector> using namespace std; #define inf 0x3f3f3f3f #define eps 1e-10 #define ll long long int const maxn = (1<<20); const int mod = 1e9 + 7; int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } int a[42]; ll dp[42][maxn]; int main() { int t; scanf("%d",&t); int ca=1; while(t--) { int n,m; memset(dp,0,sizeof(dp)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); dp[0][0]=1; for(int i=1;i<=n;i++) for(int j=0;j<maxn;j++) dp[i][j]=dp[i-1][j]+dp[i-1][j^a[i]]; //如果前i-1个数异或值是j就不需要将第i个数进行异或,如果前i-1个数有异或后是j^a[i]的,那么第i个数进行异或,刚好可以得j ll ans=0; printf("case #%d: ",ca++); for(int i=m;i<maxn;i++) ans+=dp[n][i]; printf("%lldn",ans); } return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/608409.html