首页 > 代码库 > HDU 5119 Happy Matt Friends(DP || 高斯消元)
HDU 5119 Happy Matt Friends(DP || 高斯消元)
题目链接
题意 : 给你n个数,让你从中挑K个数(K<=n)使得这k个数异或的和小于m,问你有多少种异或方式满足这个条件。
思路 : 正解据说是高斯消元。这里用DP做的,类似于背包,枚举的是异或的和,给定的数你可以选择放或者不放,dp[i][j]代表的是前 i 个数中选择k个异或的和为j。
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #define LL long long 5 using namespace std ; 6 int a[41] ; 7 LL dp[41][1 << 20] ; 8 int main() 9 {10 int T,n,m,casee = 1 ;11 scanf("%d",&T) ;12 while(T--)13 {14 scanf("%d %d",&n,&m) ;15 for(int i = 0 ; i < n ; i++)16 scanf("%d",&a[i]) ;17 memset(dp,0,sizeof(dp)) ;18 dp[0][0] = 1 ;19 LL ans = 0 ;20 if(m == 0) ans++ ;21 for(int i = 0 ; i < n ; i++)22 {23 for(int j = 0 ; j < (1 << 20) ; j++)24 {25 if(dp[i][j] == 0) continue ;26 dp[i+1][j] += dp[i][j] ;27 int temp = j ^ a[i] ;28 dp[i+1][temp] += dp[i][j] ;29 if(temp >= m)30 {31 ans += dp[i][j] ;32 }33 }34 }35 printf("Case #%d: %I64d\n",casee++,ans) ;36 }37 return 0;38 }
HDU 5119 Happy Matt Friends(DP || 高斯消元)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。