题面
BZOJ https://lydsy.com/JudgeOnline/problem.php?id=3142
洛谷 https://www.luogu.org/problemnew/show/P3228
题解
唯一考虑的就是把一段值给分配给 \(k-1\) 天, 假设这 \(k-1\) 天分配好了, 第 \(i\) 天是 \(a_i\), 假设 \(Sum=\sum a_i\). 那么这一种分配方案的贡献就是 \(n-Sum\).
而分配方式一共有 \(m^{k-1}\) 种, 所以先把 \(n\) 个提出来, 得到 \(n*m^{k-1}\) 再减去一堆东西. 减去是的啥呢? 所有合法方案的 \(a_i\) 的和.
那么考虑一个位置为某个特定值的贡献就好了.
也就是 \((k-1)\frac{m(m+1)}{2}*m^{k-2}\)
直接快速幂就做完了.
- #include<iostream>
- using namespace std;
- int k,m,P;long long n;
- int fpow(int a,int b){int s=1;while(b){if(b&1)s=1ll*s*a%P;a=1ll*a*a%P;b>>=1;}return s;}
- int main()
- {
- cin>>n>>k>>m>>P;
- cout<<((n%P)*fpow(m,k-1)%P-(1ll*m*(m+1)/2)%P*(k-1)%P*fpow(m,k-2)%P+P)%P<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2909389.html