Data Processing
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 530 Accepted Submission(s): 191
Problem Description
Chinachen is a football fanatic, and his favorite football club is Juventus fc. In order to buy a ticket of Juv, he finds a part-time job in Professor Qu’s lab.
And now, Chinachen have received an arduous task——Data Processing.
The data was made up with N positive integer (n1, n2, n3, … ), he may calculate the number
, you can assume
mod N =0. Because the number is too big to count, so P mod 1000003 is instead.
Chinachen is puzzled about it, and can’t find a good method to finish the mission, so he asked you to help him.
And now, Chinachen have received an arduous task——Data Processing.
The data was made up with N positive integer (n1, n2, n3, … ), he may calculate the number
, you can assumemod N =0. Because the number is too big to count, so P mod 1000003 is instead.Chinachen is puzzled about it, and can’t find a good method to finish the mission, so he asked you to help him.
Input
The first line of input is a T, indicating the test cases number.
There are two lines in each case. The first line of the case is an integer N, and N<=40000. The next line include N integer numbers n1,n2,n3… (ni<=N).
There are two lines in each case. The first line of the case is an integer N, and N<=40000. The next line include N integer numbers n1,n2,n3… (ni<=N).
Output
For each test case, print a line containing the test case number ( beginning with 1) followed by the P mod 1000003.
Sample Input
2 3 1 1 3 4 1 2 1 4
Sample Output
Case 1:4 Case 2:6HintHint: You may use “scanf” to input the data.
Source
这个题比较水。直接二分幂，然后分母求逆元就可以了
我的代码：
#include<stdio.h>
#include<string.h>
typedef __int64 ll;
ll num[40005];
ll mod=1000003;
ll power(ll p,ll n,ll m)
{
ll sq=1;
while(n)
{
if(n%2==1)
sq=(sq%m)*(p%m)%m;
p=(p%m)*(p%m)%m;
n=n/2;
}
return sq%m;
}
int main()
{
int t,T,i;
ll re,n,ans;
scanf("%d",&T);
for(t=1;t<=T;t++)
{
scanf("%I64d",&n);
for(i=1;i<=n;i++)
scanf("%I64d",&num[i]);
re=power(n,mod-2,mod);
ans=0;
for(i=1;i<=n;i++)
ans=(ans+power(2,num[i],mod))%mod;
ans=ans*re%mod;
printf("Case %d:%I64d\n",t,ans);
}
return 0;
}