题解 P4541 【[ZJOI2011]细胞】

· · 题解

首先先来翻译一下并不明确的题意

给你一个长度为1000的仅含1~9的字符串,现在我们将它随意的切成一些段并且每段的长度至少为1,将切开的每一段数视为一个十进制数字,并且将他们求和，记这个和为T

那么我希望你求出

\sum_{T}fib(T-1)

也就是说我们枚举所有可能的划分然后计算出一个T值,这个T值对答案的贡献为fibonacci数列的第T-1项

好了那这个题意看起来可能有点过于和题面无关了

那么我们来解释一下这个式子是怎么推出来的

首先我们根据题意可以得到在第一步分裂之后方案数的多少仅仅和小球的数目有关，而小球的数目其实就是分割出的数字之和，也就是T

那么我们直接考虑T个球的方案数是不太科学的，让我们来考虑有n条边时的方案数是f_{n}

那么首先我们的第一条边肯定是要退化的这个显然没有任何问题(否则这个结构就不合法了因为第一个球没有退化边)

但是第二条边退不退化就说不好了

那么假如第2个边退化，那么我们就递归到了一个第2个边被钦定退化的子问题,这个子问题的方案数就是f(n-1)

否则第3条边就必须退化了,那么我们就递归到了一个第3条边被钦定退化的子问题,这个子问题的方案数就是f(n-2)

所以我们可以推出一个有趣的递归式

f(0)=0,f(1)=1 f(n)=f(n-1)+f(n-2)

应该都知道f(n)就是Fibonacci数列的第n项了吧……

那么由于T个球恰好有T-1条边，所以我们的方案数就是Fib(T-1)了

那么问题来了,我们该怎么求呢?

这里如果是一个一般一些的数列我们可以使用矩阵乘法

不过这题的话我们会发现我们要求的东西似乎是斐波那契数列

所以众所周知,斐波那契数列有一个通项公式

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

等等这公式里全是无理数你让我怎么算？

注意到我们是在模剩余系下做到运算,如果我们可以找到一个数x使得x^2 \equiv 5 \mod (10^9+7)的话，我们就可以使用x来代替我们式子中的根号5,于是我们就可以愉快的计算了

换句话说我们就是要找到5的二次剩余

然后我们暴力的试了一下发现在模10^9+7的时候并没有我们需要的x。换句话说在这个剩余系里我们没办法对5开方……

怎么办呢？

如果在实数里面我们开方失败的时候会强行定义一个i来代表\sqrt{-1},通过强行引入复数来使得我们可以对负数开方

因此我们在膜剩余系下也可以使用同样的套路

我们定义数对(a,b)表示形如a+b\sqrt{5}之类的数字

那么我们会发现

(a_{1}+b_{1}\sqrt{5})+(a_{2}+b_{2}\sqrt{5})=(a_{1}+a_{2})+(b_{1}+b_{2})\sqrt{5} (a_{1}+b_{1}\sqrt{5})-(a_{2}+b_{2}\sqrt{5})=(a_{1}-a_{2})+(b_{1}-b_{2})\sqrt{5} (a_{1}+b_{1}\sqrt{5})×(a_{1}+b_{1}\sqrt{5})=(a_{1}a_{2}+5b_{1}b_{2})+(b_{1}a_{2}+b_{2}a_{1})\sqrt{5} \frac{(a_{1}+b_{1}\sqrt{5})}{(a_{2}+b_{2}\sqrt{5})}=\frac{(a_{1}+b_{1}\sqrt{5})(a_{2}-b_{2}\sqrt{5})}{(a_{2}+b_{2}\sqrt{5})(a_{2}-b_{2}\sqrt{5})} =\frac{(a_{1}a_{2}-5b_{1}b_{2})+(b_{1}a_{2}-b_{2}a_{1})\sqrt{5}}{a_{2}^{2}-5b_{2}^{2}}

换句话说我们发现这样的数对(a,b)是对加减乘除运算全部封闭的,因此我们可以用这样的数对来套用Fibonacci数列的通项公式,由于最后根号5全部会被消掉因此我们可以最后直接提取数对的a部分就行了

好了我们接着来看如何计算题目中给定的式子

\sum_{T}Fib(T-1) =\frac{1}{\sqrt{5}}(\sum_{T}(\frac{1+\sqrt{5}}{2})^{T-1}-\sum_{T}(\frac{1-\sqrt{5}}{2})^{T-1})

因此我们分别计算两个次幂的和就可以了

那这个东西怎么计算呢？

我们大力O(N^2)dp

设dp_{i}表示在i这里切了一刀的前缀的次幂之和,转移就是十分显然的枚举上一刀切到了那里

dp_{i}=\sum_{j=0}^{i-1}dp_{j}cst(i,j)

其中cst(i,j)代表的就是(i,j)底数的这一段字符串对应十进制数字次幂

那么cst(i,j)怎么计算呢？

很简单我们考虑这样一个过程假如我们已经知道了底数的1926081次幂,设它是a(当然实际的题目中不会出现这个次幂)现在想要计算底数的192680817次幂设这个数是b

那么我们可以得到一个这样的等式就是

a^{10}×base^7=b

所以我们预处理一下base的1~9次幂然后每次在数字后边插入一个字符就可以递推出所有的cst(i,j)了

然后我们就可以愉快的计算啦~

对了这个算法常数会比矩乘的做法小很多很多，目前这份代码暂时是rk1.比rk2快3倍

上代码~

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e3+10;typedef long long ll;const ll mod=1e9+7;
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;}
int n;int m;char mde[N];
struct cmp//手写复数类 
{
    ll r;ll v;
    friend cmp operator +(cmp a,cmp b){return (cmp){(a.r+b.r)%mod,(a.v+b.v)%mod};}
    friend cmp operator *(cmp a,cmp b){return (cmp){(a.r*b.r+5*a.v*b.v)%mod,(a.r*b.v+a.v*b.r)%mod};}
    friend cmp operator -(cmp a,cmp b){return (cmp){(a.r+mod-b.r)%mod,(a.v+mod-b.v)%mod};}
    friend cmp operator /(cmp a,cmp b)
    {
        ll inv=po((b.r*b.r+mod-5*b.v*b.v%mod)%mod,mod-2);
        return (cmp){(a.r*b.r%mod+mod-5*a.v*b.v%mod)*inv%mod,(a.v*b.r%mod+mod-a.r*b.v%mod)*inv%mod};
    }
}dp[N],mi[N],tmi[N],cst[N];
inline cmp po(cmp a,int p){cmp r=(cmp){1,0};for(;p;p>>=1,a=a*a)if(p&1)r=r*a;return r;}
inline cmp solve(cmp bas)//计算其中的一个幂次 
{
    tmi[0]=mi[0]=(cmp){1,1};tmi[1]=mi[1]=bas;
    for(int i=2;i<=9;i++)tmi[i]=tmi[i-1]*tmi[1];
    for(int i=0;i<=n;i++)cst[i]=(cmp){1,0};dp[0]=(cmp){1,0};
    for(int i=1;i<=n;i++)
    {
        dp[i]=(cmp){0,0};
        for(int j=0;j<i;j++)cst[j]=po(cst[j],10)*tmi[mde[i]-'0'];
        for(int j=0;j<i;j++)dp[i]=dp[i]+dp[j]*cst[j];
    }dp[n]=dp[n]/bas;dp[n]=dp[n]*(cmp){0,400000003};return dp[n];
}
int main()
{
    scanf("%d",&n);scanf("%s",mde+1);//然后直接暴力套通项公式就行了 
    printf("%lld",(solve((cmp){500000004,500000004})-solve((cmp){500000004,500000003})).r);
    return 0;
}