bzoj 2323: [ZJOI2011]细胞

题面

题意

给出一个数字串表示一个细胞,将其分为若干段等大小球,每个球内有一段数字,每一段再分为该数字大小个小球,每个小球与两边的有丝连接(除了两头的),每一个小球至少退化一条丝,那么有几种不同的分法.

做法

经过分析之后,可以发现分段与去掉丝两部相互独立,而且退化这一步的种类数恰好是斐波那契数,因为数字大小是10^100级别的,因此要用矩阵快速幂来写,然后问题就在与分段.

可以用dp来实现,dp[i]表示i到n这一段的种类数,那么dp[i]转移到dp[i-1]可以枚举以i-1为左端点的所有数字段,该数字段的种类数与剩余部分的种类数(已用dp记录)的积之和即为dp[i-1].

最后dp[1]就是答案.

代码

实现起来并不是很长

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define N 1010
#define M 1000000007
using namespace std;

ll n;
char str[N];
struct Jz
{
    ll num[][];
    Jz()
    {
        num[][]=num[][]=;
        num[][]=num[][]=;
    }
    void ql()
    {
        memset(num,,sizeof(num));
    }
    Jz operator + (const Jz &u) const
    {
        Jz res;
        ll i,j;
        for(i=;i<=;i++)
        {
            for(j=;j<=;j++)
            {
                res.num[i][j]=(num[i][j]+u.num[i][j])%M;
            }
        }
        return res;
    }
    Jz operator * (const Jz &u) const
    {
        Jz res;
        ll i,j,k;
        res.ql();
        for(i=;i<=;i++)
        {
            for(j=;j<=;j++)
            {
                for(k=;k<=;k++)
                {
                    res.num[i][j]+=num[i][k]*u.num[k][j]%M;
                    res.num[i][j]%=M;
                }
            }
        }
        return res;
    }
    Jz pw(ll u)
    {
        Jz res,v;
        v=*this;
        for(;u>;)
        {
            if(u&) res=res*v;
            v=v*v;
            u>>=;
        }
        return res;
    }
};
Jz dp[N],fb;

int main()
{
    ll i,j;
    scanf("%lld%s",&n,str+);
    fb.num[][]=;
    fb.num[][]=fb.num[][]=fb.num[][]=;
    for(i=n;i>=;i--)
    {
        Jz now;
        dp[i].ql();
        for(j=i;j<=n;j++)
        {
            now=now.pw()*fb.pw(str[j]-);
            dp[i]=dp[i]+dp[j+]*now;
        }
    }
    cout<<dp[].num[][]%M;
}