[HNOI2013] 数列

ajcxsu
ajcxsu 2018年03月10日
  • 34 次阅读

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://acxblog.site/archives/sol_luogu_3228.html
本文采用 CC BY-NC-SA 3.0 协议进行许可