[HNOI2013] 数列

Author Avatar
空気浮遊 2018年03月10日
  • 在其它设备中阅读本文章
  • 数论
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

Problem

小 T 最近在学着买股票,他得到内部消息:F 公司的股票将会疯涨。股票每天的价格已知是正整数,并且由于客观上的原因,最多只能为 N。在疯涨的 K 天中小 T 观察到:除第一天外每天的股价都比前一天高,且高出的价格(即当天的股价与前一天的股价之差)不会超过 M,M 为正整数。并且这些参数满足 M(K-1)<N。小 T 忘记了这 K 天每天的具体股价了,他现在想知道这 K 天的股价有多少种可能

$M,\ K,\ P \leq 10^9,\ N \leq 10^{18}$
本题很贴心地没有提醒,P 可能不为质数,但一定为奇数

Solution

设计一个平面直角坐标系。纵坐标为股价,横坐标为第 x 天,整点上用数字表示方案数。

从 1 天开始,假设股价走的折线到第 k 天是一条道路,题目需要你统计道路的个数。
假设 m =2,第一天价格为 1,我们把这个道路和方案数画出来,发现很像斜着的杨辉三角。

那么考虑 m 不为 2 的情况。则第一天方案数为 $1$, 第二天方案数为 $m$。第三天由于方案数的每个 1(每一条现已经发展的道路)都会有贡献,则第三天方案数为 $m^2$。以此类推,第 k 天方案数为 $m^{k-1}$。

显然这个方案数三角的第 k 天一列,是一列按股价从上到下排的数字。而这列数字由于类似杨辉三角的性质,是对称的。

那么假设第一天价格为 1。那么到了第 k 天后,这列数字的顶端(即股价最大值)是 $1+m(k-1)$,这列数字的底端则是 $1+k$。由于题面说明参数满足 $M(K-1) < N$,则 $M(K-1)+1 \leq N$。也就是我们统计的三角形方案数,在第一天价格为 1 的时候,是绝对合法的。因此我们得到了价格为 1 的方案数 $M^{K-1}$。那么到一开始价格为 2, 价格为 3, 同时最后一列数也会向上移一格。一直下去我们会发现那列数会触及到 n 的限制。

当触及到了限制以后,那列数仍会往上走。超过这个限制的方案数我们则不会统计。
你可以画个图。由于对称,我们可以把跨界的方案数全部相加除以二。由于不好画图,细节还是自己想吧。

然后最终我们得到的方案如下:
令第 k 列数的和为 $W=m^{k-1}$

则未触及 N 的方案数为 $ansa=W(n-m(k-1))$

触及了 N 的方案数为 $ansb=\frac {W(mk-m-k+2)}{2}=\frac {W(m-1)(k-1)}{2}$

最终总方案数为 $ans=ansa+ansb=W(n-m(k-1))+\frac {W(m-1)(k-1)}{2}$

我调了一下午,最终发现错在求逆元处。

Code

// Code by ajcxsu
// Problem: sequence

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,k,m,p;
template<typename T> void gn(T &x) {
    x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

ll qpow(ll x,ll y) {
    x%=p;
    ll ret=1;
    while(y) {
        if(y&1) ret=(ret*x)%p;
        x=(x*x)%p;
        y>>=1;
    }
    return ret;
}

void exgcd(ll a,ll b,ll &x, ll &y) {
    if(!b) {
        x=1, y=0;
        return;
    }
    ll xb,yb;
    exgcd(b,a%b,xb,yb);
    x=yb, y=xb-a/b*yb;
}

ll inv(ll x) {
    ll n1,n2;
    exgcd(x,p,n1,n2);
    return n1;
}

int main() {
    gn(n),gn(k),gn(m),gn(p);
    ll W=qpow(m,k-1);
    ll ans=((n-m*(k-1))%p)*W;
    ans%=p;
    ll ansb;
    ansb=W*(k-1), ansb%=p;
    ansb*=m-1, ansb%=p;
    ansb*=inv(2), ansb%=p;
    ans=((ans+ansb)%p+p)%p;
    printf("%lld\n",(long long)ans);
    return 0;
}

本文链接:https://pst.iorinn.moe/archives/sol_luogu_3228.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material