UVa 12810 - Sumthing

contents

1. 1. Problem
2. 2. Sample Input
3. 3. Sample Output
4. 4. Solution

Problem

$$S(1) = \sum_{i=1}^{n} A[i] \\ S(2) = 2 \sum_{i=1}^{n} \sum_{j=i+1}^{n} A[i] A[j] \\ S(3) = 2^{2} \sum_{i=1}^{n} \sum_{j=i+1}^{n} \sum_{k=j+1}^{n} A[i] A[j] A[k] \\ ...$$

將 S(1) … S(n) 加總後 mod 1000000009 輸出。

Sample Input

2
3
1 2 3
5
2 3 5 7 11

Sample Output

52
66412

Solution

特別發現到 1000000009 是質數，對於任意一個數字都存在乘法反元素，那麼將總和定義為

$(1 + 2 A[0])(1 + 2 A[1])(1 + 2 A[2]) ... (1 + 2 A[n])/2 \text{ mod } 1000000009$

/2 部分利用乘上 2 在 mod 1000000009 下的反元素即可。

#include <stdio.h> 

const long long mod = 1000000009LL;
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = (ret * x)%mod;
        y >>= 1, x = (x * x)%mod;
    }
    return ret;
} 
int main() {
    int testcase, n;
    long long div2 = mpow(2, mod-2, mod);
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        long long p = 1, x;
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x);
            p *= (1 + x * 2);
            p %= mod;
        }
        p = ((p - 1) * div2)%mod;
        printf("%lld\n", p);
    }
    return 0;
}