7.15测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
----------------------------------------------------------
SuperOj1721~1722,还有一道提答题
----------------------------------------------------------
T1:
不难发现他坑定是每次要么在当前位置相邻的位置拿一下,要么是在另一行任意位置拿一下
我写的是一种n^3的DP:
f[i][j][k]表示上面还剩i个,下面还剩j个,每次枚举在对面行拿多少个,然后乘以拿的方案数转移一下就行了
按照qjc的思路,可以用f[i][j][k][l]表示自己左边有i个,右边有j个,对面行有k个,当前在第l行,然后可以暴力转移一下,这个是n^4的
然后qjc发现i+j相同的时候f相同,因此就可以压缩到2维,然后就是n^2的了
按照lcr的思路,考虑把拿的过程倒过来,也就是添加,发现每次要么在自己两侧添加,要么在对面行添加一个,设表示上面已有i个,下面已有j个,暴力转移(转移是O(1)的)就行了,n^2的
----------------------------------------------------------
T2:
琦爷太神辣
首先有一个结论:d(a*b)=Σ(x|a)Σ(y|b)[(x,y) = 1]
为什么呢?
如果一个数是∏(pi^ki),那么这个数的约数个数就是∏(ki+1)
每个素数单独考虑,考虑第i个素数,归纳假设这个结论是对的,那么前i-1个素数生成的约数个数就是∏(kj+1)
设第i个素数在a中的幂次是u,在b中的幂次是v,那么最后的答案里面他的贡献是使得答案乘上了(u+v+1)
而第i个素数,设在x中的幂次是c,在y中的幂次是d,那么记为(c,d),这个表达式要求x,y互质,因此要么是(1~u,0),要么是(0,1~v),要么是(0,0),而第i个素数的幂次为任意值时,前面的素数都会取遍所有可能的值,根据归纳假设,前面的素数得到的答案是∏(kj+1),而第i个数使得答案不断的加上∏(kj+1),加了(u+v+1)次((c,d)的取值一共有u+v+1种),因此此时的答案就是(u+v+1)∏(kj+1),原结论得证
然后三个Σ的情况也同理可证,最后的答案就是
r = Σ(a)Σ(b)Σ(c)Σ(x|i)Σ(y|j)Σ(z|k)[(x,y) = 1] * [(x,z) = 1] * [(y,z) = 1]
= Σ(x)Σ(y)Σ(z) [(x,y) = 1] * [(x,z) = 1] * [(y,z) = 1] * floor(A / x) * floor(B / y) * floor(C / c)
另外为了方便设QT(x) = floor(T / x)
随便拿一坨来做懵逼钨丝反演,得到:
r = Σ(x)Σ(y)Σ(z) [(x,y) = 1] * [(x,z) = 1] * QA(x) * QB(y) * QC(z) * Σ(d|(y,z))miu(d)
= Σ(x)QA(x)Σ(d)miu(d)Σ(y)Σ(z)[(x,y) = 1] * [(x,z) = 1] * QB(y) * QC(z)
= Σ(x)QA(x)Σ(d)miu(d) (Σ(y)[(x,y) = 1] * QB(y)) * (Σ(z)[(x,z) = 1] * QC(z))
= Σ(x)QA(x)Σ(d)miu(d) fx(y) * gx(z)
然后枚举x,确定x后暴力求每个fx和gx的值,然后枚举d算一下就行了..
时间复杂度n^2
----------------------------------------------------------
T3:
NOI模拟题十合一...
不想说了,心累...
----------------------------------------------------------
评论 (0)
