灰暗而空虚的景色β（数学思维题）

链接真的被这题坑惨了。。哎

题目：

“雪啊。”

“雪是红色的。”

像坏掉的复读机一样，梓川咲太只能把闪烁的思绪断断续续的说出来。

“这，是梦吧。”

从口中滑出的却是这样的话。

回过神的时候，天空即将被冰冷黑暗的天空吞没，而自己已经站在湘南台站附近的图书馆的门口。那是第一次遇见樱岛麻衣的地方，是一切的开端。

无所谓了，已经没有可以称为家而能回去的地方了。就在梓川咲太开始自暴自弃的躺在地上任由黑暗吞噬的时候。

眼前突然出现了穿着白大褂的年轻女子，在昏暗的路灯下，随风飘扬的似乎是红色的秀发。

“不要去轻易的改变过去。”开口便是这么难懂的话。

“打个比方，对于一个长度为n，所有元素都为0的数列。每次操作都选取一个位置，使得从这个位置往后都变成1,4,9,16…i^2 ”

“不可思议啊，为什么我一直在，为什么你们，一直在让我做这种数学题。”梓川咲太快濒临崩溃了。

“为了拯救樱岛麻衣和牧之原翔子。这样的理由够充分吗？”那位女子的一句话，让咲太的精神从深海下看到一束光。

“你能计算出经过这么多次操作以后变得面目全非的数列的和吗？”

“不可随便改变过去，就刚才那个比方来说，如果有很多次这样的操作，那么这个数列的和也很难计算吧。”

“可你现在就是面临这个问题哦。计算出那个数列的和，你一定能够知道答案。”这是只有拥有确信的心的人才能说出来的话。

“算出来以后呢。”梓川咲太还需要最后一块拼图。

“去找牧之原翔子吧，一切因她而始，也必定一切因她而终。”

时间的流动在慢慢的将咲太唤回现实。

“许多失败了的未来，无法挽回的过去，但是肯定在这之后，会有连接到…”

熟悉的话语再次传来。但话语的主人已经消失在夜空里。

Input

第一行输入一个数字T(T<=10)表示数据有多少组；

每一组数据第一行包含两个整数n(1<=n<=1e9)，Q(Q<=5e4),分别表示数列的长度以及操作的个数。

接下来的Q个数按照操作的时间顺序给出每次操作选择的位置.

Output

输出一个数字表示这个数列的和，由于答案可能很大，所以你需要将答案mod 123456789。

Sample Input

1

3 2

3

1

Sample Output

14

首先，一个公式很重要：

还有一个很类似但是用不到的

数列an=1 2 3 …… n=n(n 1)/2

n(n 1)(n 2)/6是数列{an}的前n项和

(来源百度)

首先分析一下这题的数据不能暴力，不能打表，只能使用某种数学方法。上述公式就是求值。另外，分析题目，其实真正改变串串大小的值的是靠前的位置和后出现的位置。那么可以从后往前看，先标记index为n 1,从后往前遍历b的数值发现只有数值小于index时候会更新部分值。增加的就是两个新旧点之间的距离长度的平方之和。如果大于index肯定不会更新数值的。

思路虽然明确的，但是对于java这题很坑的。n*(n 1)(n 2)会超出long范围，但是c 的int64可以用。如果Java的话可以考虑大数或者预处理。将除号除掉然后快速幂。

先把（n%mod）((n 1)%mod)处理了。然后再处理第三个，如果三个一块依然超出long范围。只能两两。

附上ac代码（没用大数）

import java.util.Scanner;
public class Main {
    static long mod=123456789;
  public static void main(String[] args) {
    // TODO 自动生成的方法存根
    Scanner sc=new Scanner(System.in);
    int t=sc.nextInt();
    for(int q=0;q<t;q  )
    {
      long n=sc.nextLong();
      int m=sc.nextInt();
      long value=0;
      long a[]=new long[m 1];
      for(int i=0;i<m;i  )
      {
        a[i 1]=sc.nextLong();
      }
      long index=n 1;
      for(int j=m;j>0;j--)
      {
        if(a[j]<index)
        {
          long len=index-a[j];
          long len1=len 1;long len2=(len*2 1);
          int q1=2;int q2=3;
          if(len%q1==0) {len=len/q1;q1=1;}
          if(len1%q1==0) {len1=len1/q1;q1=1;}
          if(len2%q1==0) {len2=len2/q1;q1=1;}
          if(len%q2==0) {len=len/q2;q2=1;}
          if(len1%q2==0) {len1=len1/q2;q2=1;}
          if(len2%q2==0) {len2=len2/q2;q2=1;}
          value =(((len%mod)*(len2%mod)%mod)*(len1%mod))%mod;
          value%=mod;
          index=a[j];
          //System.out.println(q1*q2 " " len2 " " len);
        }
      }
      value=(value%mod) mod;
      value%=mod;
      System.out.println(value);
    }
  }
}

哎，?，都是泪。