小汪作为一个有数学天分的程序猿,设计了一套密码生成器来搞定自己的密码问题。
密码生成器由N个槽位组成,槽位的下标为0~N-1,每个槽位存储一个数。起初每个槽位都是0。
密码生成器会进行M轮计算,每轮计算,小汪会输入两个数L,R(L<=R),密码生成器会将这两个数作为下标,将两个下标之间(包含)的所有槽位赋值为i(i为当前的轮次,i∈[1,M])。
M轮计算完成后,密码生成器会根据槽位的最终值生成一条密码,密码的生成规则为: (0a[0] + 1a[1] + 2*a[2] + …
(N-1)*a[N-1]) mod 100000009 其中a[i]表示第i个槽位的最终值。 请帮助小汪把他的密码生成器实现为代码。
输入描述:第一行为两个整数N,M,表示槽位个数和计算轮数。接下来M行,每行两个整数Li,Ri,表示第i轮计算的输入。
输出描述:输出一行,一个整数A,表示小汪的开机密码。
示例1输入5 32 31 21 1
输出10
说明对于输入样例,密码生成过程如下:初始: 0 0 0 0 0第1轮:0 0 1 1 0第2轮:0 2 2 1 0第3轮:0 3 2 1 0密码生成器最终生成 0 3 2 1 0,则密码为(0*0 + 3*1 + 2*2 + 1*3 + 0*4) mod 100000009 = 10
备注:mod 表示取余操作,a mod b表示a,b相除得到的余数对于前30%的测试数据,保证 N,M<=10000对于前50%的测试数据,保证 N,M<=200000对于100%的测试数据,保证 N<=1.5*10^7,M<=200000
import java.util.Scanner;public class Main {public static void main(String[] args) {/*** int[n] int l int r int m* 1.读入n和m* 2.创建密码数组,初始值为0,长度为n* 3.建立循环,循环次数为m,进行m轮计算操作* 4.计算完成后,生成最终密码** *///读入n和mScanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();//创建密码数组,初始值为0,长度为nint[] password = new int[n];//建立循环,循环次数为m,进行m轮计算操作for (int i = 1; i <= m; i++) {int l = sc.nextInt();int r = sc.nextInt();for(int j = l;j<= r;j++){password[j]=i;}}long result = 0;for (int i = 0; i < password.length; i++) {result += (long)(i * password[i]);}result = result % 100000009L;//计算完成后,生成最终密码System.out.println(result);}}