题解 P3228 【[HNOI2013]数列】

[$blog$](https://www.cnblogs.com/hbxblog/p/10395890.html) ### $Solution$ 这道题貌似并不难的样子$QAQ$ 我们发现这个因为有首项的关系所以有点不太好弄.所以我们要将这个首项对答案的影响给去掉. 我们可以构建一个差分数组,我们令他等于$a[1],a[2]...a[k-1]$ 则一个查分数组对答案的贡献为: $$\sum_{i=1}^{k-1}n-a[i]$$ 然后我们一共有$m^(k-1)$个这样的查分数组,所以总贡献为: $$\sum_{j=1}^{m^{k-1}}\sum_{i=1}^{k-1}n-a[j][i]$$ 我们将$n$提出来,式子变为: $$n*m^{k-1}-\sum_{j=1}^{m^{k-1}}\sum_{i=1}^{k-1}a[j][i]$$ 所以现在只需要化简后面的式子了. 枚举一些数发现(实际上是我不会证明) 发现在区间$[1,m]的数每个数出现的个数相同$ 至于怎么发现的,打表找规律啊. 这样的话,每个数出现的次数就可以确定了: $m^{k-1}$个数组,每个数组$(k-1)$个数, 则每个数的个数为: $$m^{k-1}*(k-1)/m$$ $$=m^{k-2}*(k-1)$$ 然后后面式子的值就只需要用这个数乘上$1+2+3+...+m的值了$ 所以后面式子实际上就是: $$m^{k-2}*(k-1)*((1+m)*m)/2$$ 所以最终答案为: $$n*m^{k-1}-m^{k-2}*(k-1)*((1+m)*m)/2$$ 注意取模的问题啊,好坑!!! ### $Code$ ``` cpp #include<bits/stdc++.h> using namespace std; #define int long long int read(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar(); while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } int ksm(int a,int b,int mod){ int ans=1; while(b){ if(b&1) ans=a*ans%mod; a=a*a%mod; b>>=1; } return ans%mod; } main(){ int n=read(),k=read(),m=read(),p=read(); printf("%lld",(n%p*ksm(m,k-1,p)%p-ksm(m,k-2,p)*(k-1)%p*((1+m)*m/2%p)%p+p)%p); } ```