2020-team12-031

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(stding.png, 1000px)]]
[[Image(sub1.png, 1000px)]]
[[Image(sub2.png, 1000px)]]

== 特性 ==

本场三开

== 问题 ==


== 题解 == 

A:签到

B:对给你的两个单词暴力枚举数字，然后对加法后的数字进行数字对字母的还原，不能还原的先放着，然后在trie树上匹配这个新串，遇到没有确定的字母就枚举，匹配可以写成dfs。

C:模拟题，分解成子问题，先将子树的答案记录下，就好写了。（ctc想了半天才有这个好做法，之前一直在整体添加和修改，太难实现）

D:看似从上到下和从下到上都可以走，实际上会出现第i行如果走不到那么答案直接算i-1行，所以暴力是只能从上到下推SG的。但又可以观察发现每行之间的转移可以根据前8行是否可到得到，压位转移即可。

E:签到

F:暴力的复杂度瓶颈主要在于对于6e5个f(x)=ax^2^+bx+c要试除的质数数实在太多，考虑对每个数筛选出那些值得试除的质数。
① 对于一个质数p，若a%p!=0且p不等于2，那么在[0,p)内最多只有两个x使得(ax^2^+bx+c)%p=0.必要性显然，充分性可以反证，设三个x然后对方程作差。（也许学了离散后来会有更好的挣法？）
而6e5<2×3×5×7×11×13×17×19，所以对于最多八个a%p==0的质数让6e5个全都试除，否则通过cipolla模意义开根解出其两个解x1,x2以后，只要让所有的f(kp+x1),f(kp+x2)试除质数p即可，这显然是调和级数级别的试除数量。
② 如何确定要枚举的p? 我们先处理掉那些p^3^<f(6e5)的p(6e5以下）,那么试除完它们以后，剩下的只有单质数，大质数平方数和两个大质数相乘的情况，重点显然在于最后一种情况。考虑6e5以上的大质数显然也最多只有两个x。假设其为x1,x2,那么f(x1)-f(x2)%p=0 → a(x1+x2)(x1-x2)+b(x1-x2) %p=0 → (a(x1+x2)+b)%p=0.那么如果有p满足这个式子就可以得出存在两个数对它取余相同（如果为0，则产生贡献）从1到2*6e5枚举(x1+x2=x)，对这些x进行试除即可，注意这里也有1.2e6个1e12级别的数，同样不能直接筛，要“先解方程处理出要试除的小质数，将它们筛干净，留下一个大质数”。
于是得到整体算法流程： 筛小素数得到小素数集合P，先处理存在(a(x1+x2)+b)%p=0的那些大质数p得到集合Q，再对PUQ分别算出哪些f(x)要试除。总共试除的质数每次大约是7e6.

细节：
① Cipolla算法简介：（）
② 上面②步中，枚举x进行处理时，当a,b都%p=0时是要让所有x都试除的，如果有%p非0才要求-b/a%p再筛。因为这个WA17了一年。
③ 对于特别大的不可快速幂质数：有可能出现一个f(x) = p1×p2,p1是2^31.5^以上的大质数（不可以快速幂取逆元），p2是6e5以上的大质数，而p1有x1和x2而p2没有（除不掉），导致程序让p1*p2而非p1进入答案统计。严格来说，p1有可能回取到1e10,1e11,这需要写其他求逆元方式，但我的程序在第二步强行让3e9以下的质数都进入试除（1e9,2e9都不行）就在3.8秒通过了。
④ 直接(ll) sqrt(x) 不用担心炸精度，即使x有1e17级别。


G:整体右转45度，那么只需要对一条一条水平线和三角形求交，用组合数公式算一下即可。whn在实现时采用“先算三条线段与水平线的交点然后舍去在三角形外的那个”的方法，然后判点是否在三角形内的过程中炸了精度。

H: 

I: 

J: 

K: 签到。

L:签到

M：签到

N:

O:

[/wiki/2020-team12 返回]

特性

本场三开

问题

题解

A:签到

B:对给你的两个单词暴力枚举数字，然后对加法后的数字进行数字对字母的还原，不能还原的先放着，然后在trie树上匹配这个新串，遇到没有确定的字母就枚举，匹配可以写成dfs。

C:模拟题，分解成子问题，先将子树的答案记录下，就好写了。（ctc想了半天才有这个好做法，之前一直在整体添加和修改，太难实现）

D:看似从上到下和从下到上都可以走，实际上会出现第i行如果走不到那么答案直接算i-1行，所以暴力是只能从上到下推SG的。但又可以观察发现每行之间的转移可以根据前8行是否可到得到，压位转移即可。

E:签到

F:暴力的复杂度瓶颈主要在于对于6e5个f(x)=ax2+bx+c要试除的质数数实在太多，考虑对每个数筛选出那些值得试除的质数。

① 对于一个质数p，若a%p!=0且p不等于2，那么在[0,p)内最多只有两个x使得(ax2+bx+c)%p=0.必要性显然，充分性可以反证，设三个x然后对方程作差。（也许学了离散后来会有更好的挣法？）

而6e5<2×3×5×7×11×13×17×19，所以对于最多八个a%p==0的质数让6e5个全都试除，否则通过cipolla模意义开根解出其两个解x1,x2以后，只要让所有的f(kp+x1),f(kp+x2)试除质数p即可，这显然是调和级数级别的试除数量。

② 如何确定要枚举的p? 我们先处理掉那些p3

于是得到整体算法流程： 筛小素数得到小素数集合P，先处理存在(a(x1+x2)+b)%p=0的那些大质数p得到集合Q，再对PUQ分别算出哪些f(x)要试除。总共试除的质数每次大约是7e6.

细节：

① Cipolla算法简介：（）

② 上面②步中，枚举x进行处理时，当a,b都%p=0时是要让所有x都试除的，如果有%p非0才要求-b/a%p再筛。因为这个WA17了一年。

③ 对于特别大的不可快速幂质数：有可能出现一个f(x) = p1×p2,p1是231.5以上的大质数（不可以快速幂取逆元），p2是6e5以上的大质数，而p1有x1和x2而p2没有（除不掉），导致程序让p1*p2而非p1进入答案统计。严格来说，p1有可能回取到1e10,1e11,这需要写其他求逆元方式，但我的程序在第二步强行让3e9以下的质数都进入试除（1e9,2e9都不行）就在3.8秒通过了。

④ 直接(ll) sqrt(x) 不用担心炸精度，即使x有1e17级别。

G:整体右转45度，那么只需要对一条一条水平线和三角形求交，用组合数公式算一下即可。whn在实现时采用“先算三条线段与水平线的交点然后舍去在三角形外的那个”的方法，然后判点是否在三角形内的过程中炸了精度。

H:

I:

J:

K: 签到。

L:签到

M：签到

N:

O:

附加文件