BZOJ2173 整数的lqp拆分（生成函数）

　　首先有序整数拆分有个显然的递推式是g(n)=Σg(i) (i=0~n-1)，即枚举加入最后一个数之前和是多少。（虽然不用递推式也能显然地知道答案是2^n-1）。

　　类似地，lqp拆分有递推式f(n)=Σf(i)fib(n-i) (i=0~n-1)。由乘法分配律就可以推出。特别地，f(0)=1。

　　又是一个卷积。是不是可以直接算了？啊要分治FFTn有1e6而且还不是NTT模数……肯定跑不过去啊。于是考虑生成函数。

　　设其生成函数为F(x)，斐波拉契数列的生成函数为FIB(x)。则F(x)=F(x)·FIB(x)+1。因为f(0)=1是我们的特殊规定所以补上1。即有F(x)=1/(1-FIB(x))。

　　考虑求出FIB(x)的有限表示。可以把fib(n)的递推式也看做卷积。设a₁=1,a₂=1，则有fib(n)=Σfib(i)a(n-i) (i=0~n-1)。而a的生成函数为A(x)=x+x²。那么有FIB(x)=FIB(x)·A(x)+x。有FIB(x)=x/(1-A(x))=x/(1-x-x²)。于是代入得F(x)=1/[1-x/(1-x-x²)]=1-x/(x²+2x-1)。

　　这个求出来……多项式求逆？照样爆炸啊。

　　据说可以用特征根。然而那是啥玩意啊？

　　推了半天……不如打表！

　　则显然f(n)=2f(n-1)+f(n-2)。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define P 1000000007

#define N 1000010

int n,f[N];

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj2173.in","r",stdin);

    freopen("bzoj2173.out","w",stdout);

    const char LL[]="%I64d";

#else

    const char LL[]="%lld";

#endif

    n=read();

    f[]=,f[]=;

    for (int i=;i<=n;i++) f[i]=((f[i-]<<)%P+f[i-])%P;

    cout<<f[n];

    return ;

}

巴特西

BZOJ2173 整数的lqp拆分（生成函数）

最新文章

热门文章