本文共 2055 字，大约阅读时间需要 6 分钟。

题目大意

给定长度为$n$的数组$a$，下面循环的深度为$k$，求$sum$：

int n, sum = 0;int a[maxn];ll solve(){       for (int i = 0; i < n; i++) {           for (int j = 0; j < n; j++) {               for (int k = 0; k < n; k++) {                   ...                sum += a[i] + a[j] + a[k] + ...;            }        }    }}

解题思路

这道题我打表找到的规律，后来去看了下题解，发现都讲的似懂非懂，没有说到正确的点上，后来我在纸上推了发现了正解：

不难发现我们只需要知道数组的每个元素一共出现了多少次。以$a[0]$为例，对于第一层循环的$a[0]$，当执行完下面的所有$k-1$层循环，那么$a[0]$一共被加了$n^{k-1}$次；对于第二层循环的$a[0]$，它上一层循环执行$n$次，它下面的循环执行了$n^{k-2}$次，根据乘法原理，那么它一共被加了$n^{k-1}$；以此类推，一共$k$层循环，那么我们就得出了，每个数都被加了$k\ast n^{k-1}$次。

//// Created by Happig on 2020/10/21//#include <bits/stdc++.h>#include <unordered_map>#include <unordered_set>using namespace std;#define fi first#define se second#define pb push_back#define ins insert#define Vector Point#define ENDL "\n"#define lowbit(x) (x&(-x))#define mkp(x, y) make_pair(x,y)#define mem(a, x) memset(a,x,sizeof a);typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef pair<int, int> pii;typedef pair<ll, ll> pll;typedef pair<double, double> pdd;const double eps = 1e-8;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double dinf = 1e300;const ll INF = 1e18;const int Mod = 1e9 + 7;const int maxn = 2e5 + 10;ll qkp(ll x, ll n, ll p) {       ll ans = 1;    x %= p;    while (n) {           if (n & 1) ans = ans * x % p;        x = x * x % p;        n >>= 1;    }    return ans;}int main() {       //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int T, kase, n, k, Mod;    cin >> T;    while (T--) {           cin >> n >> k >> Mod;        ll sum = 0;        for (int i = 1, x; i <= n; i++) {               cin >> x;            sum += x;        }        sum %= Mod;        ll ans = 1LL * k % Mod * qkp(n, k - 1, Mod) % Mod * sum % Mod;        cout << "Case " << ++kase << ": " << ans << ENDL;    }    return 0;}

转载地址：http://diqq.baihongyu.com/