Sample Input

2

3 1

1 2 3

3 10

1 2 3

Sample Output

6 60074

做法：快速幂+__int128,需注意ai可能是负数，模的是10^10+9，超int了

模乘法：对一个数可以拆分为N=（P*(N/P)+(N%P)）

 1 #include <bits/stdc++.h>
 2 #define MAX 100000
 3 #define LL long long
 4 //#define __int128 long long
 5 #define mod 10000000007LL
 6 using namespace std;
 7 int cas=1,T;
 8 template <class T>  
 9 bool scanff(T &ret)
10 { //Faster Input  
11     char c; int sgn; T bit=0.1;  
12     if(c=getchar(),c==EOF) return 0;  
13     while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();  
14     sgn=(c=='-')?-1:1;  
15     ret=(c=='-')?0:(c-'0');  
16     while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');  
17     if(c==' '||c=='
'){ ret*=sgn; return 1; }  
18     while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;  
19     ret*=sgn;  
20     return 1;  
21 } 
22 template <class T>
23 void printff(T ret)
24 { //Faster Output
25     char s[22];
26     if(ret<0) { printf("-");ret=-ret; }
27     int len=0;
28     while(ret)
29     {
30         s[++len]=ret%10+'0';
31         ret/=10;
32     }
33     if(!len) s[++len]='0';
34     while(len)
35     {
36         printf("%c",s[len]);
37         len--;
38     }
39 }
40 LL qmod( __int128 a, LL n)
41 {
42     __int128 res=1;
43     LL flag=1;
44     if(a<0) { flag=(n&1?-1:1);a=-a; }
45     a%=mod;
46     while(n)
47     {
48         if(n&1) res=res*a%mod;
49         a=a*a%mod;
50         n>>=1;
51     }
52     return (LL)res*flag;
53 }
54 int main()
55 {
56     //freopen("1.in","w",stdout);
57     //freopen("1.in","r",stdin);
58     //freopen("1.out","w",stdout);
59     scanf("%d",&T);
60     while(T--)
61     {
62         int n;
63         LL k,a,res=0;
64         scanf("%d%lld",&n,&k);
65         for(int i=0;i<n;i++)
66         {
67             scanf("%lld",&a);
68             res=(res+qmod(a,k))%mod;
69         }
70         printff((res+mod)%mod);
71         printf("
");
72     }
73     //printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
74     return 0;
75 }

View Code