0。Guass消元的方法
Guass消元可以求矩陣的秩，行列式，逆元，解方程組等等。
矩陣的值可以是整數 or 浮點數。
對于解方程組來說，x1 + x2 + ... mod m = b 用主列消元法，需要求逆元。
如果是浮點數，可以用迭代法（spfa），在姜碧野的論文里有講。
1。利用Guass消元解決計數問題
這一類我掌握的不好，一般來講是求方程組的解的個數。
當然應該只對 x1 + x2 + ... + xn mod m = b 這樣的整數方程組有效了。
srm 590 div1 500就是典型的例子，在n個數中挑選一些數，讓其xor值小于等于limit。
這個問題和等于是等價的。至于等于怎么求，就是方程組的解數了。和自由元的個數相關。
srm 590div1 500pt
1 #include<iostream>
2 #include<vector>
3 using namespace std;
4 typedef long long ll;
5 typedef vector<int> Vec;
6 typedef vector<Vec> Mat;
7 ll Guass(vector<ll>& number,ll limit)
8 {
9 int m = number.size();
10 Mat matrix(50,Vec(m+1));
11 for(int i = 0; i < 50; i++){
12 for(int j = 0; j < m; j++){
13 matrix[i][j] = !!(1LL << i & number[j]);
14 }
15 matrix[i][m] = !!(1LL << i & limit);
16 }
17
18 int free = 0,line = 0;
19 for(int row = 0; row < m ; row++){
20 int p = -1;
21 for(int i = line; i < 50; i++) if(matrix[i][row]){
22 p = i;
23 }
24 if(-1 == p){
25 free ++;
26 continue;
27 }
28 swap(matrix[line],matrix[p]);
29 for(int i = line + 1; i < 50; i++) if(matrix[i][row]){
30 for(int p = 0; p <= m; p++)
31 matrix[i][p] ^= matrix[line][p];
32 }
33
34 line ++;
35 }
36 for(int i = line; i < 50; i++)
37 if(1 == matrix[i][m])
38 return 0;
39 cout<<"answer : "<< limit <<" "<<free<<endl;
40 return 1LL << free;
41 }
42 class XorCards{
43 public :ll numberOfWays(vector<ll> number,ll limit)
44 {
45 int n = number.size();
46 ll ans = Guass(number,limit);
47 for(int i = 0; i < 50; i++) if(1LL<<i & limit){
48 vector<ll> vct(n);
49 for(int j = 0; j < n; j++){
50 vct[j] = number[j] >> i;
51 }
52 ans += Guass(vct,(limit>>i) - 1);
53 }
54 return ans;
55 }
56 };2。開關問題
3。求期望
posted on 2013-09-14 01:13
西月弦 閱讀(303)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告