题面
题解
设\(\{a_n\}\)为差分数组，可以得到柿子：
\[\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}
\]
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;
}