题意：N（N<=40000）个数n1, n2, ..., nN (ni<=N)，求(2 ^ n1 + 2 ^ n2 + ... + 2 ^nN) / N % 1000003。 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3049 ——>>RJ白书上说“由于‘乘法逆’太重要了……”，上一年南京区赛同学也碰到了求逆元……现在，学习了。。       什么是乘法逆？ab % m = 1 （这里的 a, b 分别都是模 m 的同余等价类），a 模 m 的乘法逆是 b，同时，b 模 m 的乘法逆是a。       乘法逆有什么用？这个用处可还真不小。。如果要求 a / b % m（保证 b | a），但是 a 很大很大，比如 a = 2 ^ 40000，这个式子可不等价于 (a % m) / (b % m) % m。。这时，乘法逆就可以上场了。。一个数除以 b 后模 m，等价于该数乘以 b 模 m 的乘法逆后模 m。。于是上式可变成 a * b的乘法逆 % m，这就容易多了，就是 (a % m) * (b的乘法逆 % m) % m。。       怎么求乘法逆？要求 a 模 m 的乘法逆，设其为 x，因为 a * x % m = 1，所以 a * x + m * y = 1。。这是什么，一元二次方程，于是乎，扩展欧几里得飞一下就出来了。。 #include typedef long long LL; const int MOD = 1000003; const int MAXN = 40000 + 10; int N, kase; LL sum; int pow2[MAXN]; void GetPow2() { pow2[0] = 1; for (int i = 1; i < MAXN; ++i) { pow2[i] = (pow2[i - 1] << 1) % MOD; } } void Read() { int n; sum = 0; scanf("%d", &N); for (int i = 0; i < N; ++i) { scanf("%d", &n); sum = (sum + pow2[n]) % MOD; } } void gcd(LL a, LL b, LL& d, LL& x, LL& y) { if (!b) { d = a; x = 1; y = 0; return; } else { gcd(b, a % b, d, y, x); y -= a / b * x; } } LL Inv(int a, int n) { LL ret, d, y; gcd(a, n, d, ret, y); return d == 1 ? (ret + n) % n : -1; } void Solve() { LL ret; LL inv = Inv(N, MOD); ret = sum * inv % MOD; printf("Case %d:%I64d ", ++kase, ret); } int main() { int T; kase = 0; GetPow2(); scanf("%d", &T); while (T--) { Read(); Solve(); } return 0; }