http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1009&cid=832
In the world line 1.048596%
“雪啊。”
“雪是红色的。”
像坏掉的复读机一样，梓川咲太只能把闪烁的思绪断断续续的说出来。
“这，是梦吧。”
从口中滑出的却是这样的话。
回过神的时候，天空即将被冰冷黑暗的天空吞没，而自己已经站在湘南台站附近的图书馆的门口。那是第一次遇见樱岛麻衣的地方，是一切的开端。
无所谓了，已经没有可以称为家而能回去的地方了。就在梓川咲太开始自暴自弃的躺在地上任由黑暗吞噬的时候。
眼前突然出现了穿着白大褂的年轻女子，在昏暗的路灯下，随风飘扬的似乎是红色的秀发。
“不要去轻易的改变过去。”开口便是这么难懂的话。
“打个比方，对于一个长度为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
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
using namespace std;
typedef long long ll;
const int N=100000;
const ll MOD=123456789;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,q;
int a[N+100];
ll cal(ll x){
__int128 v = x;
v = v * (v+1) * (v*2+1)/6;
v %= MOD;
return v;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
scanf("%d", &t);
while(t--){
int n, m;
scanf("%d%d", &n, &m);
ll ans = 0;
for(int i = 1; i <= m; ++i)
scanf("%d", &a[i]);
int lat = n+1;
for(int i = m; i >= 1; --i){
if(lat <= a[i]) continue;
ans += cal(lat-a[i]);
ans %= MOD;
lat = a[i];
}
ans = (ans%MOD)+MOD;
ans %= MOD;
printf("%lld\n", ans);
}
//cout << "Hello world!" << endl;
return 0;
}
京公网安备 11010502036488号