【BZOJ3142】[HNOI2013]数列（组合计数）

题面

题解

唯一考虑的就是把一段值给分配给(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;
}