題目鏈接

題意 ： 給你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

?

轉載于:https://www.cnblogs.com/luyingfeng/p/4142565.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的HDU 5119 Happy Matt Friends(DP || 高斯消元)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。