2018-Reconquista-T2
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
== Contest Information ==
'''XVI Open Cup - Grand Prix of SPb'''
[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010314 Opentrains]
== 流水账 ==
== 总结 ==
=== lsmll ===
本次训练很多题都犯了不应该的错误，代码出bug比较多，应该是很久没有训练过的原因。D题的做法应该是有待改进的，所以卡了很长时间常数才做出来。应该注意查错时最好仔细看完代码把所有错误找出来再改。
=== jsb ===
这场比赛打得有点糟糕。开场不是很顺利，大家各有罚时（然而毒瘤非我莫属）；后来不知不觉就在三开了。
我开了D题，转化大概正确，但选择了比较麻烦的线段树去维护，然后怎么也调不出了……
在lzw学长的帮助下调出了一些bug，后来还要借助对拍才保证了正确性……
结果TLE了……乱七八糟卡常数卡了很久才过……贡献了一坨罚时……
感觉这种题还是要再考虑考虑有没有更优美的做法（虽然我们好像想了很久了）。真的转化麻烦了的话，其实可以考虑先去开别的题。
立个flag，会去补题的。
=== lzw ===
我写的E题出了不少锅，每次对着代码发现了一个错误就改一下提交，导致了不必要的罚时。应该吸取教训，把整份代码检查一遍再提交。最后get成就帮助jsb找出了D题代码的一个bug。
== 补题 ==
B []
C []
F [lzw] 在整数环上，所有形如AX + BY的最小正整数是gcd（A， B）。 这个性质可以推广到多项式上，证明和整数环上的证明一致。 所以我们要求的就是AX + BY = gcd（A， B）的一组（X， Y）。 整数环上就是扩展欧几里德，多项式的话要做辗转相除，除法比较恶心。所以可以考虑辗转相减。 利用性质： AX + BY = gcd(A, B) 和
BX + （A - CB）Y = gcd（A， B） 解空间是一样的。
假设deg（A） >= deg(B). 如果deg（A） = deg（B）。 求出BX + （A - B）Y = gcd 的解（X， Y）， 那么 （Y， X - Y）是AX + BY = gcd 的解。 如果deg（A） > deg(B). k = deg(A) - deg(B). 求出BX + (A - Bx^k^)Y = gcd的解（X， Y）， 那么（Y， X-Yx^k^）是原方程的解。 mod 2的多项式环上， 减法和加法等价于bitset的xor，可以用bitset优化。
K [lsmll]
L []-jsb
== Solution ==
[http://www.cnblogs.com/clrs97/p/6032092.html Claris]Contest Information
XVI Open Cup - Grand Prix of SPb
流水账
总结
lsmll
本次训练很多题都犯了不应该的错误，代码出bug比较多，应该是很久没有训练过的原因。D题的做法应该是有待改进的，所以卡了很长时间常数才做出来。应该注意查错时最好仔细看完代码把所有错误找出来再改。
jsb
这场比赛打得有点糟糕。开场不是很顺利，大家各有罚时（然而毒瘤非我莫属）；后来不知不觉就在三开了。
我开了D题，转化大概正确，但选择了比较麻烦的线段树去维护，然后怎么也调不出了……
在lzw学长的帮助下调出了一些bug，后来还要借助对拍才保证了正确性……
结果TLE了……乱七八糟卡常数卡了很久才过……贡献了一坨罚时……
感觉这种题还是要再考虑考虑有没有更优美的做法（虽然我们好像想了很久了）。真的转化麻烦了的话，其实可以考虑先去开别的题。
立个flag，会去补题的。
lzw
我写的E题出了不少锅，每次对着代码发现了一个错误就改一下提交，导致了不必要的罚时。应该吸取教训，把整份代码检查一遍再提交。最后get成就帮助jsb找出了D题代码的一个bug。
补题
B []
C []
F [lzw] 在整数环上，所有形如AX + BY的最小正整数是gcd（A， B）。 这个性质可以推广到多项式上，证明和整数环上的证明一致。 所以我们要求的就是AX + BY = gcd（A， B）的一组（X， Y）。 整数环上就是扩展欧几里德，多项式的话要做辗转相除，除法比较恶心。所以可以考虑辗转相减。 利用性质： AX + BY = gcd(A, B) 和
BX + （A - CB）Y = gcd（A， B） 解空间是一样的。
假设deg（A） >= deg(B). 如果deg（A） = deg（B）。 求出BX + （A - B）Y = gcd 的解（X， Y）， 那么 （Y， X - Y）是AX + BY = gcd 的解。 如果deg（A） > deg(B). k = deg(A) - deg(B). 求出BX + (A - Bxk)Y = gcd的解（X， Y）， 那么（Y， X-Yxk）是原方程的解。 mod 2的多项式环上， 减法和加法等价于bitset的xor，可以用bitset优化。
K [lsmll]
L []-jsb