Press "Enter" to skip to content

2020 杭电多校第一场

第一场

比赛总结

这次比赛十分难受,又是倒数的一天。开场斐波那契,最后一小时总算过了,┭┮﹏┭┮。

1005.Fibonacci Sum(hdoj6755)

题目链接

题面

The Fibonacci numbers are defined as below:

$$F_0=0,F_1=1$$

$$F_n=F_{n-1}+F_{n-2}(n>1)$$

Given three integers $N$, $C$ and $K$, calculate the following summation:

$$(F_0)^K+(F_C)^K+(F_{2C})^K+\cdots +(F_{NC})^K$$

Since the answer can be huge, output it modulo 1000000009 (109+9).

标签

数论 逆元 二次剩余 快速幂 高性能

解题思路

已知斐波那契数列的通项公式

$$F_n=\frac{1}{\sqrt 5}\left(\left(\frac{1+\sqrt 5}{2}\right)^n-\left(\frac{1-\sqrt 5}{2}\right)^n\right)$$

因为$5^{\frac{(1e9+9-1)}{2}}\equiv 1(\mathrm{mod}\ 1e9+9)$

所以在模数是$1e9+9$的时候,$\sqrt 5$可以用$x^2\equiv5(\mathrm {mod}\ 1000000009)$中的$x$来替代

虽然正常情况下$x$需要用[BSGS](https://oi-wiki.org/math/bsgs/)算法,但是我们这里既然只求一次,那么就可以直接穷举得到$x=383008016$。

接下来我们令$a=\frac{1+\sqrt 5}{2}\ b=\frac{1-\sqrt 5}{2}$

$a\equiv(1+x)inv(2)\equiv691504013(\mathrm{mod}\ {100000009})\\b=(1-x)inv(2)\equiv308495997(\mathrm{mod}\ {100000009})$

$$(a^{cn}-b^{cn})^k=C_k^0(a^{cn})^k-C_k^1(a^{cn})^{k-1}b^c+\\\cdots+(-1)^{r}C_k^r(a^{cn})^{k-r}(b^{cn})^r+\cdots\\+(-1)^{k-1}C_k^{k-1}a^{cn}(b^{cn})^{k-1}+(-1)^nC_k^{k}(b^{cn})^n$$

可以发现每一项构成为$(-1)^{r}C_k^r(a^{cn})^{k-r}(b^{cn})^r$把$n$提取出去发现这是一个以公比为$q=(a^c)^{k-r}(b^{c})^r$的等比数列,所以答案为

$$\sum_{r=0}^k(-1)^rC^r_k\frac{q(q^n-1)}{q-1}$$

阶乘和$a^k$用预处理可以加速运算时间复杂度为$klog (n+c)$

但是你以为这就完了吗?,太年轻了少年,我这样就被T了一发,可以通过欧拉降幂把时间复杂度优化为$k\log(\mathrm{mod})$才能勉强卡过

虽然我比赛的时候这样的复杂度就能过,但是赛后再次提交就被T了?,然后我们继续考虑怎么优化?

  • 使用线性筛来预处理阶乘的逆(大约-1000ms)
  • 对前面的系数打表(几乎没变化)?
  • 对两个快速幂$(a^c)^k$和$(a^{cn})^k$打表$O(k+\log(p))$(大约-2000ms)
  • 对$(a^c)^i(b^c)^{k-i}-1$的逆元打表(大约-1500ms)

我就讲一下逆元的打表吧,其他的都应该很好理解,实在不行看一下我的程序?,逆元的打表十分有意思

我们令$d_i=(a^c)^i(b^c)^{k-i}-1$,$M_n=d_0d_1d_2\cdots d_n$我们是不是可以求出$M_k$的逆元$M_k^{-1}=\frac{1}{d_0d_1d_2\cdots d_k}$

然后我们要求出每个$d_i$的逆元$\frac{1}{d_i}=M_k^{-1}(d_{i+1}d_{i+2}\cdots d_k)M_{i-1}$,$M_{i}^{-1}$可以通过从$k$遍历$d_i$,就可以得到每个$d_i$的逆元了。

这样处理后时间复杂度就降为$O(k)$

参考代码

187ms

#include <iostream>
#include <cstring>
#include <cstdio>
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)1e5+5;
const ll MOD=(int)1e9+9;
const ll phi=1000000008;
ll inv[MAXN],fac[MAXN],CA[MAXN],CB[MAXN],p[MAXN],NA[MAXN],NB[MAXN],inv2[MAXN],pre[MAXN],tm[MAXN];
const ll A=691504013,B=308495997;

inline ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
void init()
{
    CA[0]=CB[0]=1;
    NA[0]=NB[0]=1;
    fac[0] = 1;
    //对阶乘打表
    for(int i=1; i<MAXN; i++)fac[i] = fac[i-1] * i % MOD;
    
    //对阶乘的逆打表
    inv[0]=inv[1] = 1;
    for (int i=2; i<=MAXN; ++i)inv[i] = (-(MOD/i))*inv[MOD%i]%MOD;
    for (int i=2; i<=MAXN; ++i)inv[i]=(inv[i]*inv[i-1])%MOD;


    //对1/sqrt(5)^n打表没有啥用
    p[0]=1;
    for(int i=1; i<MAXN; i++) p[i]=p[i-1]*276601605%MOD;
    
}

int main()
{
    int T;
    ll n,k,c;
    init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld%lld",&n,&c,&k);
        
        c%=phi;

        //对快速幂打表
        ll ca=powmod(A,c,MOD),cb=powmod(B,c,MOD);
        ll na=powmod(A,(n%phi)*c%phi,MOD),nb=powmod(B,(n%phi)*c%phi,MOD);
        for(int i=1; i<=k; i++)
        {
            CA[i] = CA[i - 1] * ca % MOD;
            CB[i] = CB[i - 1] * cb % MOD;
            NA[i] = NA[i - 1] * na % MOD;
            NB[i] = NB[i - 1] * nb % MOD;
        }

        //对逆元打表
        ll mul=1;
        for (int i = 0; i <= k; i++)
        {
            tm[i] = (CA[k - i] * CB[i] - 1) % MOD;
            if (tm[i])mul *= tm[i];
            mul %= MOD;
            pre[i] = mul;
        }
        mul=powmod(mul,MOD-2,MOD);
        for (int i = k; i >=0; i--)
        {
            if(i)inv2[i]=(pre[i-1]*mul)%MOD;else inv2[i]=mul;
            if(tm[i])mul=mul*tm[i]%MOD;
        }
        
        //代入公式求解答案
        ll ans = 0;
        for(int i=0; i<=k; i++)
        {
            ll t = CA[k - i] * CB[i] % MOD;
            ll C = fac[k]*inv[k-i]% MOD * inv[i] % MOD;
            ll tmp = t * (NA[k-i] * NB[i] % MOD - 1) % MOD * inv2[i] % MOD;
            if(t == 1) tmp = n % MOD;
            tmp = tmp * C % MOD;
            if(i & 1) ans -= tmp;
            else      ans += tmp;
            ans %= MOD;
        }
        ans = ((ans * p[k]) % MOD+ MOD) % MOD;
        printf("%lld\n",ans);
    }
    return 0;
}

1009 Leading Robots (hdoj 6759)

题目链接

解题思路

画图,视每个机器人为一个2次函数,求哪些可以出现在最上面

以加速度降序排列。加速度最高的必为答案之一,维护栈,栈顶与次顶的追及时间必然大于当前边,否则被当前边覆盖,退栈并继续判断,判断成功后加入当前边。 注意重复点答案不累加。

参考代码

int n,cnt;
struct node {
    int x,a; bool f;
    bool operator<(const node&t) const
    {
        return a>t.a;
    }
}p[N],b[N];

double get_t(int i,int j)//j>i
{
    return (double)(p[j].x-p[i].x)/(p[i].a-p[j].a);
}

int st[N],top;

void solve()
{
    scanf("%d",&n); cnt=0;
    for(int i=0;i<n;++i)
    {
        scanf("%d%d",&b[i].x,&b[i].a);
        b[i].f=0;
    }
    sort(b,b+n);
    for(int i=1;i<n;++i)
    {
        if(b[i].x==b[i-1].x&&b[i].a==b[i-1].a)
        {
            b[i].f=b[i-1].f=1;
        }
    }
    p[++cnt]=b[0];
    for(int i=1;i<n;++i)
    {
        if(b[i].x>p[cnt].x)
        {
            p[++cnt]=b[i];
        }
    }
    if(cnt==1)
    {
        if(p[cnt].f==1) printf("0\n");
        else  printf("1\n");
        return;
    }
    
    top=0;
    st[++top]=1;
    for(int i=2;i<=cnt;++i)
    {
        if(top<2)  { st[++top]=i; continue;}
        
        double pre=get_t(st[top-1], st[top]),t=get_t(st[top], i);
        if(t<pre)
        {
            st[++top]=i;
        }
        else
        {
            --top; --i;
        }
    }
    int ans=0;
    for(int i=1;i<=top;++i)
    {
        if(p[st[i]].f==0) ++ans;
    }
    cout<<ans<<endl;
}

Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments
0
喜欢聆听每一种不同的观点,欢迎评论。x
()
x