3.10测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-----------------------------------------
题面大概可以在SuperOj上找到
-----------------------------------------
T1:
有意思的题...
用f1(a,b),f2(a,b),f3(a,b),f4(a,b)分别表示数字对(a,b)是否满足第一句话，第二句话，第三句话和第四句话，然后枚举一下数
对，丢到这四个函数里面验证一下就好
另外验证的时候数字可能达到很大
可以设置一个上界max，跳过超过了max的数字
但是这样就会增加一些不正确的答案（答案越少，跑的越快，最少的时候刚好全部是正确答案）
根据题目的条件可以知道刚好有22个答案，然后调一下参数直到只有22个答案为止
-----------------------------------------
T2:
随便推一推公式，最后长成这样：
设k = m^2-3m+3
f1 = m^2-m
答案r = f1*2^m*∑(i=1,n)k^(i-1) * i^m
所以只需要求h = ∑(i=1,n)k^(i-1) * i^m
矩乘可以拿到80分（需要优化一下常数）
另外20分有循环节
另外，GJY神犇有一种m*m*log的做法:
把公式再推几步：
n是奇数时暴力算，只考虑n是偶数
h = ∑(i=1,n/2)k^(i-1) * i^m + ∑(i=1,n/2)k^(i+n/2-1) * (i+n/2)^m
= ∑(i=1,n/2)k^(i-1) * i^m + k^(n/2)∑(i=1,n/2)k^(i-1) * (i+n/2)^m
= ∑(i=1,n/2)k^(i-1) * i^m + k^(n/2)∑(i=1,n/2)k^(i-1) * ∑(j=0,m)(n/2)^(m-j)*i^j*C(m,j)
= ∑(i=1,n/2)k^(i-1) * i^m + k^(n/2)∑(j=0,m) (n/2)^(m-j)*C(m,j) ∑(i=1,n/2)k^(i-1) * i^j
设f(n,m)=∑(i=1,n)k^(i-1) * i^m
就有h = f(n,m) = f(n/2,m) + k^(n/2)∑(j=0,m) (n/2)^(m-j)*C(m,j) f(n/2,j)
发现f的第一个参数只有log种(每次折半),第二个参数有m种，转移一次是O(m)的
时间复杂度O(m*m*log)
叶队还有一种O(m^2 + m*log*log)的算法(太神啦):
首先搞一个i^m的差分表出来
考虑差分表的第1列第p行对第j列第q行的贡献，就是从第1列第p行到第j列第q行的路径数（只能向上、右走），设为f(p,j,q)
显然有f(p,j,q)=f(p-r,j,q-r)
所以差相同的行贡献也相同
因此可以FFT来做到mlog递推一次
然后考虑对答案的贡献
为了方便用(a,b)表示第a列第b行，(a,s)表示n=a时的答案
(1,p)对(i,s)的贡献就是(1,p)对(j,1)的贡献的带权和(1<=j<=i)
假设已经求到了(i,j)和(i,s)
(1,p)对(i,s)的贡献和(i,p)对(2i,s)的贡献只差一个常数k^i
(i,p)对(2i,k)的贡献可以用FFT算
因此可以倍增
时间复杂度O(m*log*log),另外还要算上求差分表的时间复杂度O(m^2)
-----------------------------------------
T3:
首先把字符串排序，设的lcp(i,i+1)为height(i)
显然lcp(i,j)=min{height(k) | i<=k<=j}
然后设f(l,r,s)表示在[l,r]这个区间，选了s个数的答案
转移:f(l,r,s) = max{f(l,mid,i) + f(mid + 1,r,j) + i*j*height[mid] | i+j=s , mid是[i,r-1]中height最小的数}
[l,r]一共有O(n)个(像线段树那样),s有O(n)个
时间复杂度O(n^2)
-----------------------------------------
评论 (0)
