F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 4772 >> 关于题目
CreationDecember @ 2017-03-22 07:20:23
[ Quote ] [ Edit ] [ Delete ] 1#
相信各位大佬都看出来这是一道毫无诚意的二合一
本题是我校一名神犇看论文找到的一个结论+之前省队集训的一道题目,我给强行合起来了,然后就拿去当胡策了
结果得分惨不忍睹,我想知道这个题目具体的难度是什么,在未经过出题人同意的情况下传了上来,深感愧疚
orz Claris 糖教 NiroBC怒踩std
题解方面,由于出题人不愿意露面,所以我这里简单说一下
以下来自出题人的课件

枚举一个有序数对(x,y)然后计算它们在所有划分方案里的出现次数并由此计算贡献就好啦。

假设我们可以预处理出来f[x][y]表示单个(x,y)的贡献
ans=∑x∑yf[x][y]∗∑i∑jg[n−x∗i−y∗j]
其中g[x]表示x的整数划分方案数(就是那个可以直接完全背包统计的东西)

我们发现固定住x,y,i以后那个j其实是个等差数列。

所以我们对于g数组统计一个部分和就可以了。时间复杂度O(n2logn)

关于函数g,实际上g(n)=φ(n)*d(n),可以用burnside引理证明
所以预处理函数g只需要线筛一下就可以了

@tangjz
Claris @ 2017-03-22 11:52:32
[ Quote ] [ Edit ] [ Delete ] 2#
这个题我发现直接枚举x,y,i,j复杂度也就5e7,并不是n^2log^2n
tangjz @ 2017-03-23 19:26:38
[ Quote ] [ Edit ] [ Delete ] 3#
楼上+1
CreationDecember @ 2017-03-24 21:14:12
[ Quote ] [ Edit ] [ Delete ] 4#
哦,受教了,原来是这样跑的比std还快(也可能是std的常数写挫了),不过当时出题人认为本题好的地方在于g函数,原本是想出一道g的前缀和,无奈出题人说自己想不出来怎么筛,所以就硬套了一个水idea
注:g函数其实是Menon’s Identity
tangjz @ 2017-03-25 12:46:13
[ Quote ] [ Edit ] [ Delete ] 5#
我也觉得g函数比较好,所以曾经出了一道题给uoj (๑•̀ㅂ•́)و✧(可惜没用上
xht13127 @ 2018-06-20 18:01:35
[ Quote ] [ Edit ] [ Delete ] 6#
g函数前缀和可以用min25筛求出。
[Top] [Previous Page] [Next Page]

HOME Back