UC知道哪位高人提示一下思路。。acm题目。。。summing sums
来源：百度知道 编辑：UC知道 时间：2024/06/10 21:32:18
The N (1 <= N <= 50,000) cows, conveniently numbered 1..N, are trying to learn some encryption algorithms. After studying a few examples, they have decided to make one of their own! However, they are not very experienced at this, so their algorithm is very simple:
Each cow i is given a starting number C_i (0 <= C_i < 90,000,000),and then all the cows perform the following process in parallel:
* First, each cow finds the sum of the numbers of the other N-1 cows.
* After all cows are finished, each cow replaces her number with the sum she computed. To avoid very large numbers, the cows will keep track of their numbers modulo 98,765,431.
They told Canmuu the moose about it in November; he was quite impressed.
Then one foggy Christmas Eve, Canmuu came to say:
"Your algorithm is too easy to break! You should repeat it T(1 <= T <= 1,414,213,562) times instead."
Obviously, the cows were ver
USACO的题吧?
首先，设第k(1 <= k <= T)轮迭代后的数:
Vk1,Vk2,..Vkn,它们的和 = Sk
Sk = nS(k - 1) - (V(k-1)1 - V(k-1)2 - ...- V(k-1)n) = nS(k-1) - S(k-1)
(n - 1)S(k-1)
得到Sk = (n - 1)^k*S0 ......... (1)
S0可以累加输入数据得到
接下来，让我们看看Vk1(1 <= k <= 1)的规律:
V01 = V1
V11 = S0 - V1
V21 = S1 - V11 = S1 - S0 + V1
V31 = S2 - V21 = S2 - S1 + S0 - V1
....
当k是偶数时(配合(1)式)
Vk1 = S(k - 1) - S(k - 2) + S(k - 3) +.. -S0 + V1
= ((n - 1)^(k - 1) - (n - 2)^(k - 3) + ... - 1)S1 + V1(等比数列求和)
= ((n - 1)^k - 1)/n * S0 + V1 ...(2)
当k 是奇数时
Vk1 = S(k - 1) - S(k - 2) +... + S0 - V1
= ((n - 1)^(k - 1) - (n - 2)^(k - 2) +...+ 1)S0 - V1
= ((n - 1)^k + 1)/n * S0 - V1 ...(3)
这么一来，第k论迭代过后的Vk1都可以写成k的表达式
具体计算VT1 % MOD时，分子上半部分用乘幂的二分法O(log(k))完成，注意到 MOD = 98,765,431是质数，分母除法可以用n乘以MOD的逆来做，复杂度O(1)
类似的，VT2,VT3...VTn的值都可以这样求出，复杂度O(N)(前面的乘幂可保存下来后面不用重复计算)
好了，算法说到这个份上，程序你应该会写了吧?
好多英文啊 又头晕了 看英文书我倒不头晕