| |
不指定 类别: 默认分类 | @ 2015/03/15 17:21 | 评论(0) | 阅读(1396)
A
    a和x必然有一个在10^6以内,枚举a或x到10^6的情况即可。

B
    二分搜索answer,然后判定乘积大于answer的有多少个
    判定的大概过程就是把A排序后,一边从左向右枚举i,一边维护另一个j,保证
ai*aj > answer 。这个过程中j显然是单调的。
    要分正负具体讨论,实现起来应该有些复杂。

C:
    虽然是一个环,但可以分奇偶讨论,简单地证明有一条边是用不到的。
    所有枚举断开的那条边,这个问题就变成了一个线性的分配问题。
    这样只要每次从断开的边上的某个点出发,分配的方式也就固定了:
    考虑每条边对答案的贡献,显然就是这条边的两侧看做一个整体,考察他们的整体
供需关系如何。

D:
    用一下必要条件:鸽笼原理。于是可以发现,字符串最长的长度不超过7。(举个
例子,字符串长度为10^6时,那么长度为6的字符串在其中最多出现了10^6 - 7 + 1次,
但长度为6的字符串最多有10^7 - 10^6个,一定会出现重复。而在实际情况中,由于
字符串排列本身的限制条件,导致实际的最长长度还要低于7。 )
    于是直接O(N*7)的暴力枚举,开个exist数组记录即可。
    并且由于数据过于温暖,现场赛还有部分O(N * M)的复杂度的极为粗暴的算法也被
温柔地放过了。

E:
    题解较长,看群内共享。

F:
    用一下等比数列求和公式,发现最后结果为(A^X - 1) / (A - 1),因为题目中给出
的限制条件,gcd(A, M) = gcd(A-1, M) = 1,可以发现/(A - 1)可以处理成某个非0的
乘法逆元,并不影响结果。
    于是考虑X取何值时,A^X % M = 1。由欧拉定理可知,X = phi(M)时为一个可行
解。
    然后可以证明可行解一定是phi(M)的最小的非1的约数。(充分性显然,必要性
可以用反证法,假设存在一个比phi(M)更小的Y,满足A^Y % M == 1,且Y不能够整除
phi(M),那么相当于存在A^(phi(M) % Y) == 1, 而phi(M) % Y又必然小于Y,那么
那么递归下去直到Y=1时,发现矛盾 )
    现场赛时有位数院的同学用BSGS的方法过了这个题,虽然代码跑了30s,也还是被放
过了= =

G:
    判断是否为对角线的依据就是:把这条边所在的两个点删掉以后,整张图是否变成
两个不连通的部分。
    最后只保留非对角线的边,然后dfs一遍,求字典序最小的遍历。

H:
    题解较长,看群内共享。

I:
    根据拓扑关系建树。可以虚拟一个0节点作为根节点,即该节点处于所有无父亲节点
的前面。
    对于每个节点,满足了下面的所有拓扑关系之后,相当于形成了一段相对顺序固定的
子序列。
    例如u节点以下有三个子节点,其三个子节点v1,v2,v3所包含的子树的节点数分别为
2,3,4。而dp(v1), dp(v2), dp(v3)则分别表示v1, v2, v3以下所有拓扑关系全部满足时
的方案数。
    此时u显然是u这个子树中第一个出现在最后生成的子序列中的数,而v1, v2, v3则为
三个相对位置关系并不确定,内部关系已经确定的子序列。
    那么先把第一个子序列v1放下来,再把v2插进去,确定顺序之后,再把v3插进去。
    用组合公式表示就是
    dp[u] = dp[v1] * C( v1 + 1 + v2 - 1, v2 ) * dp[v2] * C( v1 + v2 + v3 + 1 - 1, v3 )
* dp[v3]。
    (这里用到可重复组合的公式,即有n个盒子,放入m个球,每个盒子可以放置任意多个球,
总方案数为C(n + m - 1, m)。)

J:
    略。












--
hi, 如果还有什么问题,请在下面留言让我们知道 :)
无觅相关文章插件
默认分类 | 引用(0) |