P3228 [HNOI2013]数列 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • 杜岱玮
    太强啦!%%%
  • CRYst_Alise
    你的新博客域名为什么我的浏览器访问还给我出来给个警告????
作者: 老K QAQ 更新时间: 2018-04-07 10:53  在Ta的博客查看 举报    4  

详情在博客(因为我的公式渲染出了点锅在这上面不好调)

就是快速幂了。


ll fpm(ll a,ll b,ll p){
    ll c=1;
    while(b){
        if(b&1)c=c*a%p; 
        a=a*a%p;
        b>>=1;
    }
    return c;
}
int main(){
#ifdef cnyali_lk
    freopen("3228.in","r",stdin);
    freopen("3228.out","w",stdout);
#endif
    ll n,m,k,p;
    n=read();//read是读入
    k=read()-1;
    m=read();
    p=read();
    n%=p;
    printf("%lld\n",(n*fpm(m,k,p)%p-fpm(m,k-1,p)*k%p*(m*(m+1)/2%p)%p+p)%p);
    return 0;
}

评论

  • 还没有评论
作者: League丶翎 更新时间: 2018-03-22 16:39  在Ta的博客查看 举报    2  

无耻的安利一波博客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;
}

评论

  • 还没有评论
作者: 撤云 更新时间: 2019-02-18 15:32  在Ta的博客查看 举报    1  

$blog$

$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$

#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);
}

评论

  • 杜岱玮
    博客过期了。。。
作者: zqy1018 更新时间: 2017-06-14 13:18  在Ta的博客查看 举报    0  

这是一道数学题。

解这道题可以利用画图和DP的方法。

由于图比较多,具体题解见这里:

题解

代码如下(实际上只有一个快速幂的过程):

ll N,M,K,P;
ll Pow(ll a,ll b,ll c){
    ll res=1;
    a%=c;
    while(b){
        if(b&1)res=(res*a)%c;
        a=(a*a)%c,b>>=1;
    }
    return res;
}
void init(){
    scanf("%lld%lld%lld%lld",&N,&K,&M,&P);
}
void solve(){
    ll ans1=Pow(M,K-1,P);
    ll inv2,ans;
    N%=P,ans=(N*ans1)%P;
    if(M&1)inv2=(M+1)/2,inv2=inv2*M%P;
    else inv2=M/2,inv2=inv2*(M+1)%P;
    inv2=inv2*(K-1)%P;
    inv2=inv2*Pow(M,K-2,P)%P;
    ans+=P,ans=(ans-inv2)%P;
    printf("%lld\n",ans);
}
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。