contents
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 Output
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 下的反元素即可。
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
|
#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("%lldn", p); } return 0; }
|
近期评论