Summing Sums
Time Limit:1000MSMemory Limit:30000KB
Total Submit:408Accepted:86
Description
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 very frustrated with having to perform so many repetitions of the same boring algorithm, so after many hours of arguing, Canmuu and the cows reached a compromise: You are to calculate the numbers after the encryption is performed!
*Some extra feedback will be provided for the first 10 submissions to this problem.
Input
* Line 1: Two space-separated integers: N and T
* Lines 2..N+1: Line i+1 contains a single integer: C_i
Output
* Lines 1..N: Line i contains a single integer representing the number of cow i (modulo 98,765,431) at the end of the encryption.
Sample Input
3 4
1
0
4
INPUT DETAILS:
Three cows, with starting numbers 1, 0, and 4; four repetitions of the encryption algorithm.
Sample Output
26
25
29
OUTPUT DETAILS:
The following is a table of the cows' numbers for each turn:Cows' numbers
Turn Cow1 Cow2 Cow3
0 1 0 4
1 4 5 1
2 6 5 9
3 14 15 11
4 26 25 29
Source
usaco 07CHN
----------------------------------------------------------------------------------------
解法一：
令 cs = c[1] + c[2] + ... + c[n-1] + c[n]；
令 a[t][i] = 处理 t 次后的c[i]；
令 s[t] = a[t][1]+a[t][2]+a[t][3] + … + a[t][n]
t = 0 时，
s[0] = cs = (n-1)^0 * cs
a[0][i] = c[i]
t = 1 时，
s[1] = (n-1)*s[0] = (n-1)^1 * cs
a[1][i] = s[0] – a[0][i] = (n-1)^0 * cs – c[i]
t = 2 时，
s[2] = (n-1)*s[1] = (n-1)^2 * cs
a[2][i] = s[1] – a[1][i] = ((n-1)^1-(n-1)^0)*cs + c[i]
t = 3 时，
s[3] = (n-1)*s[2] = (n-1)^3 * cs
a[3][i] = s[2] – a[2][i] = ((n-1)^2 – (n-1)^1 + (n-1)^0) * cs – c[i]
结论：
a[t][i] = [ (n-1)^(t-1) – (n-1)^(t-2) + (n-1)^(t-3) - … (n-1) ^ 0 ] * cs + (-1)^t * c[i]
令 ns = (n-1)^(t-1) - (n-1)^(t-2) + (n-1)^(t-3) - (n-1)^(t-4) ... (n-1)^(0)
则 a[t][i] = ns * cs + (-1)^t * c[i]
求 ns 时，使用二分法，求等比数列的和。
解法一代码
1/**//*
2
EOJ 1851 Summing Sums
3
4
5cs = c[1] + c[2] + 
+ c[n-1] + c[n]
6
7ns = (n-1)^(t-1) - (n-1)^(t-2) + (n-1)^(t-3) - (n-1)^(t-4) (n-1)^(0)
8
9a[i] = ns * cs + (-1)^t * c[i]
10
11ns 以二分法求得。
12
13
*/
14
15
16#include <stdio.h>
17
18
19#define M 98765431
20#define L 50009
21
22typedef __int64 Lint;
23
24int c[ L ];
25
26
27 /**//* return ( x^n ) % M */
28 /**//* 二分 */
29 /**//* n >= 0 */
30Lint pow_mod( Lint x, Lint n ) {
31 Lint p = 1, b = 1;
32
while ( b <= n ) {
33 b <<= 1;
34
}
35 b >>= 1;
36 x = x % M;
37 while ( b ) {
38 p = ( p * p ) % M;
39 if ( b & n ) {
40 p = ( p * x ) % M;
41 }
42 b >>= 1;
43 }
44 return p;
45}
46
47 /**//* return ( x^(n-1) + x^(n-2) + x^(n-3) + + x^2 + x^1 + 1 ) % M */
48 /**//* 二分 */
49 /**//* n >= 0 */
50Lint sum_pow_mod( Lint x, Lint n ) {
51 if ( 0 == n ) {
52 return 0;
53 }
54 if ( n & 1 ) {
55 return ( sum_pow_mod( x, n-1 ) + pow_mod( x, n-1 ) ) % M;
56 }
57 x = x % M;
58 return ( (x+1) * sum_pow_mod( x*x, n>>1 ) ) % M;
59}
60
61 /**//* return ns % M */
62 /**//* n >= 2 */
63 /**//* t >= 1 */
64Lint get_ns_mod( int n, int t ) {
65 Lint x = n - 1;
66 if ( 1 == t ) {
67 return 1;
68 }
69 if ( t & 1 ) {
70 return ( pow_mod( x, t-1 ) + M - get_ns_mod( n, t-1 ) ) % M;
71 }
72 return ( (x-1) * sum_pow_mod( x*x, t>>1 ) ) % M;
73}
74
75
76int main() {
77 int n, t, i;
78 Lint ns;
79 int cs = 0, ncs;
80 scanf( "%d%d", &n, &t );
81 for ( i = 1; i <= n; ++i ) {
82 scanf( "%d", c+i );
83 cs = ( cs + c[ i ] ) % M;
84 }
85
86 if ( 2 > n ) {
87 puts( "0" );
88 return 0;
89 }
90
91 ns = get_ns_mod( n, t );
92 ncs = (int)( ( ns * cs ) % M );
93 if ( t & 1 ) {
94 for ( i = 1; i <= n; ++i ) {
95 printf( "%d\n", ( ncs + M - c[ i ] ) % M );
96 }
97 }
98 else {
99 for ( i = 1; i <= n; ++i ) {
100 printf( "%d\n", ( ncs + c[ i ] ) % M );
101 }
102 }
103 return 0;
104}
105
----------------------------------------------------------------------------------------
解法二：
分析同上，只是
求 ns 时，使用等比数列求和公式。
对于除法之后再取余的问题，zyd 教了我一个技巧。
解法二代码
1/**//*
2EOJ 1851 Summing Sums
3
4
5cs = c[1] + c[2] + + c[n-1] + c[n]
6
7ns = (n-1)^(t-1) - (n-1)^(t-2) + (n-1)^(t-3) - (n-1)^(t-4) (n-1)^(0)
8
9a[i] = ns * cs + (-1)^t * c[i]
10
11
12ns 以等比数列求和公式求得。
13
14
15对于除法之后再取余数的处理：
16
17一：
18若 a * c % m == 1 ，
19则 b / a % m == ( b / a ) * ( a * c ) % m = b * c % m 。
20
21二：
22若 p 为质数且 a 与 p 互质，
23则 a^(p-1) % p == 1 。
24
25*/
26
27
28#include <stdio.h>
29
30
31#define M 98765431
32#define L 50009
33
34typedef __int64 Lint;
35
36int c[ L ];
37
38
39 /**//* return ( x^n ) % M */
40 /**//* 二分 */
41 /**//* n >= 0 */
42 /**//* x >= 0 */
43Lint pow_mod( Lint x, Lint n ) {
44 Lint p = 1, b = 1;
45 while ( b <= n ) {
46 b <<= 1;
47 }
48 b >>= 1;
49 x = x % M;
50 while ( b ) {
51 p = ( p * p ) % M;
52 if ( b & n ) {
53 p = ( p * x ) % M;
54 }
55 b >>= 1;
56 }
57 return p;
58}
59
60 /**//* return ns % M */
61 /**//* n >= 2 */
62 /**//* t >= 1 */
63Lint get_ns_mod( int n, int t ) {
64 Lint qt = pow_mod( 1-n+M, t );
65 Lint nm2 = pow_mod( n, M-2 );
66 Lint tmp = ( ( M + 1 - qt ) * nm2 ) % M;
67 return ( (t & 1) ? tmp : (M - tmp) );
68}
69
70
71int main() {
72 int n, t, i;
73 Lint ns;
74 int cs = 0, ncs;
75 scanf( "%d%d", &n, &t );
76 for ( i = 1; i <= n; ++i ) {
77 scanf( "%d", c+i );
78 cs = ( cs + c[ i ] ) % M;
79 }
80
81 if ( 2 > n ) {
82 puts( "0" );
83 return 0;
84 }
85
86 ns = get_ns_mod( n, t );
87 ncs = (int)( ( ns * cs ) % M );
88 if ( t & 1 ) {
89 for ( i = 1; i <= n; ++i ) {
90 printf( "%d\n", ( ncs + M - c[ i ] ) % M );
91 }
92 }
93 else {
94 for ( i = 1; i <= n; ++i ) {
95 printf( "%d\n", ( ncs + c[ i ] ) % M );
96 }
97 }
98 return 0;
99}
100
----------------------------------------------------------------------------------------
解法三：
模拟实际的变换过程，但是通过二分法加速。
构造矩阵
A =
[ -1 1 ]
| |
[ 0 n-1 ]
[ Ci ] [ Ci ]
| | = A^t * | |
[ CS ] [ CS ]
其中，A^t 可以二分。