TC SRM 682
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-----------------------------------------------------------
看到某神犇在做于是看了一下题
发现都不会QAQ
于是果断找神犇问懂了，把懂了的东西写一下好了
-----------------------------------------------------------
250：
好像是bzoj3293（然后看了一眼，发现我A过，但是并不会）
-----------------------------------------------------------
500:
首先可以发现任意两个数做一次操作都不会变劣
考虑两个数以及他们的两个质因子a和b
假设一个是(a^c)*(b^d)另一个是(a^e)*(b^f)
操作一次之后得到:(a^min{c,e})*(b^min{d,f})和(a^max{c,e})*(b^max{d,f})
不妨假设c<e好了
那么操作之后的就是(a^c)*(b^min{d,f})和(a^e)*(b^max{d,f})
若b<f，那不变
否则，操作之后变优
考虑两个数的质因子(p^k这种），含有这个的两个数做一次操作这个不会消失，只会从一个上面除掉然后乘到另一个上面
然后，一定可以搞出一个数，他的所有质因子的指数都是出现过的最大的，这样一定是是最优的
对于剩下的数递归的搞就行了
-----------------------------------------------------------
900:
首先设x'=x+y,y'=x-y
那么x和y的每一次操作对于x'和y'来说都是两个人都是要么加要么减
因此x'和y'是不相关的（x'增大的时候y'增减都可以）
而答案就是(((x'+y')/2)^n)*(((x'-y')/2)^m)的期望
提一个2^(-n-m)出来，就只剩了((x'+y')^n)*((x'-y')^m)
为了方便下面都用x代替x'，y代替y'好了
暴力展开
这个就是Σ(i=0,n)C(n,i)*(x^i)*(y^(n-i)) * Σ(j=0,n)C(n,j)*(x^j)*((-y)^(n-j))
=Σ(i=0,n)Σ(j=0,n)C(n,i)*C(n,j)*(x^(i+j))*(y^(n-i))*(x^j)*((-y)^(n-j))
因为x,y互不影响，所以只需要单独求出x^k和y^k和(-y)^k的期望乘起来就好
以x为例
也就是说x有一个初始值x0,然后每一次转移它要么+1要么-1求x^i的期望
设f(i,j)表示转移了i次,x^j的期望
f(i,j)=Σ(k=0,j)C(j,k)*f(i-1,k) + Σ(k=0,j)C(j,k)*f(i-1,k)*((-1)^(j-k))
也就是二项式定理暴力展开..
然后就可以矩乘一下了
-----------------------------------------------------------
评论 (0)
