AC. 梦想

frank_c1

2016多校联合训练6

发布于2016年08月04日 | 暂无评论 | 651阅读 | 比赛经历

今天题目好丧病啊……

早上听闻人手不足,有一种浓浓的要滚粗的感觉。

最后发现排名还不错,做了五道居然有rank 15,真不容易。

切了四道感觉还是不错的。感谢大爷们把思博题都让我A。

补题啦~

1001. A Boring Question

\sum_{1 \le k_1,k_2,...,k_m \le n} \sum_{j=1} ^ {m-1} {{k_{j+1} \choose k_j}} \mod 10 ^ 9 + 7

1 \le T \le 10000, 0 \le n \le 10 ^ 9, 2 \le m \le 10 ^ 9

这题可能需要一些高超的数学推导技巧。不过我们发现公式这样复杂,肯定有一些奥妙重重的规律。

我们小范围打表后可以发现,同一纵列是有明显的递推关系的。且第i列的递推公式为

f(0) = 1, f(n) = mf(n-1) + 1

结合高中数学知识可以推出通项是

f(n) = \frac{m ^ {n+1} -1} {m - 1}

时间复杂度O(T\log n)

1002. A Simple Chess

有一枚棋子,初始在(1,1),要走到(n,m)

棋子在(x,y)时可以走到(x+2,y+1)或者(x+1,y+2),不能出界。有r个坏点,棋子不能走到坏点上。

(1,1)走到(n,m)的方案数,答案对110119取模。保证(1,1)不是坏点。

1 \le n,m \le 10 ^ {18}, 1 \le r \le 100

这是一道经典问题。

一开始意识模糊了一下方程写错了。坑了一会儿才搞对。

先将点去重后按x - y排序。设点1是(1,1)f(i)是点1走到点i的方案数,则

f(i) = ways(1,i) - \sum_{j=2} ^ {i-1} {ways(j,i)f(j)}

ways(i,j)指点i走到点j的方案数。我们发现在每个点只有两种选择,我们先列个方程算出两种跳法各需要多少次,不妨设为a次和b次,则ways就是{a + b \choose a}

至于组合数,我们发现模数奥妙重重,肯定是Lucas啦。

时间复杂度O(r ^ 2 \log n)

1003. A Simple Nim

给定n堆石子,第i堆有a_i个。

每次玩家有两种操作。第一种是选取一堆,取走其中若干个石子。第二种是将一堆石子分成三堆,每堆非空。

求是否先手必胜。

1 \le T \le 100, 1 \le n \le 10 ^ 6, 1 \le a_i \le 10 ^ 9

设某堆有x个石子的SG值是SG(x)

结合定义,有

SG(x) = mex\{SG(0),SG(1),...,SG(x-1),SG(i) \; xor \; SG(j) \; xor \; SG(k) \; |  \; i + j + k = x\}

发现数据范围奥妙重重。于是我们小范围打个表,发现SG(8k + 7) = 8k + 8, SG(8k + 8) = 8k + 7, k \in N,其他SG(x) = x。求一发SG和即可。

时间复杂度O(Tn)

1004. Magic Number

1005. Master Zhu

1006. Stabilization

1007. This world need more Zhu

给定n个点的带权树,第i个点权值为a_i

给定m个询问,形如

1 \; u \; v \; a \; b:询问点u子树中出现过a次的权值之和与出现过b次的权值之和的最大公约数,保证u = v

2 \; u \; v \; a \; b:询问路径(u,v)上出现过a次的权值之和与出现过b次的权值之和的最大公约数。

1 \le T \le 10, 1 \le n,m \le 10 ^ 5, 1 \le a_i \le 10 ^ 9

数据范围和仅有询问操作说明肯定是莫队。

我们发现子树操作可以转化为区间操作。于是我们发现两种操作分别对应树上莫队和序列莫队,分开来做就好了。

于是就找板子拼成了一份200+行的代码。出题人您有意思吗?

时间复杂度O(Tn \sqrt {n})

1008. To My Girlfriend

1009. Up Sky,Mr.Zhu

1010. Windows 10

1011. Zhu’s Math Problem