題面

題解

設(shè)\(\{a_n\}\)為差分?jǐn)?shù)組，可以得到柿子：
\[ \begin{aligned} ans &= \sum_{a_1 = 1} ^ m \sum_{a_2 = 1} ^ m \cdots \sum_{a_{k-1} = 1} ^ m (n - \sum_{i = 1} ^ {k - 1} a_i) \\ &= nm^{k - 1} - \sum_{a_1 = 1} ^ m \sum_{a_2 = 1} ^ m \cdots \sum_{a_{k - 1} = 1} ^ m \sum_{i = 1} ^ {k - 1} a_i \\ &= nm^{k - 1} - \sum_{i = 1} ^ {k - 1} \sum_{a_1 = 1} ^ m \sum_{a_2 = 1} ^ m \cdots \sum_{a_{k - 1} = 1} ^ m a_i \\ &= nm ^ {k - 1} - \sum_{i = 1} ^ {k - 1} \sum_{a_i = 1} ^ m a_i \times m ^ {k - 2} \\ &= nm ^ {k - 1} - m^{k - 2}(k - 1) \times \frac{m(m + 1)}2 \end{aligned} \]
沒了

代碼

#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define RG register #define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) #define clear(x, y) memset(x, y, sizeof(x))inline long long read() {long long data = 0, w = 1; char ch = getchar();while(ch != '-' && (!isdigit(ch))) ch = getchar();if(ch == '-') w = -1, ch = getchar();while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();return data * w; }long long N; int n, k, m, p; inline int Add(int x, int y) { return (x + y) % p; } inline int Minus(int x, int y) { return (x - y + p) % p; } inline int Mul(int x, int y) { return 1ll * x * y % p; } inline int fastpow(int x, int y) {int ans = 1;for(; y; y >>= 1, x = 1ll * x * x % p)if(y & 1) ans = 1ll * ans * x % p;return ans; }inline int S(int x) { return 1ll * x * (x + 1) / 2 % p; } int main() {N = read(), k = read(), m = read(), p = read();n = N % p, k %= p, m %= p;printf("%d\n", Minus(Mul(n, fastpow(m, k - 1)),Mul(fastpow(m, k - 2), Mul(k - 1, S(m)))));return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/cj-xxz/p/10393906.html

總結(jié)

以上是生活随笔為你收集整理的【HNOI2013】数列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。