# AtCoder Beginner Contest 313 ## G - Redistribution of Piles ### 題意翻譯： 給定一個數列$a_i(a_i>0, i\in[1,n])$，和一個數$s$（初值為0），有兩種操作 - A - 全局非零數減一，減去的和加到$s$ - B ...
AtCoder Beginner Contest 313
G - Redistribution of Piles
題意翻譯：
給定一個數列\(a_i(a_i>0, i\in[1,n])\)，和一個數\(s\)（初值為0），有兩種操作
-
A - 全局非零數減一，減去的和加到\(s\)
-
B - 如果\(s\ge n\) , \(s \leftarrow (s-n)\) 數列全局加一
題解
不妨先排個序,設\(a_i\le a_{i+1}\)
那麼，每次操作A, 一定是前面的數先變為零。那麼我們考慮什麼時候對答案的貢獻會增加，
如果執行A， 再執行 B , 其間沒有數值改變，那麼這兩次操作作廢。
換句話說，我們僅僅執行有用的A，B操作。什麼時候有用？
-
執行A,當前狀態未到達過。
-
執行B,當前的數組差分情況剛剛發生改變。
那麼全部有效的執行操作序列是形如“AAAABBB”（首碼為A,尾碼為B）
顯然，有效的操作序列與最終序列形成雙射。
考慮A操作執行到把\(a_i\)變為零， 接著又把\(a_{i+1}-1\)， 即\((a_i,a_{i+1}]\) 。
那麼當前可執行的B操作次數為
\[\sum_{k=1}^{a_{i+1}-a_i} \lfloor\frac{s + k\cdot(n -i)}{n}\rfloor \]直接做的複雜度\(O(nA_{max})\)
我們考慮優化，註意到上面的式子相當於數一個線段(分子形如kx+b)下的點\((x, dn)\)。
我們換一個角度看問題，我們求出每一個 \(kn\)上面，有多少個點。
可以得到
\[\sum_{k\in(0,N]} \lfloor\frac{a + dk}{m}\rfloor = \sum_{k\in(0,\lfloor \frac{dN+a}{m} \rfloor]} \lfloor\frac{(a+dN)\mod m + km}{d}\rfloor \]我們遞歸求解即可,函數如下
int solve(int N, int D, int A, int M) {
if (!N) return 0;
ll p = ((D / M) * (N * (N - 1) / 2) % mod + (A / M) * N % mod) % mod;
D %= M, A %= M;
if (D) add(p, solve((D * N + A) / M, M, (A + D * N) % M, D), mod);
return p;
}
