刷了一页的WA 。。终于发现了 哪里错了 快速幂模板里一个变量t居然开得long ...
虽然代码写的丑了点 但是是对的 那个该死的long 啊..
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 using namespace std; 8 #define mod 1000000007 9 #define LL __int64 10 #define N 100010 11 LL n,x,a[N],s,b[N]; 12 LL exp_mod(LL a,LL n,LL b) 13 { 14 long long t; 15 if(n==0) return 1%b; 16 if(n==1) return a%b; 17 t=exp_mod(a,n/2,b); 18 t=t*t%b; 19 if((n&1)==1) t=t*a%b; 20 return t; 21 } 22 int main() 23 { 24 int i; 25 cin>>n>>x; 26 for(i = 1; i <= n ; i++) 27 { 28 scanf("%I64d",&a[i]); 29 s = s+a[i]; 30 b[i] = a[i]; 31 } 32 for(i = 1; i <= n ; i++) 33 { 34 b[i] = s-a[n-i+1]; 35 } 36 for(i = 1; i <= n ;i++) 37 a[i] = b[i]; 38 LL k = a[1]; 39 int o = 2;LL ss=a[1]; 40 LL sum=1; 41 b[2]-=a[1]; 42 while(1) 43 { 44 if(b[o]==0&&o<=n) 45 { 46 o++; 47 b[o]-=a[o-1]; 48 sum++; 49 if(o>n) break; 50 else 51 continue; 52 } 53 if(o>n) break; 54 if(sum%x!=0) break; 55 while(sum%x==0&&o<=n) 56 { 57 sum/=x; 58 ss++; 59 b[o]--; 60 if(b[o]==0) 61 { 62 o++; 63 b[o]-=a[o-1]; 64 sum++; 65 break; 66 } 67 } 68 if(o>n) break; 69 } 70 while(sum&&sum%x==0) 71 { 72 ss+=1; 73 sum/=x; 74 } 75 printf("%I64d ",exp_mod(x,min(s,ss),mod)); 76 return 0; 77 }