围观到叉姐和shi哥都强力推荐大妈题。于是就切了一套。
【ZOJ2313】
给定n<=10^2000，求一个最大的k，使得满足1<=k<=n/2 && ( i*k mod n 能取遍所有0~n-1的值 )
如果要取遍的话，必须(k,n)=1。
分3种情况讨论：
n%2==1 答案是n/2 . (k,2*k+1),考虑他们的gcd为g，那么必须 g | k，看另外一边，必然有2*k % g + 1 % g ==0 即 1 % g ==0……
n%2==0 && (n/2)%2==0 答案是n/2-1,首先因为k | 2k，n/2显然不可行。然后试试n/2-1，围观(k,2(k+1))，因为n/2-1是奇数，所以2不能作公因子。然后必然 g | k，于是(2%g) * ( k%g+1%g ) % g == 0，即2*(1%g) % g == 0.于是g=1.
n%2==0 && (n/2)%2==1 答案是n/2-2……模仿上面证吧
【ZOJ2314】
给出一个裸的无源汇上下界网络流模型，让你求一个可行流。
这个太裸直接套经典模型。
【ZOJ2315】
有一棵树，它的根节点不能涂色，让你给他的一些结点涂色，使得满足以下条件的情况下，涂的点最多，输出点数*1000和涂色方案。
1、每个结点只能有一个儿子被涂色。
2、如果本结点涂色了，那么该节点所有儿子都不能涂色。
直接树形dp……
【ZOJ2316】
给定一个无向图G=(V,E)，这个无向图对应一个N*M的矩阵A，对于矩阵中(i,j)这个格子，如果i是第j条边的其中一个端点，那么为1，否则为0。设另一M*N的矩阵B满足，B(i,j)=A(j,i)。令B * A=C，求C这个M*M的矩阵里所有元素的和是多少。
C[i,j]=Sum{ B[i,k]*A[k,j] }，他们必须都为1才能算进结果，并且只会令结果+1。那么但看中间k这个点而言，对答案的贡献显然是他度数的平方……于是水之。
【ZOJ2317】
一个N*M的矩阵(N<=10^100 M<=5)，里面每个格子要么涂白色要么涂黑色，假如矩阵里不存在2*2的子矩阵同色，那么是符合条件的。然后问，合法涂色方案有多少种。
状态压缩dp->矩阵乘法。
这个其实很水，但是常数很卡……一开始TLE到死去活来……
然后加了这个优化，还要注意变成unsigned int刚刚够（你们懂的）：
Mat operator * (const Mat &oth) const{
Mat ret;
Clear(ret.d);
int i,j,k;
for (i=0;i for (j=0;j for (k=0;k ret.d[i][j]+=d[i][k]*oth.d[k][j]; for (i=0;i for (j=0;j ret.d[i][j]%=Mod; return ret; } 5S TLE -> 300+MS 【ZOJ2318】 COCO船长被众岛围观，他那只船是圆的，岛也是圆的，问能不能再不上岸的情况下跑出这个群岛。 首先显然COCO的半径可以加到岛的半径上……然后…… T_T，我直接用了ZOJ3476 The wall II的方法……引射线，然后枚举起点，拆点，DFS判能否形成圈即可。 然后围观shi哥，发现他用了另外一个判多边形的方法，一次Bellman-Ford判负权即可…… 【ZOJ2319】 给定n<=100000个元素，让你求最多能共存多少个元素，两元素能共存必须满足Si 排序+LIS不用解释的……但是要输出方案。n lg n的算法大家都知道最后在那个表里的不是LIS。但是当你插入到表中的时候，在你前面的那一个必然可以作为你得到当前这个F值的Father……这个很容易YY到。然后Father link回去就可以了。 【ZOJ2320】 给定n(n<=100)个数，每个数Ai<=10^9，然后这些数的素因子只能是前T个素数(T<=100)。问有多少个非空子集，子集内的数之积为完全平方数。 完全平方数实际上就是在每个素因子上总个数为偶数……由于只有奇偶性，可以用布尔变量表示…… 然后可以根据这个列方程，每个变元Xi表示第i个数取还是不取，然后有T条方程，对应前T个素数与这n个数的奇偶关联。 一般我们guass消元的时候会发现无限解和无解的情况。无解很简单。平常的无限解就是某一步找不到主元了，这一个元其实是取true和false都可以
，而且只对前面的方程有影响，也就是将答案*2。然后一直消下去，那么计算有多少个元酱油了，答案应该就是2^cnt。但是注意到要非空子集，而显然空的时候是符合方程的，所以将答案-1即可。