2021-team8-002

从 Trac 迁移的文章

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

原文章内容如下：

= 流水账 =


= 总结 =
数据结构题尽量减小常数

= 题解 =

A:直接推式子然后递推。注意当i<A时dp[i]=1。

B:

C:

D:首先用类似KMP的方法计算转到哪些位置是可行的。令dp[i][0/1]表示转i次后位置与初始相同/不同的方案数。dp[i][0]=(n-1)*dp[i-1][1], dp[i][1]=dp[i-1][0]+(n-2)*dp[i][1]。矩阵乘法计算即可。

E:注意到从给定的每个party的举办人开始不断往父亲走，直到父亲不再满足年龄位于[L,R]之间，以最后停在的点作为party举办人，最终答案与原来相同。用倍增完成这一操作，然后直接dfs一次，树状数组维护根到当前节点每个年龄能参加的party数量的前缀和。

F: 模拟即可

G: 签到

H:

I:

J:

K: 每个点用一个01变量表示属于哪个集合，根据相邻点同一组有奇数个可以列n个异或方程，然后高斯消元

L:

M:相当于二维平面数点（枚举点），按第一维排序建树状数组，每个节点开vector按第二维排序，询问时分到树状数组的节点然后从前往后枚举即可（树状数组换成线段树就卡常了）

N:直接Pollard's rho，将所有质因子排序输出。

O:

流水账

总结

数据结构题尽量减小常数

题解

A:直接推式子然后递推。注意当i

B:

C:

D:首先用类似KMP的方法计算转到哪些位置是可行的。令dp[i][0/1]表示转i次后位置与初始相同/不同的方案数。dp[i][0]=(n-1)*dp[i-1][1], dp[i][1]=dp[i-1][0]+(n-2)*dp[i][1]。矩阵乘法计算即可。

E:注意到从给定的每个party的举办人开始不断往父亲走，直到父亲不再满足年龄位于[L,R]之间，以最后停在的点作为party举办人，最终答案与原来相同。用倍增完成这一操作，然后直接dfs一次，树状数组维护根到当前节点每个年龄能参加的party数量的前缀和。

F: 模拟即可

G: 签到

H:

I:

J:

K: 每个点用一个01变量表示属于哪个集合，根据相邻点同一组有奇数个可以列n个异或方程，然后高斯消元

L:

M:相当于二维平面数点（枚举点），按第一维排序建树状数组，每个节点开vector按第二维排序，询问时分到树状数组的节点然后从前往后枚举即可（树状数组换成线段树就卡常了）

N:直接Pollard's rho，将所有质因子排序输出。

O: