负担集训-Test7（多校联合训练-2）
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
----------------------------------------------
因为我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))的
----------------------------------------------
评论 (0)
