BISHI66 子数列求积

思路

求解代码

privatestaticfinalintMOD=1000000007;/** * 主函数，处理输入输出并计算区间乘积 * * @param args 命令行参数 * @throws IOException 可能抛出IO异常 */publicstaticvoidmain(String[]args)throwsIOException{// 使用BufferedReader读取输入，PrintWriter输出结果BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));PrintWriterout=newPrintWriter(newOutputStreamWriter(System.out));// 读取第一行输入，分割字符串并解析为整数n和qString[]str=br.readLine().trim().split("\\s+");intn=Integer.parseInt(str[0]);// 数组长度intq=Integer.parseInt(str[1]);// 查询次数// 创建前缀积数组，大小为n+1long[]preProduct=newlong[n+1];preProduct[0]=1;// 初始化前缀积的第一个元素为1// 读取数组元素并计算前缀积String[]numStr=br.readLine().trim().split("\\s+");for(inti=1;i<=n;i++){longval=Long.parseLong(numStr[i-1]);// 解析当前元素// 计算前缀积，并对MOD取模preProduct[i]=(preProduct[i-1]*val)%MOD;}// 创建结果列表List<Long>res=newArrayList<>();// 处理每个查询for(inti=0;i<q;i++){// 读取查询区间String[]strQ=br.readLine().split("\\s+");intl=Integer.parseInt(strQ[0]);// 区间左端点intr=Integer.parseInt(strQ[1]);// 区间右端点// 计算preProduct[l-1]的模逆元longinvPreProduct=mypower(preProduct[l-1],MOD-2,MOD);// 计算区间[l,r]的乘积longans=(preProduct[r]*invPreProduct)%MOD;res.add(ans);// 将结果添加到列表中}// 使用StringBuilder构建输出字符串StringBuildersb=newStringBuilder();for(inti=0;i<res.size();i++){// 每个结果用空格分隔，最后一个结果后不加空格sb.append(res.get(i)).append(res.size()==n-1?"":" ");}// 输出结果并关闭流out.println(sb.toString());out.flush();out.close();br.close();}privatestaticlongmypower(longbase,longexp,longmod){longans=1%mod;while(exp>0){if(exp%2==1){ans=(ans*base)%mod;}base=(base*base)%mod;exp/=2;}returnans;}