蓝桥杯javaB组备战第二天 题目 区间次方和 编号3382

这是一个前缀和问题，但是不同于以为前缀和问题

前缀和问题求解思路：

创建一个前缀数组 s[] ,存储输入的元素的a[1]到a[n]的和

及：s[1] = s[i-1]+a[i]   ,i>=1

这样比暴力算法的复杂度要低很多可以将 时间复杂度从O(q*n*m)下降到 O(n*m+q)

区间次方和

注意：这里 1=<k<=5是重点

我当时在计算前缀和的时候，没有关注k的取值

思路如下：

只需要计算 数组的1-5次方的前缀和即可

用二维前缀和数组存储数据 

s[i][j]表示前j个元素的i次方和

i>=1 且j>=1

代码如下

package Lanqiao;import java.util.Scanner;public class L3382 {public static void main(String[] args) {Scanner in  = new Scanner(System.in);int n =in.nextInt();int m =in.nextInt();int a[] = new int[100010];long s[][] = new long[6][100010];for (int i = 1; i <=n ; i++) {a[i] =in.nextInt();for (int j = 1; j <=5 ; j++) {s[j][i] = (long) Math.pow(a[i],j)+s[j][i-1];}}for (int i = 0; i <m ; i++) {int l =in.nextInt();int r =in.nextInt();int k =in.nextInt();long sum = s[k][r]-s[k][l-1];sum = (long) (sum%(Math.pow(10,9)+7));System.out.println(sum);}in.close();}
}