牛客练习赛65题解：

A题:

思路：

毫无疑问，先把小的数加起来再依次乘最优，证明：

Code:

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long

using namespace std;

const ll mod = 998244353;
const int N = 5e5 + 10;
ll a[N], n;
ll ans;

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%lld", &a[i]);
    }
    sort(a + 1, a + n + 1); //先排序
    for (int i = 1; i <= (n >> 1); ++ i)
    {
        ans += a[i];//先把小的数加起来
    }
    ans %= mod;
    for (int i = (n >> 1) + 1; i <= n; ++ i)
    {
        ans = ans * a[i] % mod;//再依次乘
    }
    cout << ans;
    return 0;
}

B题：

思路：

因为每个数都是k的正整数次幂，所以可以直接以正整数次幂的形式存起来，是k的几次幂就存几，然后
根据，求最大的指数和，最后求就行了.

Code:

#include <iostream>
#include <cstdio>
#include <map>
#define ll long long

using namespace std;

const int N = 2020;

map<ll, ll> sq;

ll n, m, k, a[N][N], mod, ans;
ll qpow(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main()
{
    scanf("%lld%lld%lld%lld", &n, &m, &k, &mod);
    if (k == 1)
    {
        cout << 1 % mod;
        return 0;
    }
    else
    {
        int i = 0;
        ll cnt = 1;
        while (cnt < 10000000000010)
        {
            sq[cnt] = i;
            ++ i;
            cnt *= k;
        }
    }
    for (int i = 1; i <= n; ++ i)
    {
        ll cnt = 0;
        for (int j = 1; j <= m; ++ j)
        {
            scanf("%lld", &a[i][j]);
            cnt += sq[a[i][j]];
        }
        ans = max(ans, cnt);
    }
    cout << qpow(k, ans);
    return 0;
}