【题解】小C的和

题意

给你 $n$ ,求 $\sum_{i=0}^{\left \lfloor \frac{n}{2} \right \rfloor}C_{n-i}^{i}$ ，其中 $C_{n-i}^{i}$ 表示组合数。对 $10^9+9$ 取模

题解

看到式子首先可以打表看看，有:

敏感的一看就会发现这是个斐波那契数列，利用矩阵快速幂就可以解决了。这里给出证明。
设 $n$ 为奇数

$f_n=\sum_{i=0}^{\left \lfloor \frac{n}{2} \right \rfloor}C_{n-i}^{i}=C_{n}^0+C_{n-1}^1+C_{n-2}^2+\cdots+C_{n-\left \lfloor \frac{n}{2} \right \rfloor}^{\left \lfloor \frac{n}{2} \right \rfloor}$
$f_{n+1}=\sum_{i=0}^{\left \lfloor \frac{n+1}{2} \right \rfloor}C_{n+1-i}^{i}=C_{n+1}^0+C_{n}^1+C_{n-1}^2+\cdots+C_{n-\left \lfloor \frac{n+1}{2} \right \rfloor}^{\left \lfloor \frac{n+1}{2} \right \rfloor-1}+C_{n+1-\left \lfloor \frac{n+1}{2} \right \rfloor}^{\left \lfloor \frac{n+1}{2} \right \rfloor}$
$f_{n+2}=\sum_{i=0}^{\left \lfloor \frac{n+2}{2} \right \rfloor}C_{n+2-i}^{i}=C_{n+2}^0+C_{n+1}^1+C_{n}^2+\cdots+C_{n+1-\left \lfloor \frac{n+2}{2} \right \rfloor}^{\left \lfloor \frac{n+2}{2} \right \rfloor-1}+C_{n+2-\left \lfloor \frac{n+2}{2} \right \rfloor}^{\left \lfloor \frac{n+2}{2} \right \rfloor}$
那么

$f_n+f_{n+1}=C_{n+1}^0+C_n^0+C_{n}^1+C_{n-1}^1+C_{n-1}^2+\cdots+C_{n-\left \lfloor \frac{n}{2} \right \rfloor}^{\left \lfloor \frac{n}{2} \right \rfloor}+C_{n-\left \lfloor \frac{n+1}{2} \right \rfloor}^{\left \lfloor \frac{n+1}{2} \right \rfloor-1}+C_{n+1-\left \lfloor \frac{n+1}{2} \right \rfloor}^{\left \lfloor \frac{n+1}{2} \right \rfloor}$
根据杨辉三角的公式有 $C_i^j=C_{i-1}^j+C_{i-1}^{j-1}$
令 $n$ 为偶数，所以上式有

$f_n+f_{n+1}=C_{n+1}^0+C_{n+1}^{1}+C_{n}^{2}+\cdots+C_{\frac{n}{2}+1}^{\frac{n}{2}}+C_{\frac{n}{2}+1}^{\frac{n}{2}}$
由于 $C_n^m=C_{n}^{n-m}$ 且 $C_{n+2}^0=C_{n+1}^0=1$
所以有 $f_{n+2}=f_{n+1}+f_n$

代码

#define MAX 2
typedef struct {
int m[MAX][MAX];
}Matrix;
const int mod=1e9+9;
Matrix P={1,1,1,0};
Matrix I={1,0,0,1};
Matrix Matrixmul(Matrix a,Matrix b)
{
    int i,j,k;
    Matrix c;
    for(i=0;i<MAX;i++)
        for(j=0;j<MAX;j++)
        {
            c.m[i][j]=0;
            for(k=0;k<MAX;k++)
            {
                c.m[i][j]=(c.m[i][j]+1ll*a.m[i][k]*b.m[k][j]%mod)%mod;
            }
        }
        return c;
}
Matrix quickpow(long long n)
{
    Matrix m=P,b=I;
    while(n>0)
    {
        if(n%2==1)
            b=Matrixmul(b,m);
        n=n/2;
        m=Matrixmul(m,m);
    }
    return b;
}
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    int Sum(int n) {
        // write code here
        Matrix a;
        a=quickpow(n);
        return a.m[0][0];
    }
};

二次剩余版

const int mod=1e9+9;
long long quickmod(long long a,long long b)
{
    long long ans=1;
    while(b)
    {
        if(b%2==1)
            ans=ans*a%mod;
        a=a*a%mod;
        b=b/2;
    }
    return ans;
}
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    int Sum(int n) {
        // write code here
        return 276601605LL*((quickmod(691504013LL,n+1)-quickmod(308495997LL,n+1)+mod)%mod)%mod;
    }
};