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
西月弦 阅读(286)
评论(0) 编辑 收藏 引用 所属分类:
解题报告