高斯消元 - hzwer.com

程序设计实习实验班2017推荐习题
区间众数问题这题写莫队是最容易的，可以对于每种出现次数的数字维护一个堆，用于删除时维护答案[crayon-673fb3f319b85191528295/]「BZOJ3659」WhichDreamedIt 神奇钥匙求以1为起点的欧拉回路的个数乘1的度数BESTtheorem[crayon-673fb3f319b95059333692/]「bzoj4031」[HEOI2015]小Z的房间矩阵树定理推荐阅读算法合集之《欧几里得算法的应用》[crayon-673fb3f319b9e292101605/]POJ2373DividingthePath用dp(i)...
12017年6月24日8,626递推与动规,STL,快速幂,单调队列,莫队算法,高斯消元

「FJ2015集训」热身题
「问题描述」定义F：F(1)=1,F(2)=2,F(n)=F(n-1)+F(n-2)(n>=3)定义p：p(i)=a1*F(1)^i+a2*F(2)^i+…+ak*F(k)^i其中k和a1…ak为常数。现在已知k,p(1),p(2),…,p(k)，求p(k+1)。为了避免高精度，所有运算都模掉M。保证F(1),…,F(n)在模质数M下两两不同，保证有唯一解。「输入格式」第一行，两个整数k,M。第二行，p(1),p(2),...,p(k)模M。「输出格式」输出p(k+1)模M。「样例输入1」310151129「样例输出1」83「样例输...
12015年7月12日4,955快速幂,高斯消元,乘法逆元
「BZOJ3270」博物馆
Description　　有一天Petya和他的朋友Vasya在进行他们众多旅行中的一次旅行，他们决定去参观一座城堡博物馆。这座博物馆有着特别的样式。它包含由m条走廊连接的n间房间，并且满足可以从任何一间房间到任何一间别的房间。两个人在博物馆里逛了一会儿后两人决定分头行动，去看各自感兴趣的艺术品。他们约定在下午六点到一间房间会合。然而他们忘记了一件重要的事：他们并没有选好在哪儿碰面。等时间到六点，他们开始在博物馆里到...
42015年2月6日6,626高斯消元,概率与期望
「codechef」December Challenge 2014
「codechefCAPPLE」ChefandAppleTrees其实我想练习打字，点开codechef随便做。。。后来发现这是在challenge，后来补了俩题[crayon-673fb3f31bef2955298291/]「codechefXORSUB」XORwithSubset求线性基，裸题[crayon-673fb3f31befb842220871/]「codechefSANSKAR」Alok-nathandHisSanskars从大到小排序后优先用大的合成随便搜索一下TAT这样过了codechef但是似乎会被构造卡掉144151017161211020171945...
02015年1月9日3,054模拟,深度搜索,高斯消元
「BZOJ2460」[BJ2011] 元素
Description 相传，在远古时期，位于西方大陆的MagicLand上，人们已经掌握了用魔法矿石炼制法杖的技术。那时人们就认识到，一个法杖的法力取决于使用的矿石。一般地，矿石越多则法力越强，但物极必反：有时，人们为了获取更强的法力而使用了很多矿石，却在炼制过程中发现魔法矿石全部消失了，从而无法炼制出法杖，这个现象被称为“魔法抵消”。特别地，如果在炼制过程中使用超过一块同一种矿石，那么一定会发生“魔法抵消”。后...
12015年1月8日5,464贪心,高斯消元
「BZOJ3105」[CQOI2013] 新Nim游戏
Description传统的Nim游戏是这样的：有一些火柴堆，每堆都有若干根火柴（不同堆的火柴数量可以不同）。两个游戏者轮流操作，每次可以选一个火柴堆拿走若干根火柴。可以只拿一根，也可以拿走整堆火柴，但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。本题的游戏稍微有些不同：在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样...
22014年12月20日7,176贪心,高斯消元
「BZOJ1923」[SDOI2010] 外星千足虫
DescriptionInput第一行是两个正整数N,M。接下来M行，按顺序给出Charles这M次使用“点足机”的统计结果。每行包含一个“01”串和一个数字，用一个空格隔开。“01”串按位依次表示每只虫子是否被放入机器：如果第i个字符是“0”则代表编号为i的虫子未被放入，“1”则代表已被放入。后面跟的数字是统计的昆虫足数mod2的结果。由于NASA的实验机器精确无误，保证前后数据不会自相矛盾。即给定数据一定有解。Output在给定数...
02014年12月16日5,258高斯消元
「BZOJ2115」[Wc2011] Xor
DescriptionInput第一行包含两个整数N和M，表示该无向图中点的数目与边的数目。接下来M行描述M条边，每行三个整数Si，Ti，Di，表示Si与Ti之间存在一条权值为Di的无向边。图中可能有重边或自环。Output仅包含一个整数，表示最大的XOR和（十进制结果）。SampleInput57122132241251453534432SampleOutput6HINT题解所有路径实际是一条1-n的路径和一堆环环用dfs求出。。。然后就是高斯消元的经典应用注意TT...
12014年12月12日5,672深度搜索,高斯消元
「hdu3949」XOR
ProblemDescriptionXORisakindofbitoperator,wedefinethatasfollow:fortwobinarybasenumberAandB,letC=AXORB,thenforeachbitofC,wecangetitsvaluebycheckthedigitofcorrespondingpositioninAandB.Andforeachdigit,1XOR1=0,1XOR0=1,0XOR1=1,0XOR0=0.Andwesimplywritethisoperatoras^,like3^1=2,4^3=7.XORisanamazingoperatorandthisisaquestionaboutXOR.WecanchooseseveralnumbersanddoXOR...
02014年12月11日7,158高斯消元
「BZOJ1770」[Usaco2009 Nov] lights 燈
Description貝希和她的閨密們在她們的牛棚中玩遊戲。但是天不從人願，突然，牛棚的電源跳閘了，所有的燈都被關閉了。貝希是一個很膽小的女生，在伸手不見拇指的無盡的黑暗中，她感到驚恐，痛苦與絕望。她希望您能夠幫幫她，把所有的燈都給重新開起來！她才能繼續快樂地跟她的閨密們繼續玩遊戲！牛棚中一共有N（1<=N<=35）盞燈，編號為1到N。這些燈被置於一個非常複雜的網絡之中。有M（1<=M<=595）條很神奇的無向...
32014年10月1日6,131深度搜索,高斯消元
「BZOJ1013」[JSOI2008] 球形空间产生器sphere
Description有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在，你被困在了这个n维球体中，你只知道球面上n+1个点的坐标，你需要以最快的速度确定这个n维球体的球心坐标，以便于摧毁这个球形空间产生器。Input第一行是一个整数，n。接下来的n+1行，每行有n个实数，表示球面上一点的n维坐标。每一个实数精确到小数点后6位，且其绝对值都不超过20000。Output有且只有一行，依次给出球心的n维坐标（n个实数），两个实数...
72014年3月13日8,160高斯消元