题解 P3228 【[HNOI2013]数列】

· · 题解

无耻的安利一波博客Chlience

这个题目我们可以画图AC

将某一个确定的上涨序列a[1],a[2],a[3],...,a[k]写出来

这个序列对于总数的贡献为1,当然,是当a[k]\leq n的时候

显然的,维持每天上涨的价格不变,由于a[1]能够有多种取值,那么它就会有很多贡献,当然,变化后的a[1]仍然要保证a[k]\leq n

那么能不能考虑维护一个股票价格的差分数列?就不用考虑a[1]的取值

并且,这个差分数列s[1],s[2],s[3],...,s[k-1]所做出的贡献就为n-\sum_{i=1}^{k-1}s[i]

一共有m^{k-1}个不同的差分数列,每个数列做出的贡献值为n-\sum_{i=1}^{k-1}s[i]

那么总贡献就为

\sum_{d=1}^{m^{k-1}}(n-\sum_{i=1}^{k-1}s[d][i])

将n提出可得

n*m^{k-1}-\sum_{d=1}^{m^{k-1}}\sum_{i=1}^{k-1}s[d][i]

现在要做的就是处理后面那一堆东西

注意,s显然是将所有可能的排列情况都算了进去,并且s[d][i]\in[1,m]

那么后面一共就会有m^{k-1}*(k-1)个数,并且在[1,m]中完全平均分布

所以[1,m]中的每个数都会出现\frac{m^{k-1}*(k-1)}{m}=m^{k-2}*(k-1)次

运用小学数学知识,将其总和化为m^{k-2}*(k-1)*\frac{(m+1)*m}{2}

这样就很好求解了

最终答案为n*m^{k-1}-m^{k-2}*(k-1)*\frac{(m+1)*m}{2} 快速幂就好啦╮(╯_╰)╭

努力追赶dalao中 给予我力量吧(丢脸ing

代码如下

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k,m,p,ans;
ll read() {
    ll ans=0,flag=1;
    char ch=getchar();
    while((ch>'9' || ch<'0') && ch!='-') ch=getchar();
    if(ch=='-') flag=-1,ch=getchar();
    while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return ans*flag;
}
ll qpow(ll a,ll b,ll mod) {
    ll ans=1;
    while(b>0) {
        if(b&1) {ans*=a;ans%=mod;}
        b>>=1;a*=a;a%=mod;
    }
    return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y) {
    if(b==0) {x=1;y=0;return a;}
    ll gcd=exgcd(b,a%b,x,y);
    ll t=x;
    x=y; y=t-(a/b)*y;
}
int main() {
    n=read(),k=read(),m=read(),p=read();
    ll x,y,gcd;
    gcd=exgcd(2,p,x,y);
    x=(x%p+p)%p;
    ans+=(qpow(m,k-1,p)*(n%p))%p;
    ans-=((((qpow(m,k-1,p)*(k-1))%p*(m+1))%p)%p*x%p);
    ans=(ans%p+p)%p;
    printf("%lld\n",ans);
    return 0;
}