BZOJ2005能量采集
本来打算放到“数学相关”里面，但是太影响排版了，而且这种神题还是单独放比较好。
一共有四种做法：
首先题目可以化成一个2*ΣΣgcd(i,j)-nm是显然的，至于前面的求法听说有好几种做法
做法一：From KZF：
首先线性筛出欧拉函数，然后直接求解，时间也是线性的。
做法二：From 小狗：
对于左式可以将其化成
然后[n/x][m/x]可以分成O(sqrt(n)+sqrt(m))段，可以预处理u(x)前缀和在根号时间内求解
所以代入kzf的第一行的式子中O(nsqrt(n))级别的。
做法三：From wulala：
要求每个数是多少个数对的gcd，可以用类似容斥但更SB的方法：首先最多这个数可以作为(n/i)*(m/i)个数对的公因数，然后减去所有gcd是i的倍数的数对，所以时间复杂度就是Σn/i，也就是调和级数，O(n log n)
做法四：From KZF：
可以先预处理出n^(2/3)的F(n)，然后将KZF最后面的那个式子分成根号块，每块求值据说是O(n^(1/6))，然后复杂度就喜闻乐见O(n^(2/3))
神奇的是，上面四种做法复杂度都不一样= =，但是水B的数据范围应该是都能让过的。
最近几次考试题
从最近几次的考试题里面放几道上来好了
最近的NOIP赛的题目比较水，但是我为毛总是不想写对拍= =，所以一直没拉开分差，也没有AK过。
唯一在考场上面没想出来的是一道搜索题：就是要搞一个多维背包。考试的时候就觉得不可做，于是觉得应该是要搜索，但是总感觉维数大小是50会挂，而且这种题目让人感觉贪心可以骗些分的样子，我这种逗了一B的代码能力也就随便写了个贪心。最后题解里面说是要加一堆的优化：主要是物品的大小有很多重复的，这些就需要决策单调性，而且还有个边界判断后面还有没有解。虽然感觉还是很不科学，但是确实是能过的= =
补：10号也考了一场。duyege差点AK但是第三题我并没有想出来，想想当时的状态虽然一直在想但是很快就走神了，而且当时我也不知为何没有那么强的做出这道题的欲望。（我为毛这么萎啊！）后来看式子的时候也是感觉得了智商癌，一直没看懂。
题意：给定数组B，第i位代表A数组前i位有多少个小于等于i的数，求有多少个满足条件的A数组，并且A数组是一个1-n的排列。
题解：“很简单啊！”。当b[i]-b[i-1]=1时说明要不就是第i位有一个1-i之间的数，要不就是第1-i-1位有一个i，所以答案乘以2*(i-1-b[i-1])+1；当b[i]-b[i-1]=2时说明第i位有一个1-i-1之间的数，并且第1-i-1位有一个i，所以答案乘以(i-1-b[i-1])^2。回想我的思路我一直觉得如果设前i位有多少种方案是会有问题的，于是一直没往这方面想，现在想想真是SB。
还有一些NOI的模拟赛，有的题目如果放到NOIP的模拟赛中我是可以想出来的，但是我总是觉得这些题会很神，所以就没认真去想。而且这两天的状态是真心萎废，甚至考试中可以做到一道题调一个上午。感觉还是心态问题，考的人里面还有某爷、某司机什么的，总觉得自己完全不可能在这些人中间考好，完全没有进入考试状态，而且总是很容易就弃疗了。但是实力不会等于成绩啊，我有几次还是有考好的机会的，而且我完全不能是因为为了考好而考试，有的题目做起来本身就应该是愉快的啊。
不多说了还是放题目吧：就是有一个数列的第一项v0给出来了，然后有s1项每一项是前一项+1，还有s2项每一项是前一位的2倍，然后后面就是ai=ai-1*……ai-k，k<=101,N<=1e9，要求数列第N项对1e8+7取模。
题解：这东西肯定没办法直接搞，所以要想办法让递推式能用矩阵乘法优化。所以想到用让ai取log然后就可以用矩阵乘法搞了，但是由于取过了log所以没办法取模，肯定会有太大了，而且还会有精度问题，算它的幂，所以要想办法尽量不用log。而且矩阵乘法的递推矩阵是没有实数的，所以我们没必要取log，只要将递推矩阵快速幂之后的最后一次矩阵乘法化乘法为幂运算就可以了，由于最后一次是幂运算，而且用于取模的数是素数，所以在矩阵快速幂的时候就可以用费马小定理模P-1。感觉就是一堆东西杂在一起，并不算难。然后被细节坑到了30分，体会到了不写对拍的快感。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 205
#define M 100000007
#define eps 1e-9
#define ll long long
struct Matrix
{
ll a[N][N];
} emp,E,ans;
ll v0,s1,s2,m,n,t;
inline ll Quick_mi(ll x,ll y)
{
ll z=1;
while (y)
{
if (y&1) z=(z*x)%M;
x=(x*x)%M;
y/=2;
}
return z;
}
inline Matrix* Multi(Matrix *x,Matrix *y)
{
Matrix *z=(Matrix*)(malloc(sizeof(Matrix)));
*z=emp;
for (int i=1;i<=m;i++)
for (int j=1;j<=m;j++)
for (int k=1;k<=m;k++)
z->a[i][k]+=x->a[i][j]*y->a[j][k];
for (int i=1;i<=m;i++)
for (int j=1;j<=m;j++)
z->a[i][j]%=M-1;
return z;
}
inline Matrix* Quick_mi(Matrix *x,ll y)
{
Matrix *z;
z=(Matrix*)(malloc(sizeof(Matrix)));
*z=E;
while (y)
{
if (y&1) z=Multi(z,x);
x=Multi(x,x);
y/=2;
}
return z;
}
int main()
{
int i,j;Matrix q,w,*e;ll k,l;double o,p;
scanf("%d",&t);
while (t--)
{
memset(emp.a,0,sizeof(emp.a));memset(E.a,0,sizeof(E.a));
memset(q.a,0,sizeof(q.a));memset(ans.a,0,sizeof(ans.a));
memset(w.a,0,sizeof(w.a));
scanf("%d%d%d%d%d",&v0,&s1,&s2,&m,&n);
for (i=1;i<=m;i++)
E.a[i][i]=1;
for (i=1;i<=m;i++)
w.a[i][i-1]=w.a[i][m]=1;
for (i=1;i<=m;i++)
for (j=1;j<=m;j++)
ans.a[i][j]=1;
if (n<=s1+1)
{cout <<v0+(n-1)<<endl;continue;}
k=v0+s1;
if (n<=s2+s1+1)
{cout <<(k*Quick_mi(2,n-s1-1))%M<<endl;continue;}
if (m==s2+s1+1)
{
q.a[1][1]=v0;
for (i=s1+1;i>=2;i--)
q.a[1][i]=k--;
k+=s1;
for (i=m-s2+1;i<=m;i++)
q.a[1][i]=(k=(k*2)%M);
}else
if (m<=s2)
{
k=(k*Quick_mi(2,s2-m))%M;
for (i=1;i<=m;i++)
k=(k*2)%M,q.a[1][i]=k;
}else
{
for (i=m-s2;i>=1;i--)
q.a[1][i]=k--;
k+=m-s2;
for (i=m-s2+1;i<=m;i++)
q.a[1][i]=(k=(k << 1)%M);
}
e=Quick_mi(&w,n-s2-s1-1);
for (i=1;i<=m;i++)
for (j=1;j<=m;j++)
ans.a[1][j]=(ans.a[1][j]*Quick_mi(q.a[1][i],e->a[i][j]))%M;
printf("%d\n",(int)(ans.a[1][m]%M));
}
return 0;
}
有道题由于第一题看错题一直觉得是FFT于是试着在考场上搞出FFT，所以没怎么想第三题，后来发现确实不难= =。
题意：有一个字符串，一开始只有大写字母，然后可以往中间加下划线、交换任意两个字符或者删字符。要求最终串的长度为N，任意两个相同的字母之间有至少k个比它大的字符（设下划线的ASCII码最大）。
题解：可以字母从小到大搞，设a[i][j]为搞到第i个字符还有j个空位的方案数，对于那个两个相同字母之间的限制可以直接组合数搞。但是N最大可能有1Y，原串最大2K+，所以只要把j换成用了j个位置，然后就可以直接DP了。（然而我还并没有写= =）
还有道题：要将1-n分成两个集合，使得不存在不同的三个数x、y、z同时存在一个集合里面使得xy=z。n<=10w
题解：考场上面就觉得很神，于是照着它给的50分线也就是n<=50交了张表，就没想太多了= =。后来题解里面说n>96时答案就是0了，于是应该交一张96的表就可以A了= =。出题人sxbk！
最近做了两套汪文潇和镇海的卷子，都考爆了，两天不仅成绩不好，而且还被自己wgy和Fadeness虐了（虽然两个都是因为数据水A的题），跟前几次集训状态相比感觉在考场上面能想出正解了（然并卵），然而还是会考挂，一是思路不清晰，很容易想错或者看错题，所以只写对了暴力完全就没有任何优势，二虽然这两场不明显，但是感觉还是代码能力弱了。除了能力问题就是整个人真的状态很萎，还是很容易弃疗，对自己还是太不自信了，有的时候真的觉得自己太弱了。还有就是最近实在是太摆了，说好的刷题量完全没上去。话说我这么萎我还能撑到什么时候？
题意：有两个长度为n的序列a、b，序列里面的每个数在1~n之间，求有多少个长度为n的排列c，使得a[c[i]]=c[b[i]]，并输出其中一个方案
题解：第一次感觉自己的思维还不是那么没救，虽然在考试最后30分钟想出来也没什么用= =。想了个把小时= =，首先看到问题感觉是置换群相关，或许会是polya计数法的奇怪运用？一直在画映射的图，感觉记不起来有什么相似的模型，想了很久差点就要弃(shui)疗(zhao)了，然后脑洞了一下试了下将这个画成第二题的环套树森林，就是对于每个i，i的父亲是a[i]，然后成了一个环套树，b也这么建，然后看图就可以很容易知道题目的要求变成了求a和b的映射使得两个森林同构。然后就可以有很多乱搞了。首先判断两个森林是不是同构的，这个总感觉最近碰到过一个相似的题目，但是那个是好像是用DP的= =，然而我感觉只会用hash的搞法。然后计算方案肯定是第i层的映射第i层的，尝试从第一层搞到最后一层，那么子树同构的结点肯定可以相互映射，那么如果a中有i个节点的子树同构，就可以把答案乘以i!，像这样子全部乘起来就是了= =那么环套树感觉又特殊一点，判断的时候用最小表示法，算的时候也是求出最小循环子串，貌似kmp相关？然后其他地方都差不多了吧，貌似求一组方案可以随便搞的样子。。。
题意：给定大小为20W的环套树森林，然后有20W组总共100W的染色，每组染色独立，染色是将一些点染成白点一些染成黑点，求每一组中“对于所有黑点是白点的祖先的二元组中黑点到白点路径上的边编号最大值”的最小值。
题解：题目是水题，但是艹蛋的题目大意（其实就是我语文不好啊！）坑了我两次，第一次naive我不记得是怎么理解的了，我竟然还写完了直到被样例卡住才反应过来，然后第二次我以为是求所有二元组中白点的父亲编号的最小值，然后一直在想线性做法= =（之前碰到过明明复杂度是n log n，而且n是100w的然后被卡掉了= =，这种情况后面也碰到过几次，完全搞怕了），最后还是写了线段树，如果理解对题意的话就应该还要加一个主席树查询最大值。如果根部有环的话就是缩点然后乱搞就是了（貌似这样还要加一棵主席树= =）总而言之如果没理解错题意感觉不难。
数学相关
最近把kzf、小狗的课件什么的都过了一下，复习了组合数学，看了两篇论文，然后准备开推鸿少给的题和其他的一些题。
乱入：话说罗大神终于要回来虐我们了真是TATQAQ2333！
BZOJ1968约数研究：只要统计每个数是多少个数的约数即可
BZOJ1211树的计数：直接搞prufer数列，因为每个节点在数列中出现di-1次。然后直接暴力枚举prufer数列个数，但是要注意特判无解。
BZOJ1005明明的烦恼：之前看的时候觉得好神，其实跟上题是一样的，直接搞prufer数列，反正已知的结点必须在数列中di-1次，然后其余部分就随便了，组合数搞搞就出来了。
BZOJ1485有趣的数列：《组合数学》原题，直接上Catalan数列。话说算答案的时候要加特技，先线性筛一下，统计出每个数的最小质因数是哪个，然后将每个合数的系数下传，细节看代码。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
#define N 2000050
ll ans=1,n,m;
int c[N],p[N],ss=0,v[N];
inline ll Quick_mi(ll x,int y)
{
ll z=1;
while (y)
{
if (y&1) z=(z*x)%m;
x=(x*x)%m;
y/=2;
}
return z;
}
int main()
{
int i,j,k,l,q,w,e;
memset(c,0,sizeof(c));memset(v,0,sizeof(v));
memset(p,0,sizeof(p));
scanf("%d%d",&n,&m);
for (i=2;i<=n << 1;i++)
{
if (!v[i]) p[++ss]=i;
for (j=1;j<=ss;j++)
{
if (p[j]*i>n << 1) break;
v[p[j]*i]=p[j];
if (i%p[j]==0) break;
}
}
for (i=2;i<=n;i++) c[i]=-1;
for (i=n+2;i<=n << 1;i++) c[i]=1;
for (i=n << 1;i>=2;i--)
if (!v[i])
ans=ans*Quick_mi(i,c[i])%m;else
c[v[i]]+=c[i],c[i/v[i]]+=c[i];
printf("%lld\n",ans);
return 0;
}
BZOJ2425计数：这题只要从高位到低位一路扫过去就可以了，因为上界对答案是造成了影响的，所以只要对于每一位统计这一位不取上界并且前面几位都取了上界的答案数，只要记下还有哪些数字没用过，这个用组合数很容易统计。
BZOJ2431逆序对数列：很容易可以得到递推式，设ai,j为i个数j个逆序对的数列，个数就是上一行的j-i+1~j个数的和，这个可以通过ai,j-1消西格玛，然后n和m只有1000，所以O(nm)的递推可以直接出答案。
BZOJ2729排队：完全就是《组合数学》第二章的题，随便算算。
BZOJ2751容易题：设si为前i个数的数列的乘积和，则si+1=si*第i个数的可取的数的和，但是由于n太大了，所以可以对于有限制的数单独算，其余的数直接快速幂统计。
BZOJ3209花神的数论题：水过，也是从高位到低位统计出现1的次数为i的数的个数，最后快速幂乘起来
BZOJ2705Longge的问题：发现就是要我们求Σ(i|n) i*φ(n/i)，然后枚举n的因子i，算φ甚至sqrt(n)都不用，因为n已经因式分解过了，所以直接枚举n的因子算φ。
BZOJ2956模积和：看起来好神，然后随手点开记录发现了第一版的HJWJBSR在3月的记录，顿时吓傻，然后马上想起来当时这题是LAccelerator叫我做的，记得当时想了好久，还被罗大神D了。于是想了想感觉确实不算难：把模化去变成ΣΣ(n-i*[n/i])*(m-j*[m/j])=(nm)^2-n^2Σi[m/i]-m^2Σi[n/i]+ΣΣij[n/i][m/j]，第二项第三项可以通过分块计算n/i然后用前缀和去乘最后加起来就可以了，话说第四项就是第二项第三项的积啊。补：话说好像还有i!=j这个限制于是减去就好了，但是这样好像还是要分块搞，还要用到什么平方和公式的= =真是hentai
BZOJ2242计算器：第一问快速幂，第二问直接移项所以还是快速幂（我还想什么扩展欧几里得真是羞耻），第三问BSGS。
BZOJ2173整数的lqp拆分：直接打表找规律= =
BZOJ2301Problem b：化简式子，线性筛出莫比乌斯函数前缀和，然后貌似就可以分块做了。
BZOJ1004Cards：直接套Burnside引理，DP求中间值。
BZOJ2463谁能赢呢？：可以发现棋盘可以多米诺骨牌覆盖的时候就先手必胜，否则后手必胜。因为先手总要从多米诺骨牌一端走到另一端。所以直接判奇偶。
BZOJ2006超级钢琴
单独放题解了= =
题意：有n个整数，然后从中间选出k段不同的、长度在[L,R]之间的区间，使得所有区间的区间和加起来最大。n,k<=50w
题解：思路对于我这种想不到的弱逼还是蛮屌的。首先看上去很有堆的感觉，但是明显把不能枚举状态，于是考虑如何优化。。那可以维护对于每个点x以它为左端点的三元组[L,R,w]，表示从x到w的区间和是右端点在L到R里面最大的，那么就可以每次把n个左端点里面最大的加进来，然后分成[L,w-1,w1]以及[w+1,R,w2]加入堆中。而求w就是先搞出一个前缀和s[i]，然后询问L到R的s[i]最大值，即RMQ问题，我用了倍增解，然后复杂度就是差不多O(nlog^2 n)。。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define N 500050
#define M 30
#define ll long long
#define INF 0x7f7f7f7f
struct Point
{
int le,ri,bg,wz;ll t;
bool operator < (const Point &x) const
{
return t>x.t||(t==x.t&&le>x.t)||(t==x.t&&le==x.le&&bg>x.bg);
}
};
multiset <Point> li;
set <Point> :: iterator it;
int n,m,st[N][M],L,R;
ll s[N],ans=0;
inline int Read()
{
int x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
int Find(int x,int y,int z)
{
if (x>y) return -INF;
if (y-x+1==(1 << z)) return st[x][z];
if (y-x+1<(1 << z)) return Find(x,y,z-1);
int i=Find(x+(1 << z),y,z-1);
return s[i]>s[st[x][z]]?i:st[x][z];
}
inline Point Make(int x,int y,int z)
{
Point i;
i.bg=x;i.le=y;i.ri=z;i.wz=Find(y,z,20);
i.t=s[i.wz]-s[i.bg-1];
return i;
}
int main()
{
int i,j,k,l;Point q,w,e;
memset(s,0,sizeof(s));memset(st,0,sizeof(st));
scanf("%d%d%d%d",&n,&m,&L,&R);
for (i=1;i<=n;i++)
s[i]=s[i-1]+Read(),st[i][0]=i;
for (i=1;(1 << i)<=n;i++)
for (j=1;j<=n-(1 << i)+1;j++)
st[j][i]=s[st[j+(1 << (i-1))][i-1]]>s[st[j][i-1]]?
st[j+(1 << (i-1))][i-1]:st[j][i-1];
for (i=1;i<=n-L+1;i++)
li.insert(Make(i,i+L-1,min(i+R-1,n)));
while (m--)
{
it=li.begin();q=*it;li.erase(it);ans+=q.t;
if (q.wz!=q.le)
li.insert(Make(q.bg,q.le,q.wz-1));
if (q.wz!=q.ri)
li.insert(Make(q.bg,q.wz+1,q.ri));
}
cout <<ans<<endl;
return 0;
}
高斯消元
Orzei了hzwer的代码，还算是学了高斯消元吧。。。然后开始水了几道题。感觉高斯消元的题目有的思路还是很屌的。。。
BZOJ1013球形空间产生器：直接根据每个点到球心的距离相等列方程，然后直接Gauss()
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 105
#define eps 1e-6
#define INF 0x7f7f7f7f
double a[N][N],f[N];
int n;
inline double sqr(double x)
{
return x*x;
}
void Gauss()
{
int now=1,i,j,k;double t;
for (i=1;i<=n;i++)
{
j=now;while (fabs(a[j][i])<eps&&j<=n) j++;
if (j>n) continue;
for (k=i;k<=n+1;k++) swap(a[now][k],a[j][k]);
for (k=i+1;k<=n+1;k++) a[now][k]/=a[now][i];
a[now][i]=1;
for (j=1;j<=n;j++)
if (j!=i)
{
t=a[j][i];
for (k=1;k<=n+1;k++)
a[j][k]-=t*a[now][k];
}
now++;
}
return;
}
int main()
{
int i,j,q,w,e;double k,l;
freopen("input.txt","r",stdin);
memset(f,0,sizeof(f));memset(a,0,sizeof(a));
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%lf",&f[i]);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
scanf("%lf",&k);
a[i][j]=2*(k-f[j]);a[i][n+1]+=sqr(k)-sqr(f[j]);
}
Gauss();
for (i=1;i<=n-1;i++)
printf("%.3lf ",a[i][n+1]);
printf("%.3lf\n",a[n][n+1]);
return 0;
}
BZOJ1923外星千足虫：取模高斯消元，感觉很吊，而且新技能get了bitset。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
#define N 2050
#define INF 0x7f7f7f7f
typedef bitset<N> M[N];
M a;
int n,m,ans=0;
void Gauss()
{
int i,j,k,l;
for (i=1;i<=n;i++)
{
j=i;while (!a[j][i]&&j<=m) j++;
if (j>m)
{ans=-1;return;}else
ans=max(ans,j);
swap(a[j],a[i]);
for (k=1;k<=m;k++)
if (k!=i&&a[k][i])
a[k]^=a[i];
}
return;
}
int main()
{
int i,j,k,l,q,w,e;
char b[N],c[N];
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%s%s",b,c);a[i][n+1]=c[0]-'0';
for (j=0;j<n;j++)
a[i][j+1]=b[j]-'0';
}
Gauss();
if (ans==-1)
{
printf("Cannot Determine\n");
return 0;
}
printf("%d\n",ans);
for (i=1;i<=n;i++)
if (a[i][n+1])
printf("?y7M#\n");else
printf("Earth\n");
return 0;
}
BZOJ2115XOR：感觉十分屌，可以将图转化为一条从1到n的路径及若干环，环有O(M)个，然后二进制按位看可不可以取，验证就用高斯消元。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 250050
#define ll long long
#define INF 0x7f7f7f7f
int ss=0,n,m,fi[N],c[N][2],tot=1,cir=0;
ll v[N],a2[N],s[N],ans=0,h[N];bool vis[N];
inline ll Read()
{
ll x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,ll z)
{
c[++ss][0]=y;c[ss][1]=fi[x];s[ss]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];s[ss]=z;fi[y]=ss;
return;
}
void DFS(int x)
{
vis[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (!vis[c[i][0]])
{
h[c[i][0]]=h[x]^s[i];DFS(c[i][0]);
}else
v[++cir]=h[c[i][0]]^h[x]^s[i];
return;
}
void Gauss()
{
int i,j,k,l;ll q,w,e;
for (q=a2[60];q;q >>= 1)
{
j=tot;while (j<=cir&&!(v[j]&q)) j++;
if (j>cir) continue;
swap(v[j],v[tot]);
for (i=1;i<=cir;i++)
if (i!=tot&&v[i]&q)
v[i]^=v[tot];
tot++;
}
return;
}
int main()
{
int i,j,k,l;ll q,w,e;
memset(s,0,sizeof(s));memset(h,0,sizeof(h));
memset(v,0,sizeof(v));memset(c,0,sizeof(c));
memset(a2,0,sizeof(a2));memset(fi,0,sizeof(fi));
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&m);
for (i=1,a2[0]=1;i<=60;i++) a2[i]=a2[i-1] << 1;
for (i=1;i<=m;i++)
k=Read(),l=Read(),q=Read(),Line(k,l,q);
DFS(1);Gauss();
ans=h[n];
for (i=1;i<tot;i++)
ans=max(ans,ans^v[i]);
cout <<ans<<endl;
return 0;
}
BZOJ2466树：据说只要高斯消元后暴力枚举未确定点DFS，总感觉dzy的代码很高能，现在还是不懂原理。。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 110
#define INF 0x7f7f7f7f
int a[N][N];
int n,m,ans,t[N];
void Gauss()
{
int i,j,k,l;
for (i=1;i<=n;i++)
{
j=i;while (!a[j][i]&&j<=n) j++;
if (j>n) continue;
swap(a[j],a[i]);
for (j=1;j<=n;j++)
if (j!=i&&a[j][i])
for (k=1;k<=n+1;k++)
a[j][k]^=a[i][k];
}
return;
}
inline void DFS(int x,int y)
{
if (y>=ans) return;
if (!x) {ans=min(ans,y);return;}
if (a[x][x])
{
t[x]=a[x][n+1];
for (int i=x+1;i<=n;i++)
t[x]^=(t[i]&a[x][i]);
DFS(x-1,y+t[x]);
}else
DFS(x-1,y+(t[x]=0)),DFS(x-1,y+(t[x]=1));
return;
}
int main()
{
int i,j,k,l,q,w,e;
while (scanf("%d",&n),n)
{
ans=INF;
memset(a,0,sizeof(a));memset(t,0,sizeof(t));
for (i=1;i<=n;i++)
a[i][i]=a[i][n+1]=1;
for (i=1;i<n;i++)
scanf("%d%d",&k,&l),a[k][l]=a[l][k]=1;
Gauss();DFS(n,0);
printf("%d\n",ans);
}
return 0;
}
BZOJ2337XOR和路径：之前一直在想怎么设从1到i的二进制位为1的概率写方程，其实还好，但是被样例卡了很久没想出来1怎么处理= =结果应该是设从i到n的二进制位为1的概率（好像确实没区别），并且a[n]设为0。然后按位跑高斯消元求出a[1]，然后带权求和即可。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 105
#define M 20050
#define INF 0x7f7f7f7f
int fi[N],c[M][3],n,m,ss=1,d[N];
double a[N][N],ans=0;
long long s=0;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
return;
}
void Gauss()
{
int i,j,k;double l;
for (i=1;i<n;i++)
{
j=i;while (!a[j][i]) j++;
swap(a[j],a[i]);
for (j=i+1;j<=n;j++) a[i][j]/=a[i][i];
a[i][i]=1;
for (j=1;j<n;j++)
if (a[j][i]&&j!=i)
{
l=a[j][i];
for (k=1;k<=n;k++)
a[j][k]-=a[i][k]*l;
}
}
return;
}
inline void Set_up(int x)
{
int i,j,k,l;double q,w,e;
for (i=1;i<n;i++)
{
q=1.0/d[i];a[i][i]=-1;
for (j=fi[i];j;j=c[j][1])
if (j%2&&c[j][0]==i) continue;else
if (c[j][0]==n) a[i][n]-=c[j][2]&x?q:0;else
if (c[j][2]&x)
a[i][c[j][0]]-=q,a[i][n]-=q;else
a[i][c[j][0]]+=q;
}
return;
}
int main()
{
int i,j,k,l,q,w,e;
memset(a,0,sizeof(a));memset(c,0,sizeof(c));
memset(fi,0,sizeof(fi));memset(d,0,sizeof(d));
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
k=Read(),l=Read(),Line(k,l,Read());
d[k]++;if (k!=l) d[l]++;
}
for (s=1;s<=1073741824;s <<= 1)
{
Set_up(int(s));Gauss();
ans+=(int)(s)*a[1][n];
memset(a,0,sizeof(a));
}
printf("%.3lf\n",ans);
return 0;
}
BZOJ3143游走：直接设每个点走过次数的期望列方程，注意边界是an=1以及a1的方程里面要加上1。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1050
#define M 1000050
#define INF 0x7f7f7f7f
struct Edge
{
int u,v;double t;
} b[M];
double a[N][N],ans=0;
int n,m,c[M][2],fi[N],ss=1,d[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line (int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
return;
}
void Gauss()
{
int i,j,k;double l;
for (i=1;i<n;i++)
{
j=i;while (!a[j][i]) j++;
swap(a[i],a[j]);
for (j=i+1;j<=n;j++)
a[i][j]/=a[i][i];
a[i][i]=1;
for (k=1;k<n;k++)
if (k!=i&&a[k][i])
{
l=a[k][i];
for (j=1;j<=n;j++)
a[k][j]-=l*a[i][j];
}
}
return;
}
void Set_up()
{
int i,j,k,l;double q,w,e;
for (i=1;i<n;i++)
{
a[i][i]=-1;
for (j=fi[i];j;j=c[j][1])
if (c[j][0]!=n)
a[i][c[j][0]]=1.0/d[c[j][0]];
}
a[1][n]=-1;
return;
}
inline bool cmp(Edge x,Edge y)
{
return x.t>y.t;
}
int main()
{
int i,j,k,l,q,w,e;
memset(c,0,sizeof(c));memset(a,0,sizeof(a));
memset(fi,0,sizeof(fi));memset(d,0,sizeof(d));
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
Line(b[i].u=k=Read(),b[i].v=l=Read()),d[k]++,d[l]++;
if (k==n) swap(b[i].u,b[i].v);
}
Set_up();Gauss();
for (i=1;i<=m;i++)
b[i].t=a[b[i].u][n]/d[b[i].u]+a[b[i].v][n]/d[b[i].v];
sort(b+1,b+m+1,cmp);
for (i=1;i<=m;i++)
ans+=b[i].t*i;
printf("%.3lf\n",ans);
return 0;
}
BZOJ3503和谐矩阵：由于元素数量过多，不能直接列方程，但是可以推出每个格子是哪些第一行元素的异或和，然后就直接列异或方程。但是最后求可行解的部分好像加了特技= =（其实是人太naive一开始还写什么DFS之类的什么找可行解）具体部分看代码吧。。。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 105
#define M 10050
#define ll long long
#define INF 0x7f7f7f7f
int a[N][N],n,m,c[N][N],ss;
ll b[N][N];
void Gauss()
{
int i,j,k,l;
for (i=1;i<=m;i++)
{
j=i;while (j<=m&&!a[j][i]) j++;
if (j>m) continue;
swap(a[i],a[j]);
for (j=1;j<=m;j++)
if (j!=i&&a[j][i])
for (k=1;k<=m;k++)
a[j][k]^=a[i][k];
}
for (i=m;i>=1;i--)
{
if (!a[i][i])
{c[1][i]=1;continue;}
for (j=i+1;j<=m;j++)
c[1][i]^=a[i][j]&c[1][j];
}
return;
}
int main()
{
int i,j,k,l,q,w,e;
memset(a,0,sizeof(a));memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
scanf("%d%d",&n,&m);
b[1][1]=1;for (i=2;i<=m;i++) b[1][i]=b[1][i-1] << 1;
for (i=2;i<=n+1;i++)
for (j=1;j<=m;j++)
b[i][j]=b[i-1][j-1]^b[i-1][j]^b[i-1][j+1]^b[i-2][j];
for (i=1;i<=m;i++)
for (j=1;b[n+1][i];j++)
a[i][j]=b[n+1][i]%2,b[n+1][i]/=2;
Gauss();ss=0;
for (i=2;i<=n;i++)
for (j=1;j<=m;j++)
c[i][j]=c[i-1][j-1]^c[i-1][j]^c[i-1][j+1]^c[i-2][j];
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
printf("%d ",c[i][j]);
printf("\n");
}
return 0;
}
先更到这里吧，感觉再多题目我也还是做不出来= =先提高自身姿势再来填坑吧。。。
