灰暗而空虚的景色β
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 DEBUGusing 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 DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifscanf("%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; }?
總結
