首页 > 代码库 > E - Fantasy of a Summation LightOJ1213
E - Fantasy of a Summation LightOJ1213
E - Fantasy of a Summation
Problem Description
If you think codes, eat codes then sometimes you may get stressed. In your dreams you may see huge codes, as I have seen once. Here is the code I saw in my dream.
1 #include <stdio.h> 2 3 int cases, caseno; 4 int n, K, MOD; 5 int A[1001]; 6 7 int main() { 8 scanf("%d", &cases); 9 while( cases-- ) {10 scanf("%d %d %d", &n, &K, &MOD);11 12 int i, i1, i2, i3, ... , iK;13 14 for( i = 0; i < n; i++ ) scanf("%d", &A[i]);15 16 int res = 0;17 for( i1 = 0; i1 < n; i1++ ) {18 for( i2 = 0; i2 < n; i2++ ) {19 for( i3 = 0; i3 < n; i3++ ) {20 ...21 for( iK = 0; iK < n; iK++ ) {22 res = ( res + A[i1] + A[i2] + ... + A[iK] ) % MOD;23 }24 ...25 }26 }27 }28 printf("Case %d: %d\n", ++caseno, res);29 }30 return 0;31 }
Actually the code was about: ‘You are given three integers n, K, MOD and n integers: A0, A1, A2 ... An-1, you have to write K nested loops and calculate the summation of all Ai where i is the value of any nested loop variable.‘
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with three integers: n (1 ≤ n ≤ 1000), K (1 ≤ K < 231), MOD (1 ≤ MOD ≤ 35000). The next line contains n non-negative integers denoting A0, A1, A2 ... An-1. Each of these integers will be fit into a 32 bit signed integer.
Output
Sample Input
23 1 350001 2 32 3 350001 2
Sample Output
Case 1: 6Case 2: 36
1 #include <stdio.h> 2 #include <queue> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <vector> 7 #include <map> 8 #include <set> 9 #include <ctime>10 #include <cmath>11 #include <cctype>12 using namespace std;13 typedef long long LL;14 const int N=1e5+10;15 const int INF=0x3f3f3f3f;16 int cas=1,T;17 int n,k,mod;18 int quick_mod(int t,int n)19 {20 int ans=1;21 while(n)22 {23 if(n&1) ans=ans*t%mod;24 t=t*t%mod;25 n>>=1;26 }27 return ans;28 }29 int main()30 {31 //freopen("1.in","w",stdout);32 // freopen("1.in","r",stdin);33 // freopen("1.out","w",stdout);34 scanf("%d",&T);35 while(T--)36 {37 scanf("%d%d%d",&n,&k,&mod);38 int ans=0;39 for(int i=0,x;i<n;i++)40 {41 scanf("%d",&x);42 ans+=x%mod;43 }44 ans%=mod;45 ans=k%mod * quick_mod(n,k-1) % mod *ans %mod;46 printf("Case %d: %d\n",cas++,ans);47 }48 //printf("time=%.3lf\n",(double)clock()/CLOCKS_PER_SEC);49 return 0;50 }
题解：
仔细研究一下代码会发现只是一条公式：k*n^(k-1)*(a1+a2+...+an)
然后快速幂即可，注意不要被循环绕晕
E - Fantasy of a Summation LightOJ1213