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

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)

相关链接

题目传送门:http://codeforces.com/contest/802/problem/L
官方题解:http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf

解题报告

这题告诉我们,这类题可以高斯消元做
裸做是$O(n^3)$的,非常不科学
这题我们发掘性质,如果从叶子开始一层一层往上消,高斯消元那一块可以做到$O(n)$
然后再算上逆元的话,总的时间复杂度:$O(n \log n)$

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

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

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
	n = read();
	for (int i = 1; i < n; ++i) {
		int u = read(), v = read();
		AddEdge(u + 1, v + 1, read());
	}
	solve(1, 1);
	int ans = (LL)b[1] * REV(MOD - a[1]) % MOD;
	ans = (ans + MOD) % MOD;
	cout<<ans<<endl;
	return 0;
}

【BZOJ 3517】翻硬币

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3517
神犇题解Ⅰ:http://blog.csdn.net/lych_cys/article/details/50363106
神犇题解Ⅱ:http://foreseeable97.logdown.com/posts/193171-bzoj3517-coins

解题报告

一道非常妙妙的题目啊!虽然没做出来 QwQ

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

我们考虑设$b_{i,j}$表示最终对没对$(i,j)$这个格子进行操作
于是我们可以得到$n^2$个方程,因为只有$n^2$个变量
所以我们可以用高斯消元在$O(n^3)$的时间复杂度内求解

但我我们发现题目中提到的$n$为偶数这个条件并没有用到
现在考虑优化高斯消元:

设$a_{i,j}$为这个格子的原始状态
设$xb_i$表示第$i$行所有$b_{i,j}$异或起来,$xa_i$表示第$i$行所有$a_{i,j}$异或起来
设$yb_i$表示第$i$列所有$b_{i,j}$异或起来,$ya_i$表示第$i$列所有$a_{i,j}$异或起来
于是我们可以得到$b_{i,j} \oplus xb_j \oplus yb_i = a_{i,j}$,设为一号方程
考虑我们求$b_{i,j}$,那么我们把所有第$j$行和第$i$列的方格对应的一号方程异或起来
之后我们发现因为$n$为偶数,所以等式变为$b_{i,j}=ya_i \oplus xa_j \oplus a_{i,j}$

然后我们惊讶地发现问题已经解决了?
第一次手动解异或方程组,感觉非常玄妙啊!

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

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() {
	n = read();
	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

题目传送门: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 3534】[Sdoi2014] 重建

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3534
矩阵树定理基础:https://oi.qizy.tech/?p=717

解题报告

说明:以下使用变量名,均同上面的矩阵树定理基础

这个题目直接看矩阵树定理肯定是没有头绪的。
但如果我们看矩阵树定理推导过程中的这个式子:\(\partial = {\sum\limits_{G’isG’sSubgraph} {\det (M(G’))} ^2}\)
不难发现我们可以这样算贡献:\(\partial = {\sum\limits_{G’isG’sSubgraph} {\det (M(G’))} ^2} \cdot P\)
其中p为,在生成树中的点的出现概率和不在生成树中的点的不出现的概率
于是现在的问题就是如何把概率给搞进去。不难发现如果我们把每条边的概率乘到M(G’)中,刚好可以满足树边那部分的概率,但非树边那部分还满足不了
于是再来考虑非树边,凑一凑发现:我们把p/(1-p)乘进去,全局再乘以(1-p)就可以满足条件了
所以L=M(G)*M(G)^T*p/(1-p)

所以直接把矩阵树定理的邻接矩阵的0/1变成概率就可以了
或者,更直接的理解:矩阵树定理里面的邻接矩阵可以推广到连边的个数,那应该可以推广到实数域,这样的话就可以对应概率了?

Code

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的房间

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4031

仍然是裸的矩阵树

#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] 生成树

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2467

传说中的矩阵树定理!其实搞一搞排列组合,然后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】特工

题目传送门:https://oi.qizy.tech/wp-content/uploads/2016/08/216378216437812.png
题解传送门:https://oi.qizy.tech/wp-content/uploads/2016/08/123478756.png
OJ传送门:http://oi.cdshishi.net:8080/Problem/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 ——————————
仔细想一想,似乎按二进制分治也可以做?

【BZOJ 1923】[Sdoi2010] 外星千足虫

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

今天在做高斯消元的专题。一看这题,欸,这不高斯消元求解异或方程组的板题吗? (~ ̄▽ ̄)→))* ̄▽ ̄*)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:这份代码是在线的做法,看题解,貌似离线也是可以做的。