首页 > 代码库 > HDU 5119 Happy Matt Friends(DP || 高斯消元)

HDU 5119 Happy Matt Friends(DP || 高斯消元)

2024-08-06 02:54:08   221人阅读

题目链接

题意 ： 给你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 }
View Code

 

HDU 5119 Happy Matt Friends(DP || 高斯消元)


联系
我们