https://ac.nowcoder.com/acm/contest/5961/B

description:

n个序列 每个序列有m个数 他们都是k的整数次幂 n个序列中所有数相乘乘积最大的值是多少 取模后输出

solution:

n和m范围不大 可以接受n * m 如果暴力计算的话 会因为取模操作而导致 大的数取模后变的比原来小的数更小 所以没法直接暴力
关键点在于他们都是k次幂 我们可以计算每个序列的指数之和 即 a[i][j] = k ^ pw 计算每个序列pw之和 取最大的 最后快速幂一下就可以得到答案了
如何快速得到指数pw 并且判断是否和a[i][j] 是本题关键 a[i][j] 范围在1e12 跑100次幂范围肯定没问题 使用pow函数计算
这样交了一发T了 复杂度还是不够优秀 毕竟pow函数有点玄学 把pow改成没有取模的快速幂 ac 算是卡了个常数 跑了900ms

最快的是对k的1到100次幂的数直接打表 然后1到100的范围暴力找 复杂度是 n * m * 100 跑了400ms
其次还有对n个序列中每个数a[i][j] /k 计算幂次 开个数组记录一下 这样跑了1200ms (可能是因为位数太多 也能ac

code

#include <bits/stdc++.h>

using namespace std;

#define LL long long

LL mod;

LL quickpow(LL a,LL b){
    LL res = 1;
    while(b){
        if(b & 1){
            res = res * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

LL pw[105];

int main() {

  int n,m;
  LL k;

  scanf("%d%d%lld%lld",&n,&m,&k,&mod);

  int ma = 0;
  pw[1] = k;
  for(int i = 2;i <= 100;i ++){
      pw[i] = pw[i - 1] * k;
  }

  for(int i = 1;i <= n;i ++){
      int sum = 0;
      for(int j = 1;j <= m;j ++){
          LL x;scanf("%lld",&x);
          for(int l = 1;l <= 100;l ++){
              if(pw[l] == x){
                  sum += l;
                  break;
              }
          }
      }
      ma = max(ma,sum);
  }

  printf("%lld\n",quickpow(k,1LL * ma));

  return 0;
}