## 一位在退学边缘疯狂试探的学渣为了高代不挂科做出的最终努力

33281378432849
## 1. 爪形行列式

1. 求$D_n = \left| {\begin{array}{*{20}{c}} {{x_1}}&1& \cdots &1\\ 1&{{x_2}}& \cdots &0\\ \vdots & \vdots & \ddots &0\\ 1&0&0&{{x_n}} \end{array}} \right|$

## 2. 两三角型行列式

1. 求$D_n = \left| {\begin{array}{*{20}{c}} {{x_1}}&b& \cdots &b\\ b&{{x_2}}& \cdots &b\\ \vdots & \vdots & \ddots &b\\ b&b&b&{{x_n}} \end{array}} \right|$
2. 求${D_n} = \left| {\begin{array}{*{20}{c}} {{x_1}}&b&b& \cdots &b\\ a&{{x_2}}&b& \cdots &b\\ a&a&{{x_3}}& \cdots &b\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a&a&a& \cdots &{{x_n}} \end{array}} \right|$
3. 求${D_n} = \left| {\begin{array}{*{20}{c}} d&b&b& \cdots &b\\ c&x&a& \cdots &a\\ c&a&x& \cdots &a\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c&a&a& \cdots &x \end{array}} \right|$

## 3. 两条线型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}} {{a_1}}&{{b_1}}&0& \cdots &0\\ 0&{{a_2}}&{{b_2}}& \cdots &0\\ 0&0&{{a_3}}& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {{b_n}}&0&0& \cdots &{{a_n}} \end{array}} \right|$

## 4. 范德蒙德型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}} {{a_1^n}}&{{a_1^{n-1}b_1}}& \cdots &a_1b_1^{n-1}&b_1^n\\ a_2^n&a_2^{n-1}b_2&\cdots & a_2b_2^{n-1} &b_2^n\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_n^n & a_n^{n-1}b_n & \cdots & a_nb_n^{n-1}& b_n^n \\ a_{n+1}^n&a_{n+1}^{n-1}b_{n+1}&\cdots&a_{n+1}b_{n+1}^{n-1} &b_{n+1}^n \end{array}} \right|$

## 5. Hessenberg型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}} 1&2&3& \cdots &n\\ 1&{ - 1}&0& \cdots &0\\ 0&2&{ - 2}& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0&0&0& \cdots &{1 - n} \end{array}} \right|$

## 6. 三对角型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}} a&b&0& \cdots &0\\ c&a&b& \cdots &0\\ 0&c&a& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0&0&0& \cdots &a \end{array}} \right|$

## 7. 各行元素和相等型行列式

* 求${D_n} = \left| {\begin{array}{*{20}{c}} {1 + {x_1}}&{{x_1}}&{{x_1}}& \cdots &{{x_1}}\\ {{x_2}}&{1 + {x_2}}&{{x_2}}& \cdots &{{x_2}}\\ {{x_3}}&{{x_3}}&{1 + {x_3}}& \cdots &{{x_3}}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {{x_n}}&{{x_n}}&{{x_n}}& \cdots &{1 + {x_n}} \end{array}} \right|​$

## 8. 相邻两行对应元素相差K倍型行列式

1. 求${D_n} = \left| {\begin{array}{*{20}{c}} 0&1&2& \cdots &{n - 1}\\ 1&0&1& \cdots &{n - 2}\\ 2&1&0& \cdots &{n - 3}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {n - 1}&{n - 2}&1& \cdots &0 \end{array}} \right|$
2. 求${D_n} = \left| {\begin{array}{*{20}{c}} 1&a&{{a^2}}& \cdots &{{a^{n - 1}}}\\ {{a^{n - 1}}}&1&a& \cdots &{{a^{n - 2}}}\\ {{a^{n - 2}}}&{{a^{n - 1}}}&1& \cdots &{{a^{n - 3}}}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a&{{a^2}}&{{a^3}}& \cdots &1 \end{array}} \right|$


## 【Codeforces 802L】Send the Fool Further! (hard)

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 200009;
const int MOD = 1000000007;

int n, head[N], nxt[M], to[M], cost[M];
int a[N], b[N], fa[N], d[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void AddEdge(int u, int v, int c) {
static int E = 1;
d[u]++; d[v]++;
cost[E + 1] = cost[E + 2] = c;
}

inline int REV(int x) {
int ret = 1, t = MOD - 2;
for (; t; x = (LL)x * x % MOD, t >>= 1) {
if (t & 1) {
ret = (LL)ret * x % MOD;
}
}
return ret;
}

void solve(int w, int f) {
if (d[w] > 1) {
a[w] = -1;
for (int i = head[w]; i; i = nxt[i]) {
b[w] = (b[w] + (LL)cost[i] * REV(d[w])) % MOD;
if (to[i] != f) {
solve(to[i], w);
}
}
if (w != f) {
b[f] = (b[f] - (LL)b[w] * REV((LL)a[w] * d[f] % MOD)) % MOD;
a[f] = (a[f] - REV((LL)d[w] * d[f] % MOD) * (LL)REV(a[w])) % MOD;
}
}
}

int main() {
#ifdef DBG
freopen("11input.in", "r", stdin);
#endif
for (int i = 1; i < n; ++i) {
}
solve(1, 1);
int ans = (LL)b[1] * REV(MOD - a[1]) % MOD;
ans = (ans + MOD) % MOD;
cout<<ans<<endl;
return 0;
}


## 【BZOJ 3517】翻硬币

### 解题报告

1. 首先一个格子要么被翻一次，要么不被翻
2. 其次全部变白和全部变黑是互逆的，所以求出一个可以推出另一个。所以我们只考虑求全部变白的情况

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1009;

int n,ans,x[N],y[N],a[N][N];
char pat[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int main() {
for (int j=1;j<=n;j++) {
scanf("%s",pat+1);
for (int i=1;i<=n;i++) {
a[i][j] = pat[i] - '0';
x[i] ^= a[i][j];
y[j] ^= a[i][j];
}
}
for (int j=1;j<=n;j++) {
for (int i=1;i<=n;i++) {
ans += x[i] ^ y[j] ^ a[i][j];
}
}
printf("%d\n",min(ans, n * n - ans));
return 0;
}


## 【BZOJ 3569】DZY Loves Chinese II

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int M = 1000000+9;
const int MOD = 9999971;
const int SGZ = 40;

int vis[N],c[SGZ],cnt,bas[SGZ],sym[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void Add_Edge(int u, int v) {
static int T = 1;
}

void DFS1(int w, int f) {
vis[w] = 1;
for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
if (vis[to[i]]) {
int W = rand()*(rand()%MOD); val[i] ^= W; val[i^1] ^= W;
sym[w] ^= W; sym[to[i]] ^= W;
} else DFS1(to[i],w);
}
}

void DFS2(int w, int f) {
for (int i=head[w];i;i=nxt[i]) if (to[i] != f && !val[i])
DFS2(to[i], w), val[i] ^= sym[to[i]],
val[i^1] ^= sym[to[i]], sym[w] ^= sym[to[i]];
}

inline bool update(int w) {
for (int i=0,tmp=val[w];i<=30;i++) if (tmp&(1<<i)) {
if (!bas[i]) {bas[i] = tmp; return false;}
else {tmp ^= bas[i]; if (!tmp) return true;}
} return val[w]?false:true;
}

int main(){
DFS1(1,1); DFS2(1,1);
k = read(); tag = 1; memset(bas,0,sizeof(bas));
for (int i=1;i<=k;i++) c[i] = read()^cnt;
for (int i=1;i<=k && tag;i++) if (update(c[i]*2)) puts("Disconnected"), tag = 0;
if (tag) puts("Connected"), cnt++;
}
return 0;
}


1A辣，撒花~ ★,°:.☆(￣▽￣)/$:.°★ #include<iostream> #include<cstdio> #define abs(x) ((x)>0?(x):-(x)) using namespace std; const int MAXN = 51; const double EPS = 1e-8; int n; double G[MAXN][MAXN],rev=1; inline double Gauss(){ double ret = 1; for (int j=1,w=j;j<=n;w=++j) { for (int k=j+1;k<=n;k++) if (abs(G[j][k]) > abs(G[j][w])) w = k; if (w != j) {for (int i=1;i<=n;i++) swap(G[i][j],G[i][w]); ret *= -1;} for (int k=j+1;k<=n;k++) if (abs(G[j][k]) > EPS) { double t = G[j][k] / G[j][j]; for (int i=1;i<=n;i++) G[i][k] -= G[i][j]*t; } ret *= G[j][j]; } return ret; } int main(){ scanf("%d",&n); for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) scanf("%lf",&G[i][j]), rev *= i<j?1:1-G[i][j]; for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) G[i][j] = G[i][j]/(1-G[i][j])*-1; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i != j) G[i][i] -= G[j][i]; n--; printf("%.10lf\n",Gauss()*rev); return 0; }  ## 【BZOJ 4031】[HEOI2015] 小Z的房间 仍然是裸的矩阵树 #include<iostream> #include<iostream> #include<cstdio> #define LL long long using namespace std; const LL MAXN = 100; const LL MOD = 1000000000; LL G[MAXN][MAXN],n,m,num[MAXN][MAXN],cnt; char pat[MAXN]; inline int Gauss(){ for (LL j=1;j<=n;j++) for (LL i=1;i<=n;i++) G[i][j] = (G[i][j]%MOD + MOD) % MOD; LL ret = 1; for (LL j=1;j<=n;j++) { for (LL k=j+1;k<=n;k++) while (G[j][k]) { LL t = G[j][j] / G[j][k]; for (LL i=1;i<=n;i++) G[i][j] = ((G[i][j] - G[i][k]*t) % MOD + MOD) % MOD; for (LL i=1;i<=n;i++) swap(G[i][j], G[i][k]); ret *= -1; ret = (ret%MOD + MOD) % MOD; } ret = (G[j][j]*ret%MOD + MOD) % MOD; } return ret; } inline void AddEdge(LL u, LL v){ G[u][u]++; G[v][v]++; G[u][v]--; G[v][u]--; } int main(){ scanf("%d%d",&m,&n); for (LL j=1;j<=m;j++) { scanf("%s",pat+1); for (LL i=1;i<=n;i++) if (pat[i] == '.') { num[i][j] = ++cnt; if (num[i-1][j]) AddEdge(num[i][j],num[i-1][j]); if (num[i][j-1]) AddEdge(num[i][j],num[i][j-1]); } } n = cnt-1; printf("%d\n",Gauss()); return 0; }  ## 【BZOJ 2467】[中山市选2010] 生成树 传说中的矩阵树定理！其实搞一搞排列组合，然后O(1)输出就可以了QAQ 唯一值得一提的，就是高斯消元那里，因为有除，且模数不是质数（不一定有逆元） 所以只能使用类似辗转相除的方法，而不能搞LCM #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 400+9; const int MOD = 2007; int G[MAXN][MAXN],n; inline int read(){ char c=getchar(); int ret=0; while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') ret=ret*10+c-'0', c=getchar(); return ret; } inline int id(int i, int j){ if (i>n) i -= n; return (--i)*4+j; } inline void Add_Edge(int u, int v){ G[u][u]++; G[v][v]++; G[u][v]--; G[v][u]--; } inline void Build_Matrix(){ for (int i=1;i<=n;i++) { for (int j=1;j<=3;j++) Add_Edge(id(i,j),id(i,j+1)); Add_Edge(id(i,4),id(i+1,1)); Add_Edge(id(i,1),id(i+1,1)); }n *= 4; n--; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) G[i][j] = (G[i][j]%MOD + MOD) % MOD; } inline int Gauss(){ int ret = 1; for (int j=1,w=0;j<=n;j++) { for (int k=j+1;k<=n;k++) while (G[j][k]) { int t = G[j][j]?G[j][k] / G[j][j]:1; for (int i=1;i<=n;i++) G[i][k] = ((G[i][k] - G[i][j]*t) % MOD + MOD) % MOD; for (int i=1;i<=n;i++) swap(G[i][k], G[i][j]); ret *= -1; } ret = ret*G[j][j] % MOD; } return (ret + MOD) % MOD; } int main(){ for (int T=read();T;T--) { n = read(); memset(G,0,sizeof(G)); Build_Matrix(); printf("%d\n",Gauss()); } return 0; }  ## 【SOJ 1718】特工 考试的时候，看一眼数据范围 马上反应过来开是FFT，而且坚信是FFT 结果后来没想出来，考完试还被lcr给D了……… 结果最后一看，真™是FFT! 这个题，看一眼马上想到高斯消元 于是考试的时候就写了O(n^3)的高斯消元 后来讲题的时候，说到其实就是一个矩阵求逆，我很赞同 于是就来补O(n^3)的矩阵求逆啦！ #include<iostream> #include<cstdio> #define LL long long #define abs(x) ((x)<0?-(x):(x)) using namespace std; const int MAXN = 3000; const double EPS = 1e-8; int n; double mat[MAXN*2][MAXN],vout[MAXN],arr[MAXN]; inline LL read(){ char c=getchar(); LL ret=0,f=1; while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();} return ret*f; } #define lowbit(x) ((x)&-(x)) inline int bitcount(int w){ int ret = 0; while (w) ret++, w -= lowbit(w); return ret; } int LCA(int a, int b){ if (!b) return a; else return LCA(b,a%b); } inline void Get_Reverse_Matrix(){ for (int i=1,w;i<=n;i++) { for (w=i;w<=n;w++) if (mat[i+n][w]) break; for (int j=1;j<=n*2;j++) swap(mat[j][w], mat[j][i]); if (abs(mat[i+n][i]) < EPS) continue; else for (int j=1;j<=n;j++) if (abs(mat[i+n][j]) > EPS && j != i) { double tmp = mat[i+n][j]/mat[i+n][i]; for (int k=1;k<=n*2;k++) mat[k][j] -= mat[k][i]*tmp; } double tmp = mat[i+n][i]; for (int j=1;j<=n*2;j++) mat[j][i] /= tmp; } } int main(){ n = read(); for (int i=1;i<=n;i++) arr[i] = read(); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) mat[i+n][j] = (bitcount((i-1|j-1)^i-1)+1) % 2; for (int i=1;i<=n;i++) mat[i][i] = 1; Get_Reverse_Matrix(); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) vout[i] += mat[i][j]*arr[j]; for (int i=1;i<=n;i++) printf("%d ",(int)(vout[i]+EPS)); return 0; }  std是应用数据特点，把矩阵求逆给搞到了O(n^logn) 我就不写程序啦，反正SOJ代码可以看 —————————— UPD 2017.7.3 —————————— 仔细想一想，似乎按二进制分治也可以做？ ## 【算法笔记】高斯消元·基础应用 我真的是好菜啊！之前一直以为高斯消元只能用来求解n元一次方程组QAQ 赶快来补一点： Gauss advance ## 【BZOJ 1923】[Sdoi2010] 外星千足虫 今天在做高斯消元的专题。一看这题，欸,这不高斯消元求解异或方程组的板题吗？ (～￣▽￣)→))*￣▽￣*)o 于是写了一写，果然是板题。然而我想只有我这种纸张才会因为把结果输反了而wa了半天吧？QAQ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; const int MAXN = 1000+9; int n,m,mat[MAXN][MAXN],tmp[MAXN],cnt; char pat[MAXN],tag[MAXN]; inline int read(){ char c=getchar(); int buf=0,f=1; while (c<'0'||c>'9'){if(c='-')f=-1;c=getchar();} while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();} return buf*f; } inline bool update(){ for (int i=1;i<=n;i++) if (tmp[i]){ if (!tag[i]) { tag[i] = 1; cnt++; for (int j=1;j<=n+1;j++) mat[j][i] = tmp[j]; return cnt == n; } else for (int j=1;j<=n+1;j++) tmp[j] ^= mat[j][i]; } return cnt == n; } inline void output(int k){ printf("%d\n",k); for (int i=n;i;i--){ int ans = mat[n+1][i]; for (int j=i+1;j<=n;j++) ans ^= mat[j][i]; if (ans) tag[i] = 1; else tag[i] = 0; for (int j=i-1;j;j--) mat[i][j] *= ans; } for (int i=1;i<=n;i++) if (tag[i]) puts("?y7M#"); else puts("Earth"); } int main(){ scanf("%d%d",&n,&m); for (int k=1;k<=m;k++){ scanf("%s",pat+1); tmp[n+1]=read(); for (int i=1;i<=n;i++) tmp[i] = pat[i]-'0'; if (update()) output(k), exit(0); } puts("Cannot Determine\n"); return 0; }  PS：这份代码是在线的做法，看题解，貌似离线也是可以做的。 ## 【BZOJ 4269】再见Xor 这个题目，拿到以后，一脸懵逼啊QAQ，想拿BFS乱搞一搞，估计会T，结果还是可耻地看了题解 高斯消元求线性基QAQ，又没有学过QAQ，I well vegtable are (T_T) 其实也不难，每一个数的二进制看成方程组，然后上高斯消元。 求出线性基之后，全部^起来就是最大值，找一个最小的^一下就是次小值 #include<iostream> #include<cstdio> using namespace std; const int MAXN = 100000+9; int n,arr[MAXN],cnt; inline void Gauss(){ for (int k=31;k;k--){ int w = 1<<(k-1), pos; for (pos=cnt+1;pos<=n;pos++) if (arr[pos]&w) break; if (pos==n+1) continue; else { swap(arr[++cnt], arr[pos]); for (int i=1;i<=n;i++) if (i!=cnt && (arr[i]&w)) arr[i] ^= arr[cnt]; } } } int main(){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&arr[i]); Gauss(); int vout = 0; for (int i=1;i<=cnt;i++) vout ^= arr[i]; printf("%d ",vout); printf("%d\n",vout ^= arr[cnt]); return 0; }  好像还有一种方法，写法跟在线求解亦或方程组很像。 但感觉不如直接高斯消元优雅，且时间复杂度相同，所以就不贴代码啦！ ## 【BZOJ 1770】[Usaco2009 Nov] lights 燈 首先，这道题状态压缩的方法很显然，但是状态太多了，会T（然而黄学长说：折半搜索也可过QAQ） 然后开始想高斯消元。一开始不知道高斯消元能解异或方程组，于是想了两个多小时QAQ 然后去补了解异或方程组，一开始对自由元的理解有问题，正确的应该是： 自由元可以随便定，每一组不同的自由元可以导出一组方程的解 换一句话说，消完元之后，非自由元的未知数的解，并非最终解 #include<iostream> #include<cstdio> using namespace std; const int MAXN = 50; const int INF = 50; int n,m,vout=INF; int mat[MAXN][MAXN],tag[MAXN]; inline int read(){ char c=getchar(); int buf=0,f=1; while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();} return buf*f; } inline void Gauss(){ for (int k=1,w=k;k<n;w=++k){ for (int i=k+1;i<=n&&!mat[k][w];i++) if (mat[k][i]) w = i; for (int i=1;i<=n+1;i++) swap(mat[i][w],mat[i][k]); for (int i=k+1;i<=n;i++) if (mat[k][i]) for (int j=1;j<=n+1;j++) mat[j][i] ^= mat[j][k]; } } void DFS(int w, int cost){ if (cost >= vout) return; else if (!w) vout = min(vout, cost); else { if (mat[w][w]) { int t = mat[n+1][w]; for (int i=w+1;i<=n;i++) if (mat[i][w]) t ^= tag[i]; tag[w] = t; DFS(w-1, cost+(t?1:0)); } else { tag[w] = 1; DFS(w-1, cost+1); tag[w] = 0; DFS(w-1, cost); } } } int main(){ n = read(); m = read(); for (int i=1;i<=n;i++) mat[i][i] = 1, mat[n+1][i] = 1; for (int i=1,a,b;i<=m;i++){ a = read(); b = read(); mat[a][b] = mat[b][a] = 1; } Gauss(); DFS(n,0); printf("%d\n",vout); return 0; }  ## 【算法笔记】高斯消元 ## 【BZOJ 1013】[JSOI2008] 球形空间产生器sphere 高斯消元第一题！ 撒花！ *★,°*:.☆\(￣▽￣)/$:*.°★*
1A！ 撒花！ *★,°*:.☆\(￣▽￣)/\$:*.°★*

#include<iostream>
#include<cstdio>
#define fabs(x) ((x)<0?-(x):(x))
using namespace std;

const int MAXN = 20;

double mat[MAXN][MAXN];
int n;

inline void Gauss(){
for (int k=1;k<=n;k++){
int w = k;
for (int i=k+1;i<=n+1;i++) if (fabs(mat[k][w]) < fabs(mat[k][i])) w = i;
for (int i=1;i<=n+2;i++) swap(mat[i][k],mat[i][w]);
for (int i=k+1;i<=n+1;i++){
double t = mat[k][i]/mat[k][k];
for (int j=1;j<=n+2;j++)
mat[j][i] -= mat[j][k]*t;
}
}
for (int k=n+1;k;k--){
for (int i=n+1;i>k;i--) mat[n+2][k] -= mat[i][k]*mat[n+2][i];
mat[n+2][k] /= mat[k][k];
}
}

int main(){
scanf("%d",&n);
for (int j=1;j<=n+1;j++){
for (int i=1;i<=n;i++)
scanf("%lf",&mat[i][j]),
mat[n+2][j] -= mat[i][j]*mat[i][j],
mat[i][j] *= -2.0;
mat[n+1][j] = 1;
}
Gauss();
for (int i=1;i<n;i++) printf("%.3lf ",mat[n+2][i]);
printf("%.3lf",mat[n+2][n]);
return 0;
}