A simple Blog for wyx I've been down the bottle hoping.
codeforces 717A 数学 斐波那契数列 二项式定理
发表于: | 分类: Oi | 评论:0 | 阅读:185

这场的题出奇的难,一道A题做了快一上午了

题目大意

给定整数 $k,l,r$,设 T 为所有长度在 $[l,r]$ 间且不存在相邻两个0的01串的集合,求从 $T$ 中取出恰好 $k$ 个长度相同的串的方案数 $1\le k\le 200,1\le l \le r\le 10^18$

下面我们来一起看一下一道纯良NOIP普及组题目是如何一步一步变得如此丧心病狂的 233333

首先我们用 $T_i$ 表示长度为 $i$ 的满足条件的 01 串的方案数,我们考虑第 $i$ 位的选择,容易发现

$$T_i = T_{i-1} + T_{i-2} $$
$$T_0 = 1, T_1 = 2$$

然后我们发现这个东西其实递归公式是一个斐波那契数列,如果你知道这个然后开始算组合数计算的话,这是一道优秀的普及组题目。

但是这显然不足以解决现在这个问题,为了方便我们让

$$f_i = f_{i-1} + f_{i-2}, f_0 = 0, f_1 = 1$$

那么就有 $T_i = f_{i+2}$

然后令$H_t = \sum_{i=0}^{t-1} C_{f_i}^k$

那么显然我们求的就是 $H_{r+3} - H_{l+2}$

现在的问题就变成怎么求 $H_i$

我们发现$C_n^k = \frac{n!}{k!(n-k)!} = \frac{1}{k!}(n-k)(n-k+1)\dots(n-1)(n)$

你会发现这是一个 $k$ 次多项式, 所以其实 $C_n^k = \sum_{i=0}^k {a_i*x^i}$

在$k^2$的时间内我们就可以得到 这个多项式啦

然后呢?

$H_t = \sum_{i=0}^{t-1}\sum_{j=0}^k{a_j\times f_i^j}$

这样的形式不好看,我们把这个循环换一下

$H_t = \sum_{i=0}^k \sum_{j=0}^{t-1}{a_i f_j^i} = \sum_{i=0}^k a_i \sum_{j=0}^{t-1}f_j^i$

现在的问题就变成了怎么求 $\sum_{j=0}^{t-1} f_j^i$

我们令$i=1$, 提高组D1T3, $i=2$, 省选 D1T2

然后我们继续变,我们发现矩阵乘法这方法比较鸡,因为几次方就需要大概多少行,200直接GG

然后我们换一个方法

$$f_i = f_{i-1} + f_{i-2}$$

我们把这东西的通项公式搞出来

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

搞到这距离正解就已经不是非常的远辣

我们需要一个先决条件:$(a+b\sqrt{5})$这东西的加减乘除在$(a+b\sqrt{5}) \mod 1e9+7$内完全封闭,也就是说我们用$a+b\sqrt{5}$作为新的最小单位能做完整个问题

那么现在就非常好做辣,我们接着变形

$$\sum_{j=0}^{n-1}F_j^i=(\frac{1}{\sqrt{5}})^i\sum_{j=0}^{n-1}[(\frac{1+\sqrt{5}}{2})^j-(\frac{1-\sqrt{5}}{2})^j]^i $$

然后?

二项式定理

$(a+b)^n = \sum_{i=0}^n C_n^i{a_i*b^{n-i}}$
$(a-b)^n = \sum_{i=0}^n C_n^i\times (-1)^{n-i}{a^i\times b^{n-i}}$

所以上面的那个式子

$$ =(\frac{1}{\sqrt{5}})^i\sum_{j=0}^{n-1}\sum_{k=0}^iC_i^k(-1)^{i-k}(\frac{1+\sqrt{5}}{2})^{jk}(\frac{1-\sqrt{5}}{2})^{j(i-k)} $$

再把两个循环倒过来
然后就行辣

$$ =(\frac{1}{\sqrt{5}})^i\sum_{k=0}^iC_i^k(-1)^{i-k}\sum_{j=0}^{n-1}[(\frac{1+\sqrt{5}}{2})^k(\frac{1-\sqrt{5}}{2})^{(i-k)}]^j$$

你看到了什么?等比数列求和!
然后我们就能搞辣!

这个复杂度就是 $k^2 \log{n}$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 200;
const int Max = 200+5;
const int mod = 1e9+7;

inline int pow(int a,int b) {
    int res = 1;
    for(;b;b>>=1,a=(LL)a*a%mod)
        if(b&1)
            res = (LL) res * a % mod;
    return res;
}

struct data{
    LL x,y;
    data(){x=y=0;}
    data(LL _x):x(_x){y=0;}
    data(LL _x,LL _y){x=_x,y=_y;}
    inline data conj(){return data(x,(mod-y)%mod);}
};

inline data operator +(const data&a,const data&b) {
    return data((a.x+b.x)%mod,(a.y+b.y)%mod);
}

inline data operator -(const data&a,const data&b) {
    return data((a.x-b.x+mod)%mod,(a.y-b.y+mod)%mod);
}

inline data operator *(const data&a,const data&b) {
    return data((a.x*b.x+5*a.y*b.y)%mod,(a.x*b.y+a.y*b.x)%mod);
}

inline data operator /(data a,data b){
    data tmp=b.conj();
    a=a*tmp;b=b*tmp;
    a=a*(pow((int)b.x,mod-2));
    return a;
}

inline data operator ^(data a,LL n){
    data ans(1);
    while(n){
        if(n&1)ans=ans*a;
        a=a*a;n>>=1;
    }
    return ans;
} 

const data S(0, 1), A = (1+S) / 2, B = (1-S) / 2;

data Fib(LL x) {
    data ans = (A^x)-(B^x);
    return ans / S;
}

data sum(data x, LL n) {
    if(x.x == 1 && x.y == 0) return n % mod;
    else return (1-(x^n))/(1-x)*x;
}

LL s[Max][Max], C[Max][Max];

inline data solve(int k, LL n) {
    data ans = 0;
    for(int i=1;i<=k;++i) {
        data w = 0;
        for(int j=0;j<=i;++j) {
            data v = sum((A^j)*(B^(i-j)),n)*C[i][j];
            if((i-j)&1) w = w - v;
            else w = w + v;
        }
        w = w * ((1/S)^i);
        w = w * s[k][i];
        if((k-i)&1) ans = ans - w;
        else ans = ans + w;
//      cout << ans.x << endl;
    }
    return ans;
}

int main() {
    int k; LL  l, r;
    cin >> k >> l >> r;
    l += 2, r += 2;
    for(int i=0;i<=N;++i) {
        C[i][0] = 1;
        for(int j=1;j<=i;++j) {
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
        }
    }
    s[1][1] = 1;
    for(int i=2;i<=N;++i) {
        for(int j=1;j<=i;++j) {
            s[i][j] = (s[i-1][j-1] + (i-1)*s[i-1][j]) % mod;
        }
    } 
    data ans = solve(k, r) - solve(k, l-1);
    for(int i=1;i<=k;++i) ans = ans / i;
    cout << ans.x << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP