whyisyoung's Blog

If you can not persist, you will never succeed :)

EOJ 1851 Solution Report -- Summing Sums

| Comments

本题也可在SPOJ上找到:http://spoj.com/problems/SUMSUMS/

话说SPOJ注册真是…,不知道是不是被墙的原因?

keywords:

快速幂取模费马小定理

记 $sum = \sum\limits_{i = 1}^{n} C_i$ 为执行算法前所有牛的总和,

$a[t][i]$ 为处理 $t$ 次后的 $C_i$

$S[t] = \sum\limits_{i=1}^{n}a[t][i]$ 为处理t次后所有牛的总和。

有如下推导过程:

$t=0$ 时,

$t=1$ 时,

$t=2$ 时,

$t = 3$时,

由此可得到规律:

令 $\text{ns} = ((n-1)^{t-1} -(n-1)^{t-2} + (n-1)^{t-3}-…+(-1)^{t-1}(n-1)^0)$

因此 $a[t][i] = \text{ns} \cdot sum + (-1)^tC_i$

当然,上述过程都没有考虑取模。

我们需要先求 $x^n \mod m$ 这里用到了 二分求快速幂取模 的算法.

基本公式:

${a1} \cdot {a2} \% c = (({a1} \% c) \cdot {a2} ) \% c$

$a^{2^i} \% c = ((a^{2^{i-1}} \% c) \cdot a^{2^{i-1}}) \% c$

因此有了以下两种递归和非递归的算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// recursive version

long long single_mod(long long x, long long n, int MOD) // x^n % MOD
{
	long long ans;

	if(n == 0)
		return 1;
	if(n == 1)
		return x % MOD;
	ans = single_mod(x, n>>1);
	ans = ans * ans % MOD;
	if(n & 1)
		ans = ans * x % MOD;
	return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// unrecursive version (optimizied)

long long single_mod(long long x, long long n, int MOD) // x^n % MOD
{
	long long ans = 1;

	while(n) {
		if(n % 2)
			ans = ans * x % MOD;
		n >>= 1;
		x = x * x % MOD;
	}
	return ans;
}

接下来求 ns % MOD, 可采用等比数列求和公式, 调用上面写的 single_mod() 函数:

因为等比数列求和公式 $S_n = \frac{a_1 - a_nq}{1-q}$ 中有除法,所以不能直接取模。

采取如下办法:

若 $a \cdot c \% MOD = 1$

则 $\frac{b}{a} \% MOD = [(\frac{b}{a} \% MOD) \cdot (a \cdot c \% MOD)] \% MOD = b \cdot c \% MOD$

为了找到这样一个合适的 $c$,我们利用费马小定理

若$a, p$互质,则 $a^{p-1} \% p = 1$

因此,符合条件的 $c = a^{MOD - 2}$

在本题中, $a = 1 - q = 1 - (1-n) = n$

当 $t$ 为奇数时,首项为 1, 公比为 $1 - n$, 末项为 $(n-1)^{t-1}$

所以

当 $t$ 为偶数时,首项为 -1, 公比为 $1 - n$, 末项为 $(n-1)^{t-1}$

所以

image4

1
2
3
4
5
6
7
8
9
10
11
12
13
long long sum_mod(int n, int t) // ((n-1)^(t-1) - (n-1)^(t-2) + ... + (-1)^(t-1)*(n-1)^0) % MOD
{
	long long ans;

	long long a = single_mod(n-1, t);
	long long b = single_mod(n, MOD - 2);

	if(t & 1)
		ans = ((1 + a) * b) % MOD;
	else
		ans = ((-1 + a) * b) % MOD;
	return ans;
}

后面的处理除了注意下可能为负数时要加一个 MOD 再取模,其他都比较容易。 调用如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int main()
{
	int n, t;
	while(scanf("%d%d", &n, &t)!=EOF) {
		long long init_sum = 0;

		if(n == 1) {
			cout << 0 << endl;
			continue;
		}


		for(int i = 1; i <= n; i++) {
			scanf("%d", &c[i]);
			init_sum = (init_sum + c[i]) % MOD;
		}

		long long total_sum = sum_mod(n, t) * init_sum % MOD;

		if(t & 1)
        	for(int i = 1; i <= n; i++)
            	printf("%lld\n", (total_sum + MOD - c[i]) % MOD);
		else
		 	for(int i = 1; i <= n; i++)
		 		printf("%lld\n", (total_sum + c[i]) % MOD) ;
	}

	return 0;
}

Reference:

http://www.cppblog.com/coreBugZJ/archive/2012/02/29/166796.html

Comments