题目链接：http://lightoj.com/volume_showproblem.php?problem=1213
#include <stdio.h> int cases, caseno;
int n, K, MOD;
int A[1001]; int main() {
scanf("%d", &cases);
while( cases-- ) {
scanf("%d %d %d", &n, &K, &MOD); int i, i1, i2, i3, ... , iK; for( i = 0; i < n; i++ ) scanf("%d", &A[i]); int res = 0;
for( i1 = 0; i1 < n; i1++ ) {
for( i2 = 0; i2 < n; i2++ ) {
for( i3 = 0; i3 < n; i3++ ) {
...
for( iK = 0; iK < n; iK++ ) {
res = ( res + A[i1] + A[i2] + ... + A[iK] ) % MOD;
}
...
}
}
}
printf("Case %d: %d\n", ++caseno, res);
}
return 0;
}
题意：告诉你这段代码，然后优化，求res； n (1 ≤ n ≤ 1000), K (1 ≤ K < 231), MOD (1 ≤ MOD ≤ 35000)
我们很容易就知道最内成的加法式子执行了n^K次，每次加了K个数，所以一共加了K*n^K个数，一共有n个数，每个数加的次数一定是相同的，所以每个数都加了K*n^(K-1)次，所以结果就是Sum*K*n^(K-1)%mod; 快速幂求一下即可；
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int oo = 0xfffffff;
const int N = 1e3+5; LL K, mod, a[N]; int n; LL Pow(LL a, LL b)
{
LL ans = 1;
while(b)
{
if(b&1)
ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
} int main()
{
int T, t = 1; scanf("%d", &T); while(T--)
{ scanf("%d %lld %lld", &n, &K, &mod); LL sum = 0; for(int i=1; i<=n; i++)
{
scanf("%lld", &a[i]); sum = (sum + a[i])%mod;
} sum = (sum * K)%mod * Pow((LL)n, K-1)%mod; printf("Case %d: %lld\n", t++, sum);
}
return 0;
}