kuangbin专题十四 LightOJ1213 规律+快速幂

本文主要是介绍kuangbin专题十四 LightOJ1213 规律+快速幂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
告诉你一段代码，然后要你找规律进行优化。
题解:
一看这道题就知道是有规律的但是硬是想了一下午都没想出来，结果上手打代码模拟一番之后就得出了答案，ORZ，不禁感叹实践出真理。这道题是怎么个规律呢？公式为：sum*k*n^(k-1).这个公式怎么的出来的呢？首先sum就是数组的总和，k就是多少行，n是数组的长度。好，现在来推导规律，首先我们看到代码就应该知道最里面那一行肯定是进行了n^k次的，然后我们先看那段代码中的a[k]是不是也运行n^k次呢，答案是肯定的。其中运行n^k中有n次是不同的数值的，就是数组中的长度，也就是可以用n次运算来算出总和sum的，那么就变成了n^(k-1)了，很好，那么*k又是怎么样来的呢，我们先将a[k]删去，看看a[k-1]项，a[k-1]在最里面那一行是不是也一样运算了n^k次呢？对，没错，然后就是用n次算出总和sum了，那么就可以得出了公式sum*k*n^(k-1)了，然后就是用快速幂来计算结果。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long int
const int MAXN=1000+7;
LL a[MAXN];
LL q_pow(LL p,LL n,LL mod)
{LL ans=1;while(n){if(n&1)ans=(ans*p)%mod;p=(p*p)%mod;n>>=1;//  printf("%lld %lld\n",ans,p);}
//  printf("%lld\n",ans);return ans%mod;
}
int main()
{int t,Case=1;scanf("%d",&t);while(t--){LL n,k,mod,sum=0;scanf("%lld%lld%lld",&n,&k,&mod);for(int i=1;i<=n;i++)scanf("%lld",&a[i]),sum=(sum+a[i])%mod;sum=((sum*q_pow(n,k-1,mod))%mod*k)%mod;printf("Case %d: %lld\n",Case++,sum);}
}