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


## 【SOJ 1718】特工

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

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(){
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)

—————————— UPD 2017.7.3 ——————————

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

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

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++){
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

#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 燈

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

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(){
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++){
mat[a][b] = mat[b][a] = 1;
}
Gauss();
DFS(n,0);
printf("%d\n",vout);
return 0;
}


## 【BZOJ 1013】[JSOI2008] 球形空间产生器sphere

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