负担集训-Test7(多校联合训练-2)

----------------------------------------------
因为我F题没加多组数据输入输出错失前50...
惨啊...

 

----------------------------------------------
 
F:题意就是,现在有一个矩阵f,满足f[1][1] = f[1][2] = 1,f[1][i] = 2 * f[1][i-2] + f[1][i-1](i>=2),f[i][j] = Sigma(k=j,j+n-1)f[i-1][k],给你n和m,求f[m][1],n,m<2^63
 
首先从第二行开始,f[i][j]就是上一行一坨连续的部分相加,那么上一行满足的递推式这一行也应该满足,对于某一行,我们只需要知道他的前两个数字就可以用矩乘得到任意位置的数,还可以得到任意位置的前缀和,因此我们得到第一行的前缀和之后,可以再乘一个转换矩阵,把他变成第二行的初始状态,这样做m-1次之后就得到了第m行的初始状态
具体来说,我们记录状态用一个长度为4的向量S,分别表示当前第一个数,当前第二个数,从开头第一个数到现在第一个数的前缀和,从开头第二个数到现在第二个数的前缀和,还需要一个4*4的矩阵A,每一次把状态向量向后推一步并且更新前缀和,还需要一个4*4的矩阵B,把状态向量的前两维更新成后两维记录的前缀和,这样就把他推到了下一行的初始矩阵,最后的答案就是((B*A(n-1))^(m-1))*S的第一维分量
----------------------------------------------
G:题意就是说,现在给你一个质数p和一个整数m<=p-1,设f(i)为满足x^i = (x+y)^i (mod p)的二元组(x,y)个数,求Sigma(i=1,p-1)f(i)
p<=1e9+7,m<=p-1
 
因为P是质数,所以P一定有原根,我们假设这个原根是g。
现在设x=g^a,y=g^b,那么就有:g^ai=(g^a+g^b)^i
等价于:1=(1+g^(b-a))^i
设g^k = 1+g^(b-a) (因为1+g^(b-a) > 1,因此0<k<p-1)
那么就有g^ki=1
等价于(p-1)|ki
设d=gcd(p-1,i)
那么ki要是(p-1)的倍数,i贡献了d这一部分,剩下的(p-1)/d这一部分就要由k来贡献,而0<k<p-1,因此k的可能的取值就是(p-1)/((p-1)/d))-1种,也就是d-1种
现在,对于某个k,对于任意一个y,可以反解出x=y/(g^k - 1),因此对于任意一个y,都有d-1种x
因此对于i,(x,y)的对数就是m*(gcd(i,p-1)-1)
因此答案就是
r = m*Sigma(i)(i*gcd(i,p-1) - i)
  = m*Sigma(i)(i*gcd(i,p-1) - m*Sigma(i)i
  = m*Sigma(i)(i*gcd(i,p-1) - m*(p^2-1)/2
现在考虑来求f(p)=Sigma(i=1,p-1)i*gcd(i,p-1)
有f(p) = Sigma(i=1,p-1)*gcd(i,p-1)
       = Sigma(d | p-1)d Sigma(i=1,(p-1)/d)i*d*[gcd(i,(p-1)/d)]
       = Sigma(d | p-1)((p-1)/d)^2 Sigma(i=1,d)i*[gcd(i,d)]
设g(d,p) = Sigma(i=1,d)i*[gcd(i,d)]
那么f(p) = Sigma(d | p-1)((p-1)/d)^2 g(d,p)
现在考虑怎么求g(d,p)
有g(d,p) = Sigma(i=1,d)i*[gcd(i,d)]
         = Sigma(i=1,d)i*Sigma(d'|gcd(i,d))miu(d')
         = Sigma(d'|d)miu(d')Sigma(i=1,d/d')i*d'
         = Sigma(d'|d)miu(d')d'*Sigma(i=1,d/d')i
         = Sigma(d'|d)miu(d')d'*(1+d/d')(d/d')/2
         = (d/2) * Sigma(d'|d)miu(d')*(1+d/d')
miu(d')就O(d'^0.5)地去求就可以了
这样就做完了
----------------------------------------------
I:题意就是说,给你n个数a[1],a[2]..a[n],问你一个长度为n的整数数组,满足第i个数在[1,a[i]]之间,并且gcd>1,这样的数组个数。
n,a[i]<=100000
 
考虑素数容斥,加上gcd至少为2的方案数,加上gcd至少为3的方案数,加上gcd至少为5的方案数,减去gcd至少为6的方案数...
设gcd至少为k的方案数为f(k),那么答案就是r = Sigma(i=2,min{ai})miu(i)*f(i)
其中miu表示莫比乌斯函数
现在来考虑怎么求f(i)
我们不难发现f(k)=Pi(i=1,n)floor(a[i]/k)
而floor(a[i]/k)只有floor(max{a[i]}/k)种
因此枚举k的倍数p*k,然后看一下a[i]在[p*k,(p+1)*k)之间的有多少个就行了
这个时间复杂度是个调和级数,因此这个算法是O(nlg(n))的
----------------------------------------------