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

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|$

【BZOJ 3811】玛里苟斯

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3811
神犇题解Ⅰ:https://blog.sengxian.com/solutions/bzoj-3811
神犇题解Ⅱ:http://yyy.is-programmer.com/posts/200623.html

解题报告

这题这么神,我们来分情况讨论:

1. $k = 1$

这就是一般的期望题。因为期望的线性,所以我们在二进制位下每一位分开考虑:

如果这一位上每一个数都是$0$,那么贡献肯定为$0$
如果有一个数为不为$0$那么我们有贡献的概率为$\frac{1}{2}$

证明的话,可以设$f_{1,0/1}$为考虑到第i个数,异或起来为0/1的概率
写出$DP$式子可以很轻松地发现这俩总是对半分,Q.E.D

于是我们直接把所有数$or$起来,然后除二输出即可
时间复杂度:$O(n)$

2. $k = 2$

这不是一般的期望题了,不是线性的,不能直接加 /(ㄒoㄒ)/~~
但我们发现某一个异或和为$(b_mb_{m-1} \cdots b_0)_{bin}$的话
其中第$i$位与第$j$位的贡献为$b_i \cdot b_j \cdot 2^{i+j}$

因为$b_i$与$b_j$是线性的,所以我们就可以枚举$i,j$然后直接加起来了!
根据$k = 1$时得到的结论,不难发现:

如果这两位独立则贡献的概率为$\frac{1}{4}$
如果这两位不独立,那么贡献的概率为$\frac{1}{2}$
如果这两位中有至少一位从没出现过,那么概率为$0$

于是我们暴力枚举$i,j$直接算贡献就可以了
时间复杂度:$O(62n + 62^2)$

3. $k \ge 3$

我们先来看一个结论:若$E(x^k) < 2^{63}$,初始集合中的每个数小于$2^{22}$
证明的话,sengxian教我的:

不妨用反证法,考虑答案为:$\sum\limits_{s \in \{1,2,\cdots,n\}}{\frac{v^3}{2^n}}$
假如有一个数的二进制下第$22$位出现了$1$,有$2^{n-1}$个集合异或起来后这一位为$1$
所以这一位的贡献就已经为$2^{63}$了,又因为答案小于$2^{63}$,矛盾,故不可能,Q.E.D

所以我们可以求出这些数的线性基,然后暴力枚举线性基的子集
根据$k = 1$时的人生经验,我们又可以得到每一种情况出现的概率相等
于是我们暴力枚举,然后暴力算贡献就可以了
时间复杂度:$O(21n + 2^{21})$

【BZOJ 4644】经典傻逼题

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4644
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5734792.html
神犇题解Ⅱ:http://blog.csdn.net/neither_nor/article/details/53997223

解题报告

首先,如果我们把边权异或到点上
原问题就可以转化为:选一些点,使NIM和最大
于是就是线性基的锅了,时间复杂度:$ \frac{{nm{L^2}}}{{{\rm{64}}}}$

然后我们发现这么做会T
于是对时间进行分治
这样的话,复杂度优化到:$ \frac{{m\log m{L^2}}}{{{\rm{64}}}}$

然后Claris还说可以用Method of Four Russians
这样话,复杂度就变成了:$ \frac{{m\log m{L^2}}}{{{\rm{64logL}}}}$

【Codeforces 662A】Gambling Nim

题目传送门:http://codeforces.com/problemset/problem/662/A
官方题解:http://codeforces.com/blog/entry/44408

说人话就是亦或和为0的概率是多少
考虑把ai全部亦或起来为sum的话
那就是求{ai^bi}有多少个子集亦或和为sum
这样的话,岂不就是线性基的拿手好戏了?

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

const int N = 500000+9;
const int SGZ = 61+9;

int n,cnt;
LL a[N],b[N],bas[SGZ],sum; 

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;
}

inline bool insert(LL w) {
	for (int i=61;~i;i--) if (w&(1LL<<i)) {
		if (bas[i]) {
			w ^= bas[i];
		} else {
			bas[i] = w;
			return true;
		}
	}	
	return false;
}

inline LL pow(LL w, int t) {
	LL ret = 1;
	while (t) {
		if (t & 1) ret *= w;
		w *= w; t >>= 1;
	}
	return ret;
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) {
		a[i] = read();
		b[i] = read();
		sum ^= a[i];
		cnt += insert(a[i] ^ b[i]);
	}
	if (!cnt && !sum) {
		puts("0/1");
	} else if (insert(sum)) {
		puts("1/1");
	} else {
		printf("%I64d/%I64d\n",pow(2LL,cnt)-1,pow(2LL,cnt));
	}
	return 0;
}

【BZOJ 2844】albus就是要第一个出场

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2844
数据生成器:http://paste.ubuntu.com/23312434/

话说这个题啊!还是挺有意思哒!
有一个结论:如果相同的数要计入答案的话,那每种答案出现了2^(n-线性基的数量)
证明:既然都为0了,那么取不取都不影响答案,于是可以随便搞一搞

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

const int MOD = 10086;
const int N = 100000+9;
const int SGZ = 30+9;

int n,m,arr[N],bas[SGZ],cnt,vout;

inline int read(){
	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 bool insert(int w) {
	for (int i=30;~i;i--) if (w&(1<<i)) {
		if (bas[i]) {
			w ^= bas[i];
		} else {
			bas[i] = w;
			return true;
		}
	}
	return false;
}

inline int pow(int w , int t) {
	int ret = 1;
	while (t) {
		if (t&1) ret = (LL)ret * w % MOD;
		w = (LL)w * w % MOD; t >>= 1;
	}
	return ret;
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) {
		arr[i] = read();
		cnt += insert(arr[i]);
	}
	m = read();
	for (int i=30,tmp=pow(2,n-cnt);~i;i--) if (bas[i]) {
		cnt--;
		if (m&(1<<i)) {
			vout += tmp * (1LL<<cnt) % MOD;
			vout %= MOD;
		}
	}
	printf("%d\n",(vout+1)%MOD);
	return 0;
}

【HDU 3949】XOR

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3949

这个题ihopenot都说是水题了,那我也扔一份代码就跑吧!
想看题解的戳这里:http://acm.hdu.edu.cn/showproblem.php?pid=3949

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

const int N = 10000+9;

int n,bas[70],cnt,m;
LL arr[N],l,r,STA,tag;

inline void insert(LL &w, int num) {
	for (int i=61;~i;i--) if (w & (1LL<<i)) {
		if (bas[i]) {
			w ^= arr[bas[i]];
		} else {
			bas[i] = num;
			break;
		}
	}
	if (!w) tag = 1;
}

inline LL cal(LL w) {
	LL ret = 0;
	for (int i=0,cur=0;i<cnt;i++) {
		while (!bas[cur]) cur++;
		if (w&(1LL<<i)) ret ^= arr[bas[cur]];
		cur++;
	}
	return ret;
}

inline int read(){
	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 T=read(),tot=1;T;T--,tot++) {
		printf("Case #%d:\n",tot);
		memset(bas,0,sizeof(bas));
		memset(arr,0,sizeof(arr));
		cnt = tag = 0; 
	 
		n = read();
		for (int i=1;i<=n;i++) {
			cin>>arr[i];
			insert(arr[i],i);
		}	
		
		for (int i=0;i<=61;i++) if (bas[i]) {
			++cnt;
			for (int j=i+1;j<=61;j++) if (bas[j]) {
				if (arr[bas[j]] & (1LL<<i)) {
					arr[bas[j]] ^= arr[bas[i]];
				}
			}
		}	
		
		m = read(); STA = (1LL<<cnt) - 1;
		for (int i=1;i<=m;i++) {
			LL tmp; scanf("%I64d",&tmp); tmp -= tag;
			if (STA < tmp) puts("-1");
			else printf("%I64d\n",cal(tmp));
		}
	}
	return 0;
}

【BZOJ 3569】DZY Loves Chinese II

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3569
数据生成器:http://paste.ubuntu.com/23227745/

这个题,是我到目前为止,做过的最妙的一道题
没有之一

给每一个非树边搞一个权值
然后亦或到它所覆盖的每一条树边上去
考虑不联通的情况:删掉了一条树边和所有覆盖他的非树边
及一个子集的亦或和为0
于是像求线性基一样,判一下是否线性无关即可

#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 head[N],nxt[M],to[M],n,m,q,val[M];
int vis[N],c[SGZ],cnt,bas[SGZ],sym[N];

inline int read(){
	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;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; 
	to[++T] = u; nxt[T] = head[v]; head[v] = T; 
}

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(){
	srand(9999971); n = read(); m = read(); 
	for (int i=1;i<=m;i++) Add_Edge(read(),read());
	DFS1(1,1); DFS2(1,1);
	for (int q=read(),k,tag;q;q--) {
		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;
}

【BZOJ 4004】[JLOI2015] 装备购买

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4004
数据生成器:http://paste.ubuntu.com/23209631/

这个题目,看一眼,就是要求一组花费最小的线性基
第一次写,写的整数高斯消元,发现爆了long long
第二次改成double,发现精度不够
第三次,搞成整数高斯消元+MOD,遂过之
想一想,如果不用线性基,只是求一组线性基的话,MOD确实没影响

另外网上用double写的标程全部被叉掉了,不要问我是怎么知道的 qwq
1248545547

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 500+9;
const int MOD = 1000000007;
 
int n,m,f[N][N],bas[N],cost[N],num[N],cnt,vout; 
 
inline int read(){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 bool cmp(const int a, const int b) {return cost[a] < cost[b];}
 
inline void update(int w) {
    for (int i=1;i<=m;i++) if (f[w][i]) {
        if (!bas[i]) {bas[i] = w, cnt++, vout += cost[w]; break;}
        else {
        	int t2 = f[bas[i]][i], t1 = f[w][i];
            for (int j=1;j<=m;j++) f[w][j] = ((LL)f[w][j]*t2 - (LL)f[bas[i]][j]*t1) % MOD;
        }
    }
}
 
int main(){
    n = read(); m = read();
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) f[i][j] = read();
    for (int i=1;i<=n;i++) cost[i] = read(), num[i] = i;
    sort(num+1,num+1+n,cmp);
    for (int i=1;i<=n;i++) update(num[i]);
    printf("%d %d\n",cnt,vout);
    return 0;
}